Given a graph that has an Eulerian cycle, write a function which returns the cycle in tuple form.

I came up with following solution for this problem and am stuck trying to make it faster. Do you have any tips?

def eulerian_cycle_1(data):
    graph, edges_amount = get_graph(data) #graph:: {source:[destination]}
    cycle = deque()

    cur = 0
    while edges_amount > 0:
        choices = graph[cur]

        while choices:
            edges_amount -= 1
            cur = choices.pop()
            choices = graph.get(cur, None)

        if edges_amount == 0:

        rotate = 0
        for cur in cycle:
            if graph[cur]:
            rotate += 1



    return tuple(cycle)



  • 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\$
  • 6
    \$\begingroup\$ Hey Sam, will be good if you append some tests where you are profiling the code, and see where the bottlenecks are, to know which kind of delays you are experiencing \$\endgroup\$
    – A. Romeu
    Commented Mar 1, 2018 at 16:46
  • 4
    \$\begingroup\$ Can you please provide some sample input and output? You mention a function, get_graph, that isn't present - can you include that as well please? \$\endgroup\$ Commented Mar 1, 2018 at 21:23
  • 1
    \$\begingroup\$ @A.Romeu: see my answer for the worst case graphs and a demonstration of the performance problem. \$\endgroup\$ Commented Mar 4, 2018 at 10:55

1 Answer 1


1. Review

  1. The code returns the wrong result when the graph has no Eulerian cycle. For example, if we give it the graph {0:[1], 1:[]} then the code returns the tuple (0, 0), which does not correspond to any legal path in the graph. It would be better to raise an exception if the graph has no Eulerian cycle.

    I know that the problem description says that the graph has an Eulerian cycle, but in real life data is sometimes incorrect and it is a good idea to write code so that it is robust.

  2. Similarly, the code goes into an infinite loop if the graph is disconnected:

    >>> eulerian_cycle_1({0:[0], 1:[1]}, 2)
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
      File "cr188627.py", line 21, in eulerian_cycle_1
        if graph[cur]:

    It would be more robust to raise an exception in this case.

  3. The code doesn't work if the graph doesn't have a node 0:

    >>> eulerian_cycle_1({1:[1]}, 1)
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
      File "cr188627.py", line 8, in eulerian_cycle_1
        choices = graph[cur]
    KeyError: 0

    It would be more robust to pick a starting node from the graph.

  4. The number of edges can be easily computed from the graph like this:

    sum(map(len, graph.values()))

    so it would simplify the interface if the code only required the graph, and computed the number of edges itself.

  5. But in fact there is no need to know the number of edges: you can exit the main loop if the search along the cycle for a node with an edge fails.

2. Performance

The problem with the performance is that whenever it reaches a point where the cycle cannot be extended, the code searches along the cycle to try to find a node which still has edges. In the worst case, a graph with \$n\$ nodes and \$O(n)\$ edges might have \$Θ(n)\$ points where the cycle cannot be extended, and at each of these points the code will have to search \$Θ(n)\$ nodes in the cycle. In this case the overall runtime will be \$Θ(n^2)\$, that is quadratic.

The worst case arises in graphs like this:

Graph with five nodes. Each node links to the next node and the previous node, except for node 0, which links to 1 and itself, and node 4, which links to 3 and itself

and we can build these graphs systematically if we define get_graph like this:

def get_graph(n):
    "Return a worst-case graph with n nodes and 2n edges."
    return {i:[min(i + 1, n - 1), max(i - 1, 0)] for i in range(n)}, 2 * n

Now, if we increase the size of the graph by 10 times, it takes 100 times as long to find an Eulerian cycle:

>>> from timeit import timeit
>>> timeit(lambda:eulerian_cycle_1(10**3), number=1)
>>> timeit(lambda:eulerian_cycle_1(10**4), number=1)

To make the runtime linear in the number of edges, we have to avoid traversing or rotating the whole cycle, except possibly once at the end. There are two approaches we might take:

  1. Represent the cycle as a linked list (not a deque) so that we can efficiently insert new items at any point, without having to rotate.

  2. Don't try to join the cycles as we go along, but instead keep a collection of cycles and stitch them together at the end using a depth-first search.

I'll show here how to implement the first approach (see this answer for how to implement the second approach).

Python doesn't provide a linked list implementation, but we can easily make one:

class Link:
    "A link in a linked list."
    def __init__(self, node):
        self.node = node
        self.next = self

    def insert(self, link):
        "Insert link after self in the linked list and return link."
        link.next = self.next
        self.next = link
        return link

Now it's just a matter of keeping track of the Link objects corresponding to the nodes in the graph that still have edges, so that we can efficiently find the place to continue extending the cycle.

def eulerian_cycle_2(graph):
    """Return an Eulerian cycle in graph, if there is one, as a list of
    nodes. If there are no Eulerian cycles, raise ValueError.

    # Take a copy of the graph so that we can modify it.
    graph = {k:v[:] for k, v in graph.items()}

    # Start at any node in the graph that has an edge.
    node = next(node for node, neighbours in graph.items() if neighbours)
    choices = graph[node]
    start = cur = Link(node)

    # Map from node we've visited (that still has edges) to a link for
    # that node in the linked list.
    visited = {}

    while True:
        # Extend current cycle until no more edges can be followed.
        cycle_start = node
        while choices:
            visited[node] = cur
            node = choices.pop()
            choices = graph[node]
            cur = cur.insert(Link(node))
        if node != cycle_start:
            raise ValueError("graph has no Eulerian cycle")

        # Find a visited node which still has edges, if any.
        while visited:
            node, cur = visited.popitem()
            choices = graph[node]
            if choices:

    if any(graph.values()):
        raise ValueError("graph has no Eulerian cycle")

    # Reconstruct cycle by following linked list.
    cycle = []
    cur = start
    while True:
        cur = cur.next
        if cur == start:
    return cycle

We should check that the performance is linear in the number of edges. Here you can see that when the graph is 10 times as big, the runtime is roughly 10 times as long, as required:

>>> timeit(lambda:eulerian_cycle_2(get_graph(10**3)[0]), number=1)
>>> timeit(lambda:eulerian_cycle_2(get_graph(10**4)[0]), number=1)
>>> timeit(lambda:eulerian_cycle_2(get_graph(10**5)[0]), number=1)
>>> timeit(lambda:eulerian_cycle_2(get_graph(10**6)[0]), number=1)

For comparison, by extrapolating the timings from earlier in this answer, we would have expected eulerian_cycle_1 to take about 24 hours to find a cycle in the worst-case graph with \$10^6\$ notes.

  • \$\begingroup\$ "Given a graph that has an Eulerian cycle," \$\endgroup\$ Commented Mar 6, 2018 at 9:08
  • \$\begingroup\$ @SamCoutteau: See §1.1 where I discuss that point. \$\endgroup\$ Commented Mar 6, 2018 at 9:20
  • \$\begingroup\$ This graph, produces an output of (0, ...., 0, 0, ..., 52) instead of (0, ..., 52, 0, ..., 0) any ideas why?, have been trying to figure out what's happening here \$\endgroup\$ Commented Mar 6, 2018 at 15:51
  • \$\begingroup\$ That's not the issue here there is no edge 0 -> 0, your code normally adds the first node on the end except in this case. the 0,0 is not the only error it also has (...,23,23,...) whilst there is no edge 23 -> 23 \$\endgroup\$ Commented Mar 6, 2018 at 16:26
  • \$\begingroup\$ this seems to fix my issues, some minor changes, like removing the self reference on the end of the list \$\endgroup\$ Commented Mar 6, 2018 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.