Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/euler.py @ 1:56ad4e20f292 draft

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