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 unlessG
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
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]