Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
488 views
in Technique[技术] by (71.8m points)

python 3.x - Understanding cuthill mckee clustering

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

enter image description here

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()

enter image description here

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

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

Please log in or register to answer this question.

Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...