Spaces:
Runtime error
Runtime error
File size: 1,039 Bytes
35b22df |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
"""
======================
Reverse Cuthill--McKee
======================
Cuthill-McKee ordering of matrices
The reverse Cuthill--McKee algorithm gives a sparse matrix ordering that
reduces the matrix bandwidth.
"""
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import networkx as nx
# build low-bandwidth matrix
G = nx.grid_2d_graph(3, 3)
rcm = list(nx.utils.reverse_cuthill_mckee_ordering(G))
print("ordering", rcm)
print("unordered Laplacian matrix")
A = nx.laplacian_matrix(G)
x, y = np.nonzero(A)
# print(f"lower bandwidth: {(y - x).max()}")
# print(f"upper bandwidth: {(x - y).max()}")
print(f"bandwidth: {(y - x).max() + (x - y).max() + 1}")
print(A)
B = nx.laplacian_matrix(G, nodelist=rcm)
print("low-bandwidth Laplacian matrix")
x, y = np.nonzero(B)
# print(f"lower bandwidth: {(y - x).max()}")
# print(f"upper bandwidth: {(x - y).max()}")
print(f"bandwidth: {(y - x).max() + (x - y).max() + 1}")
print(B)
sns.heatmap(B.todense(), cbar=False, square=True, linewidths=0.5, annot=True)
plt.show()
|