Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Eulerian circuits and graphs.
3"""
5from itertools import combinations
7import networkx as nx
9from ..utils import arbitrary_element, not_implemented_for
11__all__ = [
12 "is_eulerian",
13 "eulerian_circuit",
14 "eulerize",
15 "is_semieulerian",
16 "has_eulerian_path",
17 "eulerian_path",
18]
21@nx._dispatchable
22def is_eulerian(G):
23 """Returns True if and only if `G` is Eulerian.
25 A graph is *Eulerian* if it has an Eulerian circuit. An *Eulerian
26 circuit* is a closed walk that includes each edge of a graph exactly
27 once.
29 Graphs with isolated vertices (i.e. vertices with zero degree) are not
30 considered to have Eulerian circuits. Therefore, if the graph is not
31 connected (or not strongly connected, for directed graphs), this function
32 returns False.
34 Parameters
35 ----------
36 G : NetworkX graph
37 A graph, either directed or undirected.
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
48 If you prefer to allow graphs with isolated vertices to have Eulerian circuits,
49 you can first remove such vertices and then call `is_eulerian` as below example shows.
51 >>> G = nx.Graph([(0, 1), (1, 2), (0, 2)])
52 >>> G.add_node(3)
53 >>> nx.is_eulerian(G)
54 False
56 >>> G.remove_nodes_from(list(nx.isolates(G)))
57 >>> nx.is_eulerian(G)
58 True
61 """
62 if G.is_directed():
63 # Every node must have equal in degree and out degree and the
64 # graph must be strongly connected
65 return all(
66 G.in_degree(n) == G.out_degree(n) for n in G
67 ) and nx.is_strongly_connected(G)
68 # An undirected Eulerian graph has no vertices of odd degree and
69 # must be connected.
70 return all(d % 2 == 0 for v, d in G.degree()) and nx.is_connected(G)
73@nx._dispatchable
74def is_semieulerian(G):
75 """Return True iff `G` is semi-Eulerian.
77 G is semi-Eulerian if it has an Eulerian path but no Eulerian circuit.
79 See Also
80 --------
81 has_eulerian_path
82 is_eulerian
83 """
84 return has_eulerian_path(G) and not is_eulerian(G)
87def _find_path_start(G):
88 """Return a suitable starting vertex for an Eulerian path.
90 If no path exists, return None.
91 """
92 if not has_eulerian_path(G):
93 return None
95 if is_eulerian(G):
96 return arbitrary_element(G)
98 if G.is_directed():
99 v1, v2 = (v for v in G if G.in_degree(v) != G.out_degree(v))
100 # Determines which is the 'start' node (as opposed to the 'end')
101 if G.out_degree(v1) > G.in_degree(v1):
102 return v1
103 else:
104 return v2
106 else:
107 # In an undirected graph randomly choose one of the possibilities
108 start = [v for v in G if G.degree(v) % 2 != 0][0]
109 return start
112def _simplegraph_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]
120 last_vertex = None
121 while vertex_stack:
122 current_vertex = vertex_stack[-1]
123 if degree(current_vertex) == 0:
124 if last_vertex is not None:
125 yield (last_vertex, current_vertex)
126 last_vertex = current_vertex
127 vertex_stack.pop()
128 else:
129 _, next_vertex = arbitrary_element(edges(current_vertex))
130 vertex_stack.append(next_vertex)
131 G.remove_edge(current_vertex, next_vertex)
134def _multigraph_eulerian_circuit(G, source):
135 if G.is_directed():
136 degree = G.out_degree
137 edges = G.out_edges
138 else:
139 degree = G.degree
140 edges = G.edges
141 vertex_stack = [(source, None)]
142 last_vertex = None
143 last_key = None
144 while vertex_stack:
145 current_vertex, current_key = vertex_stack[-1]
146 if degree(current_vertex) == 0:
147 if last_vertex is not None:
148 yield (last_vertex, current_vertex, last_key)
149 last_vertex, last_key = current_vertex, current_key
150 vertex_stack.pop()
151 else:
152 triple = arbitrary_element(edges(current_vertex, keys=True))
153 _, next_vertex, next_key = triple
154 vertex_stack.append((next_vertex, next_key))
155 G.remove_edge(current_vertex, next_vertex, next_key)
158@nx._dispatchable
159def eulerian_circuit(G, source=None, keys=False):
160 """Returns an iterator over the edges of an Eulerian circuit in `G`.
162 An *Eulerian circuit* is a closed walk that includes each edge of a
163 graph exactly once.
165 Parameters
166 ----------
167 G : NetworkX graph
168 A graph, either directed or undirected.
170 source : node, optional
171 Starting node for circuit.
173 keys : bool
174 If False, edges generated by this function will be of the form
175 ``(u, v)``. Otherwise, edges will be of the form ``(u, v, k)``.
176 This option is ignored unless `G` is a multigraph.
178 Returns
179 -------
180 edges : iterator
181 An iterator over edges in the Eulerian circuit.
183 Raises
184 ------
185 NetworkXError
186 If the graph is not Eulerian.
188 See Also
189 --------
190 is_eulerian
192 Notes
193 -----
194 This is a linear time implementation of an algorithm adapted from [1]_.
196 For general information about Euler tours, see [2]_.
198 References
199 ----------
200 .. [1] J. Edmonds, E. L. Johnson.
201 Matching, Euler tours and the Chinese postman.
202 Mathematical programming, Volume 5, Issue 1 (1973), 111-114.
203 .. [2] https://en.wikipedia.org/wiki/Eulerian_path
205 Examples
206 --------
207 To get an Eulerian circuit in an undirected graph::
209 >>> G = nx.complete_graph(3)
210 >>> list(nx.eulerian_circuit(G))
211 [(0, 2), (2, 1), (1, 0)]
212 >>> list(nx.eulerian_circuit(G, source=1))
213 [(1, 2), (2, 0), (0, 1)]
215 To get the sequence of vertices in an Eulerian circuit::
217 >>> [u for u, v in nx.eulerian_circuit(G)]
218 [0, 2, 1]
220 """
221 if not is_eulerian(G):
222 raise nx.NetworkXError("G is not Eulerian.")
223 if G.is_directed():
224 G = G.reverse()
225 else:
226 G = G.copy()
227 if source is None:
228 source = arbitrary_element(G)
229 if G.is_multigraph():
230 for u, v, k in _multigraph_eulerian_circuit(G, source):
231 if keys:
232 yield u, v, k
233 else:
234 yield u, v
235 else:
236 yield from _simplegraph_eulerian_circuit(G, source)
239@nx._dispatchable
240def has_eulerian_path(G, source=None):
241 """Return True iff `G` has an Eulerian path.
243 An Eulerian path is a path in a graph which uses each edge of a graph
244 exactly once. If `source` is specified, then this function checks
245 whether an Eulerian path that starts at node `source` exists.
247 A directed graph has an Eulerian path iff:
248 - at most one vertex has out_degree - in_degree = 1,
249 - at most one vertex has in_degree - out_degree = 1,
250 - every other vertex has equal in_degree and out_degree,
251 - and all of its vertices belong to a single connected
252 component of the underlying undirected graph.
254 If `source` is not None, an Eulerian path starting at `source` exists if no
255 other node has out_degree - in_degree = 1. This is equivalent to either
256 there exists an Eulerian circuit or `source` has out_degree - in_degree = 1
257 and the conditions above hold.
259 An undirected graph has an Eulerian path iff:
260 - exactly zero or two vertices have odd degree,
261 - and all of its vertices belong to a single connected component.
263 If `source` is not None, an Eulerian path starting at `source` exists if
264 either there exists an Eulerian circuit or `source` has an odd degree and the
265 conditions above hold.
267 Graphs with isolated vertices (i.e. vertices with zero degree) are not considered
268 to have an Eulerian path. Therefore, if the graph is not connected (or not strongly
269 connected, for directed graphs), this function returns False.
271 Parameters
272 ----------
273 G : NetworkX Graph
274 The graph to find an euler path in.
276 source : node, optional
277 Starting node for path.
279 Returns
280 -------
281 Bool : True if G has an Eulerian path.
283 Examples
284 --------
285 If you prefer to allow graphs with isolated vertices to have Eulerian path,
286 you can first remove such vertices and then call `has_eulerian_path` as below example shows.
288 >>> G = nx.Graph([(0, 1), (1, 2), (0, 2)])
289 >>> G.add_node(3)
290 >>> nx.has_eulerian_path(G)
291 False
293 >>> G.remove_nodes_from(list(nx.isolates(G)))
294 >>> nx.has_eulerian_path(G)
295 True
297 See Also
298 --------
299 is_eulerian
300 eulerian_path
301 """
302 if nx.is_eulerian(G):
303 return True
305 if G.is_directed():
306 ins = G.in_degree
307 outs = G.out_degree
308 # Since we know it is not eulerian, outs - ins must be 1 for source
309 if source is not None and outs[source] - ins[source] != 1:
310 return False
312 unbalanced_ins = 0
313 unbalanced_outs = 0
314 for v in G:
315 if ins[v] - outs[v] == 1:
316 unbalanced_ins += 1
317 elif outs[v] - ins[v] == 1:
318 unbalanced_outs += 1
319 elif ins[v] != outs[v]:
320 return False
322 return (
323 unbalanced_ins <= 1 and unbalanced_outs <= 1 and nx.is_weakly_connected(G)
324 )
325 else:
326 # We know it is not eulerian, so degree of source must be odd.
327 if source is not None and G.degree[source] % 2 != 1:
328 return False
330 # Sum is 2 since we know it is not eulerian (which implies sum is 0)
331 return sum(d % 2 == 1 for v, d in G.degree()) == 2 and nx.is_connected(G)
334@nx._dispatchable
335def eulerian_path(G, source=None, keys=False):
336 """Return an iterator over the edges of an Eulerian path in `G`.
338 Parameters
339 ----------
340 G : NetworkX Graph
341 The graph in which to look for an eulerian path.
342 source : node or None (default: None)
343 The node at which to start the search. None means search over all
344 starting nodes.
345 keys : Bool (default: False)
346 Indicates whether to yield edge 3-tuples (u, v, edge_key).
347 The default yields edge 2-tuples
349 Yields
350 ------
351 Edge tuples along the eulerian path.
353 Warning: If `source` provided is not the start node of an Euler path
354 will raise error even if an Euler Path exists.
355 """
356 if not has_eulerian_path(G, source):
357 raise nx.NetworkXError("Graph has no Eulerian paths.")
358 if G.is_directed():
359 G = G.reverse()
360 if source is None or nx.is_eulerian(G) is False:
361 source = _find_path_start(G)
362 if G.is_multigraph():
363 for u, v, k in _multigraph_eulerian_circuit(G, source):
364 if keys:
365 yield u, v, k
366 else:
367 yield u, v
368 else:
369 yield from _simplegraph_eulerian_circuit(G, source)
370 else:
371 G = G.copy()
372 if source is None:
373 source = _find_path_start(G)
374 if G.is_multigraph():
375 if keys:
376 yield from reversed(
377 [(v, u, k) for u, v, k in _multigraph_eulerian_circuit(G, source)]
378 )
379 else:
380 yield from reversed(
381 [(v, u) for u, v, k in _multigraph_eulerian_circuit(G, source)]
382 )
383 else:
384 yield from reversed(
385 [(v, u) for u, v in _simplegraph_eulerian_circuit(G, source)]
386 )
389@not_implemented_for("directed")
390@nx._dispatchable(returns_graph=True)
391def eulerize(G):
392 """Transforms a graph into an Eulerian graph.
394 If `G` is Eulerian the result is `G` as a MultiGraph, otherwise the result is a smallest
395 (in terms of the number of edges) multigraph whose underlying simple graph is `G`.
397 Parameters
398 ----------
399 G : NetworkX graph
400 An undirected graph
402 Returns
403 -------
404 G : NetworkX multigraph
406 Raises
407 ------
408 NetworkXError
409 If the graph is not connected.
411 See Also
412 --------
413 is_eulerian
414 eulerian_circuit
416 References
417 ----------
418 .. [1] J. Edmonds, E. L. Johnson.
419 Matching, Euler tours and the Chinese postman.
420 Mathematical programming, Volume 5, Issue 1 (1973), 111-114.
421 .. [2] https://en.wikipedia.org/wiki/Eulerian_path
422 .. [3] http://web.math.princeton.edu/math_alive/5/Notes1.pdf
424 Examples
425 --------
426 >>> G = nx.complete_graph(10)
427 >>> H = nx.eulerize(G)
428 >>> nx.is_eulerian(H)
429 True
431 """
432 if G.order() == 0:
433 raise nx.NetworkXPointlessConcept("Cannot Eulerize null graph")
434 if not nx.is_connected(G):
435 raise nx.NetworkXError("G is not connected")
436 odd_degree_nodes = [n for n, d in G.degree() if d % 2 == 1]
437 G = nx.MultiGraph(G)
438 if len(odd_degree_nodes) == 0:
439 return G
441 # get all shortest paths between vertices of odd degree
442 odd_deg_pairs_paths = [
443 (m, {n: nx.shortest_path(G, source=m, target=n)})
444 for m, n in combinations(odd_degree_nodes, 2)
445 ]
447 # use the number of vertices in a graph + 1 as an upper bound on
448 # the maximum length of a path in G
449 upper_bound_on_max_path_length = len(G) + 1
451 # use "len(G) + 1 - len(P)",
452 # where P is a shortest path between vertices n and m,
453 # as edge-weights in a new graph
454 # store the paths in the graph for easy indexing later
455 Gp = nx.Graph()
456 for n, Ps in odd_deg_pairs_paths:
457 for m, P in Ps.items():
458 if n != m:
459 Gp.add_edge(
460 m, n, weight=upper_bound_on_max_path_length - len(P), path=P
461 )
463 # find the minimum weight matching of edges in the weighted graph
464 best_matching = nx.Graph(list(nx.max_weight_matching(Gp)))
466 # duplicate each edge along each path in the set of paths in Gp
467 for m, n in best_matching.edges():
468 path = Gp[m][n]["path"]
469 G.add_edges_from(nx.utils.pairwise(path))
470 return G