Finding an Eulerian cycle in a graph

Question

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:
            cycle.append(cur)
            edges_amount -= 1
            cur = choices.pop()
            choices = graph.get(cur, None)

        if edges_amount == 0:
            break

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

        cycle.rotate(-rotate)

    cycle.rotate(-cycle.index(0))
    cycle.append(0)


    return tuple(cycle)

Pseudocode

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\$

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)
   ^C
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
     File "cr188627.py", line 21, in eulerian_cycle_1
       if graph[cur]:
   KeyboardInterrupt
   

   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:

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)
0.08308156998828053
>>> timeit(lambda:eulerian_cycle_1(10**4), number=1)
8.778133336978499

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:
                break
        else:
            break

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

    # Reconstruct cycle by following linked list.
    cycle = []
    cur = start
    while True:
        cycle.append(cur.node)
        cur = cur.next
        if cur == start:
            break
    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)
0.0049093629932031035
>>> timeit(lambda:eulerian_cycle_2(get_graph(10**4)[0]), number=1)
0.045048179978039116
>>> timeit(lambda:eulerian_cycle_2(get_graph(10**5)[0]), number=1)
0.42420267598936334
>>> timeit(lambda:eulerian_cycle_2(get_graph(10**6)[0]), number=1)
4.303449199011084

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.