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\$
  • 6
    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 – A. Romeu Mar 1 at 16:46
  • 4
    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? – Dannnno Mar 1 at 21:23
  • 1
    @A.Romeu: see my answer for the worst case graphs and a demonstration of the performance problem. – Gareth Rees Mar 4 at 10:55
up vote 4 down vote accepted

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:

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)
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.

  • "Given a graph that has an Eulerian cycle," – Sam Coutteau Mar 6 at 9:08
  • @SamCoutteau: See §1.1 where I discuss that point. – Gareth Rees Mar 6 at 9:20
  • 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 – Sam Coutteau Mar 6 at 15:51
  • 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 – Sam Coutteau Mar 6 at 16:26
  • this seems to fix my issues, some minor changes, like removing the self reference on the end of the list – Sam Coutteau Mar 6 at 16:57

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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