Mercurial > repos > shellac > guppy_basecaller

comparison env/lib/python3.7/site-packages/networkx/utils/rcm.py @ 0:26e78fe6e8c4 draft

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