cuthill_mckee_ordering(G, heuristic=None)
Uses the Cuthill-McKee heuristic (based on breadth-first search) .
The optimal solution the bandwidth reduction is NP-complete .
A NetworkX graph
Function to choose starting node for RCM algorithm. If None a node from a pseudo-peripheral pair is used. A user-defined function can be supplied that takes a graph object and returns a single node.
Generator of nodes in Cuthill-McKee ordering.
Generate an ordering (permutation) of the graph nodes to make a sparse matrix.
>>> from networkx.utils import cuthill_mckee_ordering
... G = nx.path_graph(4)
... rcm = list(cuthill_mckee_ordering(G))
... A = nx.adjacency_matrix(G, nodelist=rcm)
Smallest degree node as heuristic function:
>>> def smallest_degree(G):See :
... return min(G, key=G.degree)
... rcm = list(cuthill_mckee_ordering(G, heuristic=smallest_degree))
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.utils.rcm.cuthill_mckee_ordering
networkx.utils.rcm.reverse_cuthill_mckee_ordering
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them