Function come::utility::graph::dominance_frontiers

pub fn dominance_frontiers<N, G>(
    dominators: &Dominators<N>,
    graph: G
) -> HashMap<G::NodeId, Vec<G::NodeId>>
where
    N: Copy + Eq + Hash,
    <G as Visitable>::Map: VisitMap<N>,
    G: IntoNeighborsDirected + IntoNodeIdentifiers + IntoNeighbors + Visitable + GraphBase<NodeId = N>,
    <G as IntoNeighborsDirected>::NeighborsDirected: Clone,
    <G as GraphBase>::NodeId: Eq + Hash + Ord,

Initially implemented bu @m4b in petgraph#178.

This function will return dominance frontiers of a graph, which represent join points in a control flow graph, and have many applications like generating static single assignment form in a compiler.

The algorithm is mentioned in “Simple, Fast Dominance Algorithm” discovered by Cooper et al.

The algorithm is O(|V|²) in the worst case, but in most real world cases it has almost linear complexity.

graph must be the same, un-mutated graph that the dominators was constructed from.

Panic when there are nodes unreachable from the root node dominators constructed with.