petgraph::algo::dominators

Function simple_fast

Source 
pub fn simple_fast<G>(graph: G, root: G::NodeId) -> Dominators<G::NodeId>
where
    G: IntoNeighbors + Visitable,
    <G as GraphBase>::NodeId: Eq + Hash,
Expand description

This is an implementation of the engineered “Simple, Fast Dominance Algorithm” discovered by Cooper et al.

This algorithm is O(|V|²) where V is the set of nodes, and therefore has slower theoretical running time than the Lengauer-Tarjan algorithm (which is O(|E| log |V|) where E is the set of edges). However, Cooper et al found it to be faster in practice on control flow graphs of up to ~30,000 nodes.

§Arguments

  • graph: a control-flow graph.
  • root: the root node of the graph.

§Returns

  • Dominators: the dominance relation for given graph and root represented by Dominators.

§Complexity

  • Time complexity: O(|V|²).
  • Auxiliary space: O(|V| + |E|).

where |V| is the number of nodes and |E| is the number of edges.