RavnaryA Knowledge Platform
Colour theme

Card 05/ 08

Take the quiz

ConceptDifficulty: Intermediate2 min

Detecting a Cycle by Counting the Output

When no vertex is ready and some are left, the ones left contain a cycle.

Kahn's algorithm reports a cycle without looking for one: if it stops with fewer vertices output than the graph has, the graph has a directed cycle and no topological order exists. This card shows why on the topic's graph with one edge added, F->B, which closes the loop B->F->B, and says what the vertices left over do and do not tell you.

The trace below runs Kahn's algorithm on that graph from a run. Each cell is a vertex and its count of unmet dependencies, or out once output.

In-degrees as Kahn's algorithm runs on the topic's graph with F->B added

InputEdges D->A, D->B, C->B, A->F, B->F, B->E and F->B

  1. Start

    1. A:1
    2. B:3
    3. C:0
    4. D:0
    5. E:1
    6. F:2

    With F->B added, B waits on three vertices: C, D and F. C and D are ready, as before.

  2. Output C

    1. A:1
    2. B:2
    3. C:outnext
    4. D:0
    5. E:1
    6. F:2

    C is output, and B drops to 2.

  3. Output D

    1. A:0
    2. B:1
    3. C:out
    4. D:outnext
    5. E:1
    6. F:2

    D is output. A reaches 0 and joins the queue; B drops to 1, still waiting on F.

  4. Output A

    1. A:outnext
    2. B:1
    3. C:out
    4. D:out
    5. E:1
    6. F:1

    A is output and F drops to 1. The queue is empty, and B, E and F are left with a count of 1 each.

ResultOutput C D A, 3 of 6 vertices; B, E and F are left with in-degree 1

The reason is that no vertex on a cycle can ever be the first of the cycle to be output. Each one waits on the vertex before it on the cycle, so each keeps a count of at least 1 until another vertex of the cycle goes out, and none of them can go first. Here B waits on F and F waits on B, so neither count reaches 0 and the queue runs dry. Without a cycle, some vertex left over always has a count of 0, so the algorithm only stops early when there is one.

The vertices left over contain a cycle, but they need not all be on it. E is left with a count of 1 because it waits on B, and B is stuck; E itself is on no cycle. A report that lists every vertex left over shows what cannot be scheduled, but to name the cycle itself, run depth-first search with three colours on the leftovers, as Graph Traversal's cycle card does.

The check costs nothing extra: compare the length of the output with the number of vertices once the queue is empty. A program that skips it returns C D A for this graph, a list that looks like an answer and silently leaves out half the tasks.

← → move through sections and cards