Module petgraph::algo::dominators
source · Expand description
Compute dominators of a control-flow graph.
The Dominance Relation
In a directed graph with a root node R, a node A is said to dominate a node B iff every path from R to B contains A.
The node A is said to strictly dominate the node B iff A dominates B and A ≠ B.
The node A is said to be the immediate dominator of a node B iff it strictly dominates B and there does not exist any node C where A dominates C and C dominates B.
Structs
- Iterator for nodes dominated by a given node.
- The dominance relation for some graph and root.
- Iterator for a node’s dominators.
Functions
- This is an implementation of the engineered “Simple, Fast Dominance Algorithm” discovered by Cooper et al.