Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/euler.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 Eulerian circuits and graphs. | |
3 """ | |
4 from itertools import combinations | |
5 | |
6 import networkx as nx | |
7 from ..utils import arbitrary_element, not_implemented_for | |
8 | |
9 __all__ = [ | |
10 "is_eulerian", | |
11 "eulerian_circuit", | |
12 "eulerize", | |
13 "is_semieulerian", | |
14 "has_eulerian_path", | |
15 "eulerian_path", | |
16 ] | |
17 | |
18 | |
19 def is_eulerian(G): | |
20 """Returns True if and only if `G` is Eulerian. | |
21 | |
22 A graph is *Eulerian* if it has an Eulerian circuit. An *Eulerian | |
23 circuit* is a closed walk that includes each edge of a graph exactly | |
24 once. | |
25 | |
26 Parameters | |
27 ---------- | |
28 G : NetworkX graph | |
29 A graph, either directed or undirected. | |
30 | |
31 Examples | |
32 -------- | |
33 >>> nx.is_eulerian(nx.DiGraph({0: [3], 1: [2], 2: [3], 3: [0, 1]})) | |
34 True | |
35 >>> nx.is_eulerian(nx.complete_graph(5)) | |
36 True | |
37 >>> nx.is_eulerian(nx.petersen_graph()) | |
38 False | |
39 | |
40 Notes | |
41 ----- | |
42 If the graph is not connected (or not strongly connected, for | |
43 directed graphs), this function returns False. | |
44 | |
45 """ | |
46 if G.is_directed(): | |
47 # Every node must have equal in degree and out degree and the | |
48 # graph must be strongly connected | |
49 return all( | |
50 G.in_degree(n) == G.out_degree(n) for n in G | |
51 ) and nx.is_strongly_connected(G) | |
52 # An undirected Eulerian graph has no vertices of odd degree and | |
53 # must be connected. | |
54 return all(d % 2 == 0 for v, d in G.degree()) and nx.is_connected(G) | |
55 | |
56 | |
57 def is_semieulerian(G): | |
58 """Return True iff `G` is semi-Eulerian. | |
59 | |
60 G is semi-Eulerian if it has an Eulerian path but no Eulerian circuit. | |
61 """ | |
62 return has_eulerian_path(G) and not is_eulerian(G) | |
63 | |
64 | |
65 def _find_path_start(G): | |
66 """Return a suitable starting vertex for an Eulerian path. | |
67 | |
68 If no path exists, return None. | |
69 """ | |
70 if not has_eulerian_path(G): | |
71 return None | |
72 | |
73 if is_eulerian(G): | |
74 return arbitrary_element(G) | |
75 | |
76 if G.is_directed(): | |
77 v1, v2 = [v for v in G if G.in_degree(v) != G.out_degree(v)] | |
78 # Determines which is the 'start' node (as opposed to the 'end') | |
79 if G.out_degree(v1) > G.in_degree(v1): | |
80 return v1 | |
81 else: | |
82 return v2 | |
83 | |
84 else: | |
85 # In an undirected graph randomly choose one of the possibilities | |
86 start = [v for v in G if G.degree(v) % 2 != 0][0] | |
87 return start | |
88 | |
89 | |
90 def _simplegraph_eulerian_circuit(G, source): | |
91 if G.is_directed(): | |
92 degree = G.out_degree | |
93 edges = G.out_edges | |
94 else: | |
95 degree = G.degree | |
96 edges = G.edges | |
97 vertex_stack = [source] | |
98 last_vertex = None | |
99 while vertex_stack: | |
100 current_vertex = vertex_stack[-1] | |
101 if degree(current_vertex) == 0: | |
102 if last_vertex is not None: | |
103 yield (last_vertex, current_vertex) | |
104 last_vertex = current_vertex | |
105 vertex_stack.pop() | |
106 else: | |
107 _, next_vertex = arbitrary_element(edges(current_vertex)) | |
108 vertex_stack.append(next_vertex) | |
109 G.remove_edge(current_vertex, next_vertex) | |
110 | |
111 | |
112 def _multigraph_eulerian_circuit(G, source): | |
113 if G.is_directed(): | |
114 degree = G.out_degree | |
115 edges = G.out_edges | |
116 else: | |
117 degree = G.degree | |
118 edges = G.edges | |
119 vertex_stack = [(source, None)] | |
120 last_vertex = None | |
121 last_key = None | |
122 while vertex_stack: | |
123 current_vertex, current_key = vertex_stack[-1] | |
124 if degree(current_vertex) == 0: | |
125 if last_vertex is not None: | |
126 yield (last_vertex, current_vertex, last_key) | |
127 last_vertex, last_key = current_vertex, current_key | |
128 vertex_stack.pop() | |
129 else: | |
130 triple = arbitrary_element(edges(current_vertex, keys=True)) | |
131 _, next_vertex, next_key = triple | |
132 vertex_stack.append((next_vertex, next_key)) | |
133 G.remove_edge(current_vertex, next_vertex, next_key) | |
134 | |
135 | |
136 def eulerian_circuit(G, source=None, keys=False): | |
137 """Returns an iterator over the edges of an Eulerian circuit in `G`. | |
138 | |
139 An *Eulerian circuit* is a closed walk that includes each edge of a | |
140 graph exactly once. | |
141 | |
142 Parameters | |
143 ---------- | |
144 G : NetworkX graph | |
145 A graph, either directed or undirected. | |
146 | |
147 source : node, optional | |
148 Starting node for circuit. | |
149 | |
150 keys : bool | |
151 If False, edges generated by this function will be of the form | |
152 ``(u, v)``. Otherwise, edges will be of the form ``(u, v, k)``. | |
153 This option is ignored unless `G` is a multigraph. | |
154 | |
155 Returns | |
156 ------- | |
157 edges : iterator | |
158 An iterator over edges in the Eulerian circuit. | |
159 | |
160 Raises | |
161 ------ | |
162 NetworkXError | |
163 If the graph is not Eulerian. | |
164 | |
165 See Also | |
166 -------- | |
167 is_eulerian | |
168 | |
169 Notes | |
170 ----- | |
171 This is a linear time implementation of an algorithm adapted from [1]_. | |
172 | |
173 For general information about Euler tours, see [2]_. | |
174 | |
175 References | |
176 ---------- | |
177 .. [1] J. Edmonds, E. L. Johnson. | |
178 Matching, Euler tours and the Chinese postman. | |
179 Mathematical programming, Volume 5, Issue 1 (1973), 111-114. | |
180 .. [2] https://en.wikipedia.org/wiki/Eulerian_path | |
181 | |
182 Examples | |
183 -------- | |
184 To get an Eulerian circuit in an undirected graph:: | |
185 | |
186 >>> G = nx.complete_graph(3) | |
187 >>> list(nx.eulerian_circuit(G)) | |
188 [(0, 2), (2, 1), (1, 0)] | |
189 >>> list(nx.eulerian_circuit(G, source=1)) | |
190 [(1, 2), (2, 0), (0, 1)] | |
191 | |
192 To get the sequence of vertices in an Eulerian circuit:: | |
193 | |
194 >>> [u for u, v in nx.eulerian_circuit(G)] | |
195 [0, 2, 1] | |
196 | |
197 """ | |
198 if not is_eulerian(G): | |
199 raise nx.NetworkXError("G is not Eulerian.") | |
200 if G.is_directed(): | |
201 G = G.reverse() | |
202 else: | |
203 G = G.copy() | |
204 if source is None: | |
205 source = arbitrary_element(G) | |
206 if G.is_multigraph(): | |
207 for u, v, k in _multigraph_eulerian_circuit(G, source): | |
208 if keys: | |
209 yield u, v, k | |
210 else: | |
211 yield u, v | |
212 else: | |
213 yield from _simplegraph_eulerian_circuit(G, source) | |
214 | |
215 | |
216 def has_eulerian_path(G): | |
217 """Return True iff `G` has an Eulerian path. | |
218 | |
219 An Eulerian path is a path in a graph which uses each edge of a graph | |
220 exactly once. | |
221 | |
222 A directed graph has an Eulerian path iff: | |
223 - at most one vertex has out_degree - in_degree = 1, | |
224 - at most one vertex has in_degree - out_degree = 1, | |
225 - every other vertex has equal in_degree and out_degree, | |
226 - and all of its vertices with nonzero degree belong to a | |
227 - single connected component of the underlying undirected graph. | |
228 | |
229 An undirected graph has an Eulerian path iff: | |
230 - exactly zero or two vertices have odd degree, | |
231 - and all of its vertices with nonzero degree belong to a | |
232 - single connected component. | |
233 | |
234 Parameters | |
235 ---------- | |
236 G : NetworkX Graph | |
237 The graph to find an euler path in. | |
238 | |
239 Returns | |
240 ------- | |
241 Bool : True if G has an eulerian path. | |
242 | |
243 See Also | |
244 -------- | |
245 is_eulerian | |
246 eulerian_path | |
247 """ | |
248 if G.is_directed(): | |
249 ins = G.in_degree | |
250 outs = G.out_degree | |
251 semibalanced_ins = sum(ins(v) - outs(v) == 1 for v in G) | |
252 semibalanced_outs = sum(outs(v) - ins(v) == 1 for v in G) | |
253 return ( | |
254 semibalanced_ins <= 1 | |
255 and semibalanced_outs <= 1 | |
256 and sum(G.in_degree(v) != G.out_degree(v) for v in G) <= 2 | |
257 and nx.is_weakly_connected(G) | |
258 ) | |
259 else: | |
260 return sum(d % 2 == 1 for v, d in G.degree()) in (0, 2) and nx.is_connected(G) | |
261 | |
262 | |
263 def eulerian_path(G, source=None, keys=False): | |
264 """Return an iterator over the edges of an Eulerian path in `G`. | |
265 | |
266 Parameters | |
267 ---------- | |
268 G : NetworkX Graph | |
269 The graph in which to look for an eulerian path. | |
270 source : node or None (default: None) | |
271 The node at which to start the search. None means search over all | |
272 starting nodes. | |
273 keys : Bool (default: False) | |
274 Indicates whether to yield edge 3-tuples (u, v, edge_key). | |
275 The default yields edge 2-tuples | |
276 | |
277 Yields | |
278 ------ | |
279 Edge tuples along the eulerian path. | |
280 | |
281 Warning: If `source` provided is not the start node of an Euler path | |
282 will raise error even if an Euler Path exists. | |
283 """ | |
284 if not has_eulerian_path(G): | |
285 raise nx.NetworkXError("Graph has no Eulerian paths.") | |
286 if G.is_directed(): | |
287 G = G.reverse() | |
288 else: | |
289 G = G.copy() | |
290 if source is None: | |
291 source = _find_path_start(G) | |
292 if G.is_multigraph(): | |
293 for u, v, k in _multigraph_eulerian_circuit(G, source): | |
294 if keys: | |
295 yield u, v, k | |
296 else: | |
297 yield u, v | |
298 else: | |
299 yield from _simplegraph_eulerian_circuit(G, source) | |
300 | |
301 | |
302 @not_implemented_for("directed") | |
303 def eulerize(G): | |
304 """Transforms a graph into an Eulerian graph | |
305 | |
306 Parameters | |
307 ---------- | |
308 G : NetworkX graph | |
309 An undirected graph | |
310 | |
311 Returns | |
312 ------- | |
313 G : NetworkX multigraph | |
314 | |
315 Raises | |
316 ------ | |
317 NetworkXError | |
318 If the graph is not connected. | |
319 | |
320 See Also | |
321 -------- | |
322 is_eulerian | |
323 eulerian_circuit | |
324 | |
325 References | |
326 ---------- | |
327 .. [1] J. Edmonds, E. L. Johnson. | |
328 Matching, Euler tours and the Chinese postman. | |
329 Mathematical programming, Volume 5, Issue 1 (1973), 111-114. | |
330 [2] https://en.wikipedia.org/wiki/Eulerian_path | |
331 .. [3] http://web.math.princeton.edu/math_alive/5/Notes1.pdf | |
332 | |
333 Examples | |
334 -------- | |
335 >>> G = nx.complete_graph(10) | |
336 >>> H = nx.eulerize(G) | |
337 >>> nx.is_eulerian(H) | |
338 True | |
339 | |
340 """ | |
341 if G.order() == 0: | |
342 raise nx.NetworkXPointlessConcept("Cannot Eulerize null graph") | |
343 if not nx.is_connected(G): | |
344 raise nx.NetworkXError("G is not connected") | |
345 odd_degree_nodes = [n for n, d in G.degree() if d % 2 == 1] | |
346 G = nx.MultiGraph(G) | |
347 if len(odd_degree_nodes) == 0: | |
348 return G | |
349 | |
350 # get all shortest paths between vertices of odd degree | |
351 odd_deg_pairs_paths = [ | |
352 (m, {n: nx.shortest_path(G, source=m, target=n)}) | |
353 for m, n in combinations(odd_degree_nodes, 2) | |
354 ] | |
355 | |
356 # use inverse path lengths as edge-weights in a new graph | |
357 # store the paths in the graph for easy indexing later | |
358 Gp = nx.Graph() | |
359 for n, Ps in odd_deg_pairs_paths: | |
360 for m, P in Ps.items(): | |
361 if n != m: | |
362 Gp.add_edge(m, n, weight=1 / len(P), path=P) | |
363 | |
364 # find the minimum weight matching of edges in the weighted graph | |
365 best_matching = nx.Graph(list(nx.max_weight_matching(Gp))) | |
366 | |
367 # duplicate each edge along each path in the set of paths in Gp | |
368 for m, n in best_matching.edges(): | |
369 path = Gp[m][n]["path"] | |
370 G.add_edges_from(nx.utils.pairwise(path)) | |
371 return G |