A cycle that traverses each edge of a graph exactly once is called an Eulerian cycle, and we say that a graph containing such a cycle is Eulerian. The following algorithm constructs an Eulerian cycle in an arbitrary directed graph $$\mathcal{G}$$.

EulerianCycle(G)
    form a cycle c by randomly walking in graph G (don't visit the same edge twice!)
    while there are unexplored edges in graph G
        select a node n in cycle c with still unexplored edges
        form cycle c' by traversing cycle c (starting at node n) and then randomly walking
        c ← c'
    return c

Assignment

Write a function eulerian_cycle that takes the location of a text file containing the description of an Eulerian directed graph $$\mathcal{G}$$ in the form of an adjacency list. Each line of the file contains the label (an integer) of a starting node, a space, the characters ->, another space and a comma-separated list containing the lexicographically sorted labels (integers) of all ending nodes connected to that starting node. The function must return an Eulerian cycle in $$\mathcal{G}$$, represented as a tuple of node labels.

Example

In the following interactive session, we assume the text file data01.txt¹ to be located in the current directory.

>>> eulerian_cycle('data01.txt')
(0, 3, 2, 6, 8, 7, 9, 6, 5, 4, 2, 1, 0)