Deadlock Detection via Wait-For Graph Cyclehard

Deadlock Detection via Wait-For Graph Cycle

hard Agents in Production 15 min

NumPy allowed · plain Python earns 10 bonus points

Implement cycle detection in a wait-for graph, the real, standard technique for detecting deadlock among agents holding and requesting shared resources.

Task

Implement has_deadlock(wait_for). wait_for[a] lists the agents that agent a is waiting on. Return True if the directed graph contains ANY cycle (a deadlock), else False. Use DFS with recursion-stack tracking.

Function Signature

has_deadlock(wait_for: dict[str, list[str]]) -> bool

Examples

Example 1: simple two-node cycle
Input: wait_for = {'a': ['b'], 'b': ['a']}
Output: True

Example 2: no cycle, linear chain
Input: wait_for = {'a': ['b'], 'b': ['c'], 'c': []}
Output: False

Example 3: self-loop is a cycle
Input: wait_for = {'a': ['a']}
Output: True

Constraints

wait_for maps agent -> list of agents it waits on (may reference agents not present as keys)

Python3Saved ✓

def has_deadlock(wait_for):

# Your implementation here

pass

Case 1: simple two-node cycle

Input: wait_for = {'a': ['b'], 'b': ['a']}

Expected: True

Case 2: no cycle, linear chain

Input: wait_for = {'a': ['b'], 'b': ['c'], 'c': []}

Expected: False

Case 3: self-loop is a cycle

Input: wait_for = {'a': ['a']}

Expected: True