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
GNetworkX graph

A graph, either directed or undirected.

sourcenode, optional

Starting node for circuit.

keysbool

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
edgesiterator

An iterator over edges in the Eulerian circuit.

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]