Warning

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

eulerian_circuit

eulerian_circuit(G, source=None)[source]

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 [R245]. General information about Euler tours [R246].

References

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