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.

Dominator Sets

By definition, a root node always dominates itself. The dominator set of any other node is determined by the intersection of the dominator sets of its immediate predecessors. If a node is unreachable from the root, dominance is undefined. In our model, we only compute dominance over reachable vertices to ensure robust convergence even in the presence of unreachable cycles.

Immediate Dominators

Every node (except the root) that is reachable from the root has exactly one immediate dominator. The immediate dominator of a node v, denoted as idom(v), is a unique strict dominator of v that does not dominate any other strict dominator of v. Intuitively, it is the closest strict dominator to v on any path from the root.

Worked Example

Consider a "Diamond" graph with nodes 0, 1, 2, 3, and 4. The edges are directed from top to bottom, with the path splitting and then merging again. Specifically, the edges are (0→1), (0→2), (1→3), (2→3), and (3→4). Let node 0 be the root, and we want to find the dominators for target node 4.

We initialize the dominator sets:

Dom(0) = {0}
Dom(1), Dom(2), Dom(3), Dom(4) = {0, 1, 2, 3, 4} (the set of all reachable nodes)

We iteratively update the sets by taking the intersection of the predecessors' dominators, plus the node itself:


Iteration 1:
Dom(1) = (Dom(0)) ∪ {1} = {0} ∪ {1} = {0, 1}
Dom(2) = (Dom(0)) ∪ {2} = {0} ∪ {2} = {0, 2}
Dom(3) = (Dom(1) ∩ Dom(2)) ∪ {3}
       = ({0, 1} ∩ {0, 2}) ∪ {3}
       = {0} ∪ {3} = {0, 3}
Dom(4) = (Dom(3)) ∪ {4} = {0, 3} ∪ {4} = {0, 3, 4}

Subsequent iterations yield no changes, indicating convergence. The dominator set for target node 4 is 0,3,4, totaling 3 dominators. Since node 3 is a strict dominator of 4 and is dominated by the other strict dominator (node 0), the immediate dominator of 4 is 3.

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.

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.
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.
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.
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.

Limitations

This module operates on a finite set of specific, predefined graph topologies with exactly 5 vertices to clearly demonstrate the concepts of dominance. It does not provide a general-purpose solver for arbitrary graph inputs or infinite graphs. Furthermore, the algorithm strictly analyzes reachability before computing dominance sets, meaning that unreachable vertices correctly report an undefined dominance status rather than yielding degenerate empty sets.

References

The computation of dominance and immediate dominators follows standard algorithms on directed graphs.

NetworkX Developers. "NetworkX Algorithms: Dominance".
https://networkx.org/documentation/networkx-3.3/reference/algorithms/generated/networkx.algorithms.dominance.immediate_dominators.html

Directed Graph Dominators