python 3.x - Understanding cuthill mckee clustering

Question

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

Answer 1

Your relabelling is wrong. You need to relabel the nodes according to their position in rcm. The following mapping works.

import networkx as nx
import matplotlib.pyplot as plt
from networkx.utils import cuthill_mckee_ordering
G = nx.gnm_random_graph(n=30, m=55, seed=1)
rcm = list(cuthill_mckee_ordering(G))

d = {node:rcm.index(node) for node in G}
H = nx.relabel_nodes(G, mapping=d)
H_adj = nx.adjacency_matrix(H,nodelist=range(30))
plt.spy(H_adj)
plt.show()