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 -*-
#
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#
# Authors:
#   Aric Hagberg <hagberg@lanl.gov>
#   Mike Trenfield <william.trenfield@utsouthwestern.edu>
"""
Eulerian circuits and graphs.
"""
from itertools import combinations

import networkx as nx
from ..utils import arbitrary_element, not_implemented_for

__all__ = ['is_eulerian', 'eulerian_circuit', 'eulerize']

[docs]def is_eulerian(G):
"""Returns True if and only if G is Eulerian.

A graph is *Eulerian* if it has an Eulerian circuit. An *Eulerian
circuit* is a closed walk that includes each edge of a graph exactly
once.

Parameters
----------
G : NetworkX graph
A graph, either directed or undirected.

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
-----
If the graph is not connected (or not strongly connected, for
directed graphs), this function returns False.

"""
if G.is_directed():
# Every node must have equal in degree and out degree and the
# graph must be strongly connected
return (all(G.in_degree(n) == G.out_degree(n) for n in G) and
nx.is_strongly_connected(G))
# An undirected Eulerian graph has no vertices of odd degree and
# must be connected.
return all(d % 2 == 0 for v, d in G.degree()) and nx.is_connected(G)

def _simplegraph_eulerian_circuit(G, source):
if G.is_directed():
degree = G.out_degree
edges = G.out_edges
else:
degree = G.degree
edges = G.edges
vertex_stack = [source]
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:
_, next_vertex = arbitrary_element(edges(current_vertex))
vertex_stack.append(next_vertex)
G.remove_edge(current_vertex, next_vertex)

def _multigraph_eulerian_circuit(G, source):
if G.is_directed():
degree = G.out_degree
edges = G.out_edges
else:
degree = G.degree
edges = G.edges
vertex_stack = [(source, None)]
last_vertex = None
last_key = None
while vertex_stack:
current_vertex, current_key = vertex_stack[-1]
if degree(current_vertex) == 0:
if last_vertex is not None:
yield (last_vertex, current_vertex, last_key)
last_vertex, last_key = current_vertex, current_key
vertex_stack.pop()
else:
_, next_vertex, next_key = arbitrary_element(edges(current_vertex, keys=True))
vertex_stack.append((next_vertex, next_key))
G.remove_edge(current_vertex, next_vertex, next_key)

[docs]def eulerian_circuit(G, source=None, keys=False):
"""Returns an iterator over the edges of an Eulerian circuit in G.

An *Eulerian circuit* is a closed walk that includes each edge of a
graph exactly once.

Parameters
----------
G : NetworkX graph
A graph, either directed or undirected.

source : node, optional
Starting node for circuit.

keys : bool
If False, edges generated by this function will be of the form
(u, v). Otherwise, edges will be of the form (u, v, k).
This option is ignored unless G is a multigraph.

Returns
-------
edges : iterator
An iterator over edges in the Eulerian circuit.

Raises
------
NetworkXError
If the graph is not Eulerian.

--------
is_eulerian

Notes
-----
This is a linear time implementation of an algorithm adapted from _.

For general information about Euler tours, see _.

References
----------
..  J. Edmonds, E. L. Johnson.
Matching, Euler tours and the Chinese postman.
Mathematical programming, Volume 5, Issue 1 (1973), 111-114.
..  https://en.wikipedia.org/wiki/Eulerian_path

Examples
--------
To get an Eulerian circuit in an undirected graph::

>>> 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)]

To get the sequence of vertices in an Eulerian circuit::

>>> [u for u, v in nx.eulerian_circuit(G)]
[0, 2, 1]

"""
if not is_eulerian(G):
raise nx.NetworkXError("G is not Eulerian.")
if G.is_directed():
G = G.reverse()
else:
G = G.copy()
if source is None:
source = arbitrary_element(G)
if G.is_multigraph():
for u, v, k in _multigraph_eulerian_circuit(G, source):
if keys:
yield u, v, k
else:
yield u, v
else:
for u, v in _simplegraph_eulerian_circuit(G, source):
yield u, v

[docs]@not_implemented_for('directed')
def eulerize(G):
"""
Transforms a graph into an Eulerian graph

Parameters
----------
G : NetworkX graph
An undirected graph

Returns
-------
G : NetworkX multigraph

Raises
------
NetworkXError
If the graph is not connected.

--------
is_eulerian, eulerian_circuit

References
----------
..  J. Edmonds, E. L. Johnson.
Matching, Euler tours and the Chinese postman.
Mathematical programming, Volume 5, Issue 1 (1973), 111-114.
 https://en.wikipedia.org/wiki/Eulerian_path
..  http://web.math.princeton.edu/math_alive/5/Notes1.pdf

Examples
--------
>>> G = nx.complete_graph(10)
>>> H = nx.eulerize(G)
>>> nx.is_eulerian(H)
True

"""
if G.order() == 0:
raise nx.NetworkXPointlessConcept("Cannot Eulerize null graph")
if not nx.is_connected(G):
raise nx.NetworkXError("G is not connected")
odd_degree_nodes = [n for n, d in G.degree() if d % 2 == 1]
G = nx.MultiGraph(G)
if len(odd_degree_nodes) == 0:
return G

# get all shortest paths between vertices of odd degree
odd_deg_pairs_paths = [(m,
{n: nx.shortest_path(G, source=m, target=n)}
)
for m, n in combinations(odd_degree_nodes, 2)]

# use inverse path lengths as edge-weights in a new graph
# store the paths in the graph for easy indexing later
Gp = nx.Graph()
for n, Ps in odd_deg_pairs_paths:
for m, P in Ps.items():
if n != m: