Plan-DAG Cycle Detection

Background

A planner that emits sub-tasks with dependencies must produce a directed acyclic graph (DAG) — otherwise the executor loops forever. Cycle detection on the DAG is a precondition for scheduling; without it, a malformed plan slips into the runtime and hangs.

Problem statement

Implement has_cycle(graph) where graph is a dict[node, list[node]] adjacency map. Return True iff the graph contains a directed cycle. Use 3-colour DFS: white (unvisited), gray (in current DFS path), black (fully explored). Hitting a gray node during DFS = back edge = cycle.

Input

• graph — dict[hashable, list[hashable]] adjacency map. Missing keys in the values list are treated as terminal (no outgoing edges).

Output

Returns bool.

Examples

Example 1 — linear chain

Input:  {"a": ["b"], "b": ["c"], "c": []}
Output: False

Example 2 — self-loop

Input:  {"a": ["a"]}
Output: True

Example 3 — three-node cycle

Input:  {"a": ["b"], "b": ["c"], "c": ["a"]}
Output: True

Example 4 — disconnected components, one cyclic

Input:  {"a": ["b"], "b": [], "c": ["d"], "d": ["c"]}
Output: True

Constraints

• Handle empty graph ({}) → False.
• Walk every node in case the graph is disconnected.
• Nodes appearing only as targets (no key in graph) are treated as having no outgoing edges.

Notes

• Why 3-colour, not 2. A simple visited set distinguishes back edges from cross edges only with extra state — 3-colour DFS makes the distinction inherent.
• Topological sort gives the same answer. Successful topological sort = acyclic; failure = cyclic. Either approach works; DFS is simpler to reason about.