Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# Source code for networkx.algorithms.euler

# -*- coding: utf-8 -*-
"""
Eulerian circuits and graphs.
"""
import networkx as nx

'Aric Hagberg <hagberg@lanl.gov>'])
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>

__all__ = ['is_eulerian', 'eulerian_circuit']

[docs]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:, 1:, 2:, 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

[docs]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.

--------
is_eulerian

Notes
-----
Linear time algorithm, adapted from _.
General information about Euler tours _.

References
----------
..  J. Edmonds, E. L. Johnson.
Matching, Euler tours and the Chinese postman.
Mathematical programming, Volume 5, Issue 1 (1973), 111-114.
..  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)