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

A = np.array([
    [0,1,1,0,0,0],
    [1,0,1,0,0,0],
    [1,1,0,1,0,0],
    [0,0,1,0,1,1],
    [0,0,0,1,0,1],
    [0,0,0,1,1,0]], dtype=float)

g = nx.from_numpy_matrix(A)
layout = nx.spring_layout(g, pos=nx.circular_layout(g))
nx.draw(g, pos=layout, with_labels=True, node_color='white')
plt.show()

# compute the degree matrix, by summing rows (or columns, since it's symmetric)
d = np.sum(A, axis=0)
print(d)

# put them on the diagonal
D = np.diag(d)
print(D)

# compute the Laplacian
L = D - A
print(L)

# compute eigenvectors and eigenvalues of the Laplacian
val, Vec = np.linalg.eigh(L)
print(val)
print(Vec)

# verify that they satisfy definition of eigenvalues/vectors
# is there one close to 3?
np.any(np.isclose(val, 3))

# check that multiplication by 3 and multiplication by eigenvector give same answer
idx_lambda3 = np.argmin(np.abs(val - 3))
v3 = Vec[:, idx_lambda3]
print(v3)
print(L @ v3)

# graph them so that we can see the eigenvalue corresponding to the fiedler vector
plt.plot(np.sort(val), linestyle='-', marker='o')
plt.show()

# get the fiedler vector, look out for the sign change
f = Vec[:, np.argsort(val)[1]]
plt.plot(f, linestyle='-', marker='o'); plt.show();

# color by fiedler vector sign change
color = ['orange' if eigv > 0 else 'gray' for eigv in f]
nx.draw(g, pos=layout, with_labels=True, node_color=color); plt.show();