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.

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]