eulerian_circuit

eulerian_circuit(G, source=None)

Return the edges of an Eulerian circuit in G.

An Eulerian circuit is a path that crosses every edge in G exactly once and finishes at the starting node.

Parameters :

G : graph

A NetworkX Graph

source : node, optional

Starting node for circuit.

Returns :

edges : generator

A generator that produces edges in the Eulerian circuit.

Raises :

NetworkXError :

If the graph is not Eulerian.

See also

is_eulerian

Notes

Uses Fleury’s algorithm [R168],[R169]_

References

[R168]

(1, 2) Fleury, “Deux problemes de geometrie de situation”, Journal de mathematiques elementaires (1883), 257-261.

[R169]

http://en.wikipedia.org/wiki/Eulerian_path

Examples

>>> G=nx.complete_graph(3)
>>> list(nx.eulerian_circuit(G))
[(0, 1), (1, 2), (2, 0)]
>>> list(nx.eulerian_circuit(G,source=1)) 
[(1, 0), (0, 2), (2, 1)]
>>> [u for u,v in nx.eulerian_circuit(G)]  # nodes in circuit
[0, 1, 2]