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
|
# -*- coding: utf-8 -*-
"""
Eulerian circuits and graphs.
"""
import networkx as nx
__author__ = """\n""".join(['Nima Mohammadi (nima.irt[AT]gmail.com)',
'Aric Hagberg <hagberg@lanl.gov>'])
# Copyright (C) 2010 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
__all__ = ['is_eulerian', 'eulerian_circuit']
def is_eulerian(G):
"""Return True if G is an Eulerian graph, False otherwise.
An Eulerian graph is a graph with an Eulerian circuit.
Parameters
----------
G : graph
A NetworkX Graph
Examples
--------
>>> nx.is_eulerian(nx.DiGraph({0:[3], 1:[2], 2:[3], 3:[0, 1]}))
True
>>> nx.is_eulerian(nx.complete_graph(5))
True
>>> nx.is_eulerian(nx.petersen_graph())
False
Notes
-----
This implementation requires the graph to be connected
(or strongly connected for directed graphs).
"""
if G.is_directed():
# Every node must have equal in degree and out degree
for n in G.nodes_iter():
if G.in_degree(n) != G.out_degree(n):
return False
# Must be strongly connected
if not nx.is_strongly_connected(G):
return False
else:
# An undirected Eulerian graph has no vertices of odd degrees
for v,d in G.degree_iter():
if d % 2 != 0:
return False
# Must be connected
if not nx.is_connected(G):
return False
return True
def eulerian_circuit(G, source=None):
"""Return the edges of an Eulerian circuit in G.
An Eulerian circuit is a path that crosses every edge in G exactly once
and finishes at the starting node.
Parameters
----------
G : NetworkX Graph or DiGraph
A directed or undirected graph
source : node, optional
Starting node for circuit.
Returns
-------
edges : generator
A generator that produces edges in the Eulerian circuit.
Raises
------
NetworkXError
If the graph is not Eulerian.
See Also
--------
is_eulerian
Notes
-----
Linear time algorithm, adapted from [1]_.
General information about Euler tours [2]_.
References
----------
.. [1] J. Edmonds, E. L. Johnson.
Matching, Euler tours and the Chinese postman.
Mathematical programming, Volume 5, Issue 1 (1973), 111-114.
.. [2] http://en.wikipedia.org/wiki/Eulerian_path
Examples
--------
>>> G=nx.complete_graph(3)
>>> list(nx.eulerian_circuit(G))
[(0, 2), (2, 1), (1, 0)]
>>> list(nx.eulerian_circuit(G,source=1))
[(1, 2), (2, 0), (0, 1)]
>>> [u for u,v in nx.eulerian_circuit(G)] # nodes in circuit
[0, 2, 1]
"""
from operator import itemgetter
if not is_eulerian(G):
raise nx.NetworkXError("G is not Eulerian.")
g = G.__class__(G) # copy graph structure (not attributes)
# set starting node
if source is None:
v = next(g.nodes_iter())
else:
v = source
if g.is_directed():
degree = g.in_degree
edges = g.in_edges_iter
get_vertex = itemgetter(0)
else:
degree = g.degree
edges = g.edges_iter
get_vertex = itemgetter(1)
vertex_stack = [v]
last_vertex = None
while vertex_stack:
current_vertex = vertex_stack[-1]
if degree(current_vertex) == 0:
if last_vertex is not None:
yield (last_vertex, current_vertex)
last_vertex = current_vertex
vertex_stack.pop()
else:
random_edge = next(edges(current_vertex))
vertex_stack.append(get_vertex(random_edge))
g.remove_edge(*random_edge)
|
