Module petgraph::algo::dominators

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

• Dominators
  The dominance relation for some graph and root.
• DominatorsIter
  Iterator for a node’s dominators.

Constants

• UNDEFINED 🔒
  The undefined dominator sentinel, for when we have not yet discovered a node’s dominator.

Functions

• intersect 🔒
• predecessor_sets_to_idx_vecs 🔒
• simple_fast
  This is an implementation of the engineered “Simple, Fast Dominance Algorithm” discovered by Cooper et al.
• simple_fast_post_order 🔒