Python topological failure: return a cycle witness

Operation contract

A shipment workflow has receive, validate and dispatch stages. Dispatch depends on receive, closing the cycle. Returning the offending path gives an operator a specific configuration error instead of an empty schedule. Topological sorting handles acyclic dependencies; strong components help when many cycles must be grouped.

Failure and ownership boundary

DFS state distinguishes unseen, active-path and completed nodes. Only an edge to an active node proves a cycle on the current traversal. This recursive version is suitable for bounded configuration graphs; an untrusted deep graph needs an iterative stack to avoid Python's recursion limit.

Working program

graph = {
    "receive": ["validate"],
    "validate": ["dispatch"],
    "dispatch": ["receive"],
}
state = {}
path = []

def cycle_from(stage):
    state[stage] = "active"
    path.append(stage)
    for dependency in graph[stage]:
        if state.get(dependency) == "active":
            return path[path.index(dependency):] + [dependency]
        if dependency not in state:
            found = cycle_from(dependency)
            if found:
                return found
    path.pop()
    state[stage] = "done"
    return None

print(" -> ".join(cycle_from("receive")))

Output

receive -> validate -> dispatch -> receive

Costs and limits

DFS takes O(V+E) time and O(V) state. The path lookup is O(V) once a cycle is found; an index map helps when reporting many witnesses.

Common Mistakes

• An edge to a completed node is not a back edge.
• Do not publish a partial order as valid after finding a cycle.
• Recursive DFS needs a depth policy for untrusted input.

Connected lessons

Python topological sort: dependency order and cycle rejection, Python strongly connected components: partition a directed dependency graph, Python graph condensation: collapse directed cycles into an acyclic component graph.