Cycle Detection in Graphs

MediumPython

Problem

Durlston Partners' research dependency graph represents relationships between computed artifacts and the inputs they depend on. Given this directed graph, determine whether any dependency cycle exists.

Implement has_cycle(graph). The graph is an adjacency-list dictionary where each key is a node and its value is a list of nodes it directly points to. Nodes may be disconnected, may appear only as neighbors, and may be represented by any hashable Python value. Return True if the graph contains at least one directed cycle, including a self-loop; otherwise return False.

Use an iterative traversal so the algorithm does not fail because of Python's recursion-depth limit on long dependency chains.

Formal Specification

Input: graph, a dictionary mapping hashable node labels to lists of neighboring node labels. A neighbor not present as a key is treated as a terminal node with no outgoing edges.
Output: A boolean indicating whether at least one directed cycle exists.

Constraints

0 <= number of keyed nodes <= 200,000
0 <= number of edges <= 500,000
Node labels are hashable
The graph may be disconnected
A neighbor may be absent from the dictionary
Duplicate edges may appear

Function Signature

def has_cycle(graph):

Use an iterative traversal so the algorithm does not fail because of Python's recursion-depth limit on long dependency chains.

Formal Specification

Input: graph, a dictionary mapping hashable node labels to lists of neighboring node labels. A neighbor not present as a key is treated as a terminal node with no outgoing edges.
Output: A boolean indicating whether at least one directed cycle exists.