Cycles in a Directed Graph

The Idea

One visited set cannot distinguish two very different situations: a node you finished long ago, and a node still sitting open on the path beneath you. Three colours can. White is untouched, grey is on the current path, black is finished. An edge into grey is a back edge, and a back edge is a cycle.

Real-World Example

A build system asked whether its tasks can run at all. Task graphs grow by accident, and the day someone makes deploy a prerequisite of build, the pipeline has no legal starting point. Colouring finds that loop before the first job runs.

The Code

g = {"build": ["test"], "test": ["deploy"], "deploy": ["build"], "docs": []}
colour = {n: "white" for n in g}

def visit(n):
    colour[n] = "grey"                   # on the current path
    for m in g[n]:
        if colour[m] == "grey":          # back edge: the path bites itself
            return True
        if colour[m] == "white" and visit(m):
            return True
    colour[n] = "black"                  # finished, never on a path again
    return False

print(any(visit(n) for n in g if colour[n] == "white"))   # True

g = {"a": ["b", "c"], "b": ["c"], "c": []}
colour = {n: "white" for n in g}

def visit(n):
  colour[n] = "grey"
  for m in g[n]:
      if colour[m] == "grey":
          return True
      if colour[m] == "white" and visit(m):
          return True
  colour[n] = "black"
  return False

print(any(visit(n) for n in g if colour[n] == "white"))