import cvxpy as cp
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np

# size of matrix : n x n
n = 8

# Build a graph as in fig 1
G1 = nx.complete_graph(5)
G2 = nx.cycle_graph(range(3,7))
G2.add_node(7)
for i in range(3,7) :
    G2.add_edge(i, 7)

G = nx.compose(G1, G2) # plotting graph
nx.draw(G, with_labels=True, font_weight='bold')
plt.show()

# ------------------------------------------------------------------------------
# Fill in code
for (i, j) in nx.non_edges(G) :
    constr += [W[i,j] == 0]
    
# Check the optimality of weights in Fig 1
W_in_fig1 = np.array([[ 0.2,  0.2,  0.2,  0.2,  0.2,  0.,   0.,   0. ],
                      [ 0.2,  0.2,  0.2,  0.2,  0.2,  0.,   0.,   0. ],
                      [ 0.2,  0.2,  0.2,  0.2,  0.2,  0.,   0.,   0. ],
                      [ 0.2,  0.2,  0.2, -0.1, -0.1,  0.,   0.4,  0.2],
                      [ 0.2,  0.2,  0.2, -0.1, -0.1,  0.4,  0.,   0.2],
                      [ 0.,   0.,   0.,   0.,   0.4,  0.2,  0.2,  0.2],
                      [ 0.,   0.,   0.,   0.4,  0.,   0.2,  0.2,  0.2],
                      [ 0.,   0.,   0.,   0.2,  0.2,  0.2,  0.2,  0.2]])


# ------------------------------------------------------------------------------

print(f"prob.status : {prob.status}")
print("optimal solution W = ")
print(np.around(W.value, 4))
print(f"optimal value : {s.value:.4f}")
print(f"eigenvalues of W - (1/n)1@1.T : \n{eigs}")