Check if a directed graph contains a cycle

Question

I am trying to optimize execution time of this function which detects cycle in a directed graph:

g = {
    1: [2, 3],
    2: [3]
}

cur_path = set()
def isCyclic(g, vertex):
    global cur_path
    cur_path.add(vertex)
    for neighboor in g.get(vertex, []):
        if neighboor in cur_path:
            return True
        else:
            if neighboor in g and isCyclic(g, neighboor):
                return True
    cur_path.remove(vertex)
    return False

I look for redundant calls, or information that I can store somewhere to improve the execution time (which is O(E), right?).

Answer 1

1. Review

1. There's no docstring. What does the function do? What arguments should I pass? What does it return?

2. This is the kind of function that would make an ideal candidate for a doctest or two.

3. The function does not actually determine if a graph contains a cycle. It determines if the graph contains a cycle starting at a given vertex. To detect a cycle, it would be necessary to call the function for each vertex in the graph.

4. The function uses a global variable for state. This makes it impossible to use the function in a multi-threaded program. It also makes it difficult to debug, because whenever anything goes wrong, you have to reset cur_path to the empty set before you can re-run the function. It would be better if all state were encapsulated inside the function.

5. else: if ...: can be abbreviated to elif ...:.

6. In British English the word is spelled "neighbour", and in American English it's spelled "neighbor".

7. It's better to use the empty tuple () as the default value if vertex is not found in g, instead of the empty list []. That's because the empty tuple is a singleton: each time () is evaluated you get the same object. But each time you evaluate [] a new empty list has to be allocated.

8. Testing neighbour in g is unnecessary since you already handle the case where vertex is not in g.

2. Revised code

Applying all the comments above:

def cyclic(g):
    """Return True if the directed graph g has a cycle.
    g must be represented as a dictionary mapping vertices to
    iterables of neighbouring vertices. For example:

    >>> cyclic({1: (2,), 2: (3,), 3: (1,)})
    True
    >>> cyclic({1: (2,), 2: (3,), 3: (4,)})
    False

    """
    path = set()

    def visit(vertex):
        path.add(vertex)
        for neighbour in g.get(vertex, ()):
            if neighbour in path or visit(neighbour):
                return True
        path.remove(vertex)
        return False

    return any(visit(v) for v in g)

3. Analysis

The function follows all simple paths in the graph, stopping when it encounters a cycle. Unfortunately, a graph may have exponentially many simple paths without containing any cycles, so the runtime is exponential in the size of the input.

For example, this function constructs a graph with exponentially many simple paths:

def test_graph(n):
    """Return an acyclic graph containing 2**n simple paths."""
    g = dict()
    for i in range(n):
        g[3 * i] = (3 * i + 1, 3 * i + 2)
        g[3 * i + 1] = g[3 * i + 2] = (3 * (i + 1),)
    return g

The graphs it constructs look like this:

Experimentally we can check that the runtime is exponential:

>>> for i in range(10, 20):
...     print(i, timeit(lambda:cyclic(test_graph(i)), number=1))
... 
10 0.017517157015390694
11 0.03172751097008586
12 0.06926556502003223
13 0.1300737849669531
14 0.25352559401653707
15 0.5073735360056162
16 0.9933696809457615
17 2.004867063020356
18 3.9877060829894617
19 7.927054518950172

You can see that each increment of i doubles the runtime.

4. An efficient algorithm

To make the algorithm efficient, we must make sure not to visit any vertex more than once, which we can do by keeping a separate set of vertices that have been visited so far. For example:

def cyclic(g):
    """Return True if the directed graph g has a cycle.
    g must be represented as a dictionary mapping vertices to
    iterables of neighbouring vertices. For example:

    >>> cyclic({1: (2,), 2: (3,), 3: (1,)})
    True
    >>> cyclic({1: (2,), 2: (3,), 3: (4,)})
    False

    """
    path = set()
    visited = set()

    def visit(vertex):
        if vertex in visited:
            return False
        visited.add(vertex)
        path.add(vertex)
        for neighbour in g.get(vertex, ()):
            if neighbour in path or visit(neighbour):
                return True
        path.remove(vertex)
        return False

    return any(visit(v) for v in g)

This visits each vertex at most once, and considers each edge at most once, so its runtime is \$ O(V + E) \$.

Experimentally we can check that the runtime is roughly linear in the size of the graph:

>>> for i in range(10, 20):
...     print(i, timeit(lambda:cyclic(test_graph(i)), number=1))
...
10 0.00017403007950633764
11 0.00014279899187386036
12 0.00015402096323668957
13 0.00016507902182638645
14 0.00017680192831903696
15 0.00019660103134810925
16 0.00020132900681346655
17 0.0002140760188922286
18 0.00022624700795859098
19 0.00023716699797660112

5. Avoiding the recursion limit

The implementation uses recursion to search the graph. This means that it uses as many stack frames as there are nodes in the longest path it visits in the graph. But Python has a limited number of stack frames (see sys.getrecursionlimit). To get round this limit, we can use the stack of iterators pattern, like this:

def cyclic(graph):
    """Return True if the directed graph has a cycle.
    The graph must be represented as a dictionary mapping vertices to
    iterables of neighbouring vertices. For example:

    >>> cyclic({1: (2,), 2: (3,), 3: (1,)})
    True
    >>> cyclic({1: (2,), 2: (3,), 3: (4,)})
    False

    """
    visited = set()
    path = [object()]
    path_set = set(path)
    stack = [iter(graph)]
    while stack:
        for v in stack[-1]:
            if v in path_set:
                return True
            elif v not in visited:
                visited.add(v)
                path.append(v)
                path_set.add(v)
                stack.append(iter(graph.get(v, ())))
                break
        else:
            path_set.remove(path.pop())
            stack.pop()
    return False