eulerian_circuit(G, source=None, keys=False)¶
Returns an iterator over the edges of an Eulerian circuit in
An Eulerian circuit is a closed walk that includes each edge of a graph exactly once.
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
Gis a multigraph.
edges – An iterator over edges in the Eulerian circuit.
- Return type
NetworkXError – If the graph is not Eulerian.
This is a linear time implementation of an algorithm adapted from 1.
For general information about Euler tours, see 2.
J. Edmonds, E. L. Johnson. Matching, Euler tours and the Chinese postman. Mathematical programming, Volume 5, Issue 1 (1973), 111-114.
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]