Warning

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

networkx.algorithms.euler.eulerian_circuit

eulerian_circuit(G, source=None, keys=False)[source]

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 – An iterator over edges in the Eulerian circuit.

Return type:

iterator

Raises:

NetworkXError – If the graph is not Eulerian.

See also

is_eulerian()

Notes

This is a linear time implementation of an algorithm adapted from [1].

For general information about Euler tours, see [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]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]