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