Directed Graph Dominators

In a rooted directed graph, a vertex d dominates a vertex v if and only if every possible directed path from the root node to v passes through d. Dominator sets are critical in computer science, particularly in compiler optimization (e.g., Static Single Assignment form) and loop detection, as they identify inevitable bottlenecks in program control flow.

Experiment

Interact with the directed graph configurations in the Directed Graph Dominators module to observe how changing the graph topology, root node, and target node affects the dominator sets.

1. Select the Graph "Diamond", set Root to "0", and Target to "4". Note that the dominator set is 0,3,4. The paths split at 0 and merge at 3, making 3 an unavoidable chokepoint before reaching 4.
2. Change the Graph to "Loop" with Root "0" and Target "4". The loop between 1 and 2 changes the dominance relations, and the dominator set becomes 0,1,4. Node 1 is now the immediate dominator of 4.
3. Switch the Graph to "Unreachable", keeping Root "0" and Target "4". Observe that the target node 4 is cut off from the root, yielding a status of "Unreachable" and no valid dominator set.
4. Select the Graph "Star", with Root "0" and Target "4". Node 0 has direct edges to all other nodes. The immediate dominator of 4 is simply 0, and the dominator set is 0,4.