Unit 11: Going in Circles

Meeting a node you are still inside

Give every node a colour. White: not touched. Grey: started, still exploring below it. Black: completely finished.

A one-way graph has a cycle exactly when a search finds an arrow pointing at a grey node — because grey means "you are still standing on it", so that arrow leads back to where you came from.

The whole check

Arrows into black nodes are fine — that part of the graph is finished and led nowhere back. Only grey means trouble.

Here 1 to 2 to 3 to 1 is the loop, and the search finds it the moment it looks at 3's arrow.

Python

def has_cycle(n, adj):
    colour = [0] * n

    def dfs(node):
        colour[node] = 1
        for nxt in adj[node]:
            if colour[nxt] == 1:
                return True
            if colour[nxt] == 0 and dfs(nxt):
                return True
        colour[node] = 2
        return False

    for i in range(n):
        if colour[i] == 0 and dfs(i):
            return True
    return False

print(has_cycle(5, [[1], [2], [3], [1], [0]]))
print(has_cycle(5, [[1], [2], [3], [], [0]]))

It prints

True
False

Why "any visited node" is the wrong test

A diamond — 0 points at 1 and 2, both point at 3 — has no cycle at all, but the second route into 3 finds a node that has been visited.

If you had checked "visited" rather than "grey", you would have reported a loop that is not there. Black exists precisely to say "visited, and safely finished".

Python

adj = [[1, 2], [3], [3], []]
colour = [0] * 4
seen_black = []

def dfs(node):
    colour[node] = 1
    for nxt in adj[node]:
        if colour[nxt] == 1:
            print("cycle!")
        if colour[nxt] == 0:
            dfs(nxt)
    colour[node] = 2
    seen_black.append(node)

dfs(0)
print(seen_black)

It prints

[3, 1, 2, 0]

And the order they turn black is useful

Nodes go black after everything they point at. So reversing that list gives a topological order — 0, 2, 1, 3 here — which is the other way to write unit 10's sort.

Kahn's version is still the safer one in Python, because this one is a recursion.

Every undirected edge looks like a loop

Walk from 0 to 1 along an edge. From 1 there is an edge back to 0, and 0 has been visited — but that is the road you just came down, not a cycle.

So remember which node you came from and ignore exactly that one.

Python

def has_cycle(n, edges):
    adj = [[] for i in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    visited = [False] * n

    def dfs(node, parent):
        visited[node] = True
        for nxt in adj[node]:
            if not visited[nxt]:
                if dfs(nxt, node):
                    return True
            elif nxt != parent:
                return True
        return False

    for i in range(n):
        if not visited[i] and dfs(i, -1):
            return True
    return False

print(has_cycle(4, [(0, 1), (1, 2), (2, 3)]))
print(has_cycle(4, [(0, 1), (1, 2), (2, 3), (3, 0)]))

It prints

False
True

Counting edges answers it too

A connected graph with no cycles is a tree, and a tree with n nodes has exactly n - 1 edges. One more edge anywhere, and a cycle is unavoidable.

So for a connected graph you can answer without searching at all — although you still have to check it is connected.

Python

for n, m in [(4, 3), (4, 4), (7, 6), (7, 9)]:
    print(n, m, m >= n)

It prints

4 3 False
4 4 True
7 6 False
7 9 True

Careful with a repeated edge

If the input can list the same edge twice, the parent trick reports "no cycle" — the second copy looks like the road you came down.

Two roads between the same pair of towns really is a loop. A problem allowing that needs the edge remembered by its number, not by the node at the end of it.

Yes is rarely the answer they want

Problems ask "print the cycle", not "does one exist". The search already knows: when it meets a grey node, that node is the start of the loop and the node it is standing on is the end.

Walk the parents from the end back to the start and you have it.

Remembering who sent you

parent[nxt] = node as you go down. found is a two-item list rather than two ordinary variables, because a value assigned inside a nested function would otherwise be a brand new local one.

Python

n = 5
adj = [[1], [2], [3], [1], [0]]
colour = [0] * n
parent = [-1] * n
found = [-1, -1]

def dfs(node):
    colour[node] = 1
    for nxt in adj[node]:
        if colour[nxt] == 1:
            found[0] = nxt
            found[1] = node
            return True
        if colour[nxt] == 0:
            parent[nxt] = node
            if dfs(nxt):
                return True
    colour[node] = 2
    return False

for i in range(n):
    if colour[i] == 0 and dfs(i):
        break

print(found)
print(parent)

It prints

[1, 3]
[-1, 0, 1, 2, -1]

Walking the chain back

From the end of the loop, follow parents until you reach the start, then reverse. Add the start on the front and you have the whole circle: 1, 2, 3.

Every arrow in that list really is in the graph, which is a check worth doing by eye once.

Python

parent = [-1, 0, 1, 2, -1]
start = 1
end = 3

cycle = [end]
node = end
while node != start:
    node = parent[node]
    cycle.append(node)

cycle.reverse()
print(cycle)

It prints

[1, 2, 3]

The same shape, for the negative cycle of unit 9

Bellman–Ford also finds a loop rather than a route: if an edge still relaxes on round n, its far end is inside — or reachable from — a negative cycle.

Following the "who improved me last" chain back n times lands you on the cycle, and walking the parents from there prints it. Same trick, different search.

A path that must end in a loop

Back to a successor graph — one exit per node. Follow it for ever and you cannot escape: there are only n nodes, so somewhere you must arrive somewhere you have been.

The question is how far along the loop starts, and how long it is. A visited list answers it in n memory. Two pointers answer it in none.

One walks, one runs

The tortoise takes one step at a time, the hare two. If there is a loop, the hare comes round the back of the tortoise and they land on the same node.

They are guaranteed to meet, because on the loop the gap between them closes by exactly one each round.

Python

succ = [1, 2, 3, 4, 5, 3]

slow = succ[0]
fast = succ[succ[0]]
steps = 0
while slow != fast:
    slow = succ[slow]
    fast = succ[succ[fast]]
    steps += 1

print(slow, fast, steps)

It prints

3 3 2

The bit that looks like magic

Now put the tortoise back at the start and move both one step at a time. Where they meet is the first node of the loop.

It is not magic, it is arithmetic: when they first met, the hare had walked exactly one whole number of loops more than the tortoise, which makes the distance from the start to the loop the same as the distance from the meeting point round to it.

Python

succ = [1, 2, 3, 4, 5, 3]

slow = succ[0]
fast = succ[succ[0]]
while slow != fast:
    slow = succ[slow]
    fast = succ[succ[fast]]

slow = 0
while slow != fast:
    slow = succ[slow]
    fast = succ[fast]
start = slow

length = 1
node = succ[start]
while node != start:
    node = succ[node]
    length += 1

print(start, length)

It prints

3 3

Three steps, no memory

Find a meeting point. Walk from the start to find where the loop begins. Walk once round to measure it.

With a visited array this is easier to write and needs a number for every node. On a graph with a thousand million nodes described by a formula rather than a list, only the two pointers will do.