/usr/lib/python3/dist-packages/networkx/utils/rcm.py is in python3-networkx 1.11-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 | """
Cuthill-McKee ordering of graph nodes to produce sparse matrices
"""
# Copyright (C) 2011-2014 by
# Aric Hagberg <aric.hagberg@gmail.com>
# All rights reserved.
# BSD license.
from collections import deque
from operator import itemgetter
import networkx as nx
__author__ = """\n""".join(['Aric Hagberg <aric.hagberg@gmail.com>'])
__all__ = ['cuthill_mckee_ordering',
'reverse_cuthill_mckee_ordering']
def cuthill_mckee_ordering(G, heuristic=None):
"""Generate an ordering (permutation) of the graph nodes to make
a sparse matrix.
Uses the Cuthill-McKee heuristic (based on breadth-first search) [1]_.
Parameters
----------
G : graph
A NetworkX graph
heuristic : function, optional
Function to choose starting node for RCM algorithm. If None
a node from a psuedo-peripheral pair is used. A user-defined function
can be supplied that takes a graph object and returns a single node.
Returns
-------
nodes : generator
Generator of nodes in Cuthill-McKee ordering.
Examples
--------
>>> 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) # doctest: +SKIP
Smallest degree node as heuristic function:
>>> def smallest_degree(G):
... return min(G, key=G.degree)
>>> rcm = list(cuthill_mckee_ordering(G, heuristic=smallest_degree))
See Also
--------
reverse_cuthill_mckee_ordering
Notes
-----
The optimal solution the the bandwidth reduction is NP-complete [2]_.
References
----------
.. [1] E. Cuthill and J. McKee.
Reducing the bandwidth of sparse symmetric matrices,
In Proc. 24th Nat. Conf. ACM, pages 157-172, 1969.
http://doi.acm.org/10.1145/800195.805928
.. [2] Steven S. Skiena. 1997. The Algorithm Design Manual.
Springer-Verlag New York, Inc., New York, NY, USA.
"""
for c in nx.connected_components(G):
for n in connected_cuthill_mckee_ordering(G.subgraph(c), heuristic):
yield n
def reverse_cuthill_mckee_ordering(G, heuristic=None):
"""Generate an ordering (permutation) of the graph nodes to make
a sparse matrix.
Uses the reverse Cuthill-McKee heuristic (based on breadth-first search)
[1]_.
Parameters
----------
G : graph
A NetworkX graph
heuristic : function, optional
Function to choose starting node for RCM algorithm. If None
a node from a psuedo-peripheral pair is used. A user-defined function
can be supplied that takes a graph object and returns a single node.
Returns
-------
nodes : generator
Generator of nodes in reverse Cuthill-McKee ordering.
Examples
--------
>>> from networkx.utils import reverse_cuthill_mckee_ordering
>>> G = nx.path_graph(4)
>>> rcm = list(reverse_cuthill_mckee_ordering(G))
>>> A = nx.adjacency_matrix(G, nodelist=rcm) # doctest: +SKIP
Smallest degree node as heuristic function:
>>> def smallest_degree(G):
... return min(G, key=G.degree)
>>> rcm = list(reverse_cuthill_mckee_ordering(G, heuristic=smallest_degree))
See Also
--------
cuthill_mckee_ordering
Notes
-----
The optimal solution the the bandwidth reduction is NP-complete [2]_.
References
----------
.. [1] E. Cuthill and J. McKee.
Reducing the bandwidth of sparse symmetric matrices,
In Proc. 24th Nat. Conf. ACM, pages 157-72, 1969.
http://doi.acm.org/10.1145/800195.805928
.. [2] Steven S. Skiena. 1997. The Algorithm Design Manual.
Springer-Verlag New York, Inc., New York, NY, USA.
"""
return reversed(list(cuthill_mckee_ordering(G, heuristic=heuristic)))
def connected_cuthill_mckee_ordering(G, heuristic=None):
# the cuthill mckee algorithm for connected graphs
if heuristic is None:
start = pseudo_peripheral_node(G)
else:
start = heuristic(G)
visited = {start}
queue = deque([start])
while queue:
parent = queue.popleft()
yield parent
nd = sorted(G.degree(set(G[parent]) - visited).items(),
key=itemgetter(1))
children = [n for n, d in nd]
visited.update(children)
queue.extend(children)
def pseudo_peripheral_node(G):
# helper for cuthill-mckee to find a node in a "pseudo peripheral pair"
# to use as good starting node
u = next(G.nodes_iter())
lp = 0
v = u
while True:
spl = nx.shortest_path_length(G, v)
l = max(spl.values())
if l <= lp:
break
lp = l
farthest = (n for n, dist in spl.items() if dist == l)
v, deg = min(G.degree(farthest).items(), key=itemgetter(1))
return v
|