I'm trying to reduce the bandwidth of the entries in the adjacency matrix of a graph via Cuthill-McKee
algorithm.
I have the following input graph and I could get the permutation order.
import networkx as nx
import matplotlib.pyplot as plt
from networkx.utils import reverse_cuthill_mckee_ordering, cuthill_mckee_ordering
G = nx.gnm_random_graph(n=30, m=55, seed=1)
nxpos = nx.spring_layout(G, dim=2, iterations=10000)
nx.set_node_attributes(G, nxpos, 'pos')
rcm = list(cuthill_mckee_ordering(G))
Next, I relabelled the nodes of the original graph
d = OrderedDict(zip(G.nodes(), rcm))
H = nx.relabel_nodes(G, mapping=d)
H_adj = nx.adjacency_matrix(H, nodelist=range(len(H.nodes())))
plt.spy(H_adj)
plt.show()
Unfortunately, the adjacency matrix H_adj
is not banded
On the other hand, when I try the below G_adj_rcm
is banded.
G_adj_rcm = nx.adjacency_matrix(G, nodelist=rcm)
plt.spy(G_adj_rcm)
plt.show()
I'm not sure if the relabelling is incorrect or if I am failing to understand how the algorithm works. Clarifications on why H_adj
is not banded will be of great help.
question from:
https://stackoverflow.com/questions/65843578/understanding-cuthill-mckee-clustering 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…