Function dfir_lang::graph::graph_algorithms::scc_kosaraju

source · 
pub fn scc_kosaraju<Id, NodeIds, PredsFn, SuccsFn, PredsIter, SuccsIter>(
    nodes: NodeIds,
    preds_fn: PredsFn,
    succs_fn: SuccsFn,
) -> BTreeMap<Id, Id>
where
    Id: Copy + Eq + Ord,
    NodeIds: IntoIterator<Item = Id>,
    PredsFn: FnMut(Id) -> PredsIter,
    SuccsFn: FnMut(Id) -> SuccsIter,
    PredsIter: IntoIterator<Item = Id>,
    SuccsIter: IntoIterator<Item = Id>,
Expand description

Finds the strongly connected components in the graph. A strongly connected component is a subset of nodes that are all reachable by each other.

https://en.wikipedia.org/wiki/Strongly_connected_component

Each component is represented by a specific member node. The returned BTreeMap maps each node ID to the node ID of its “representative.” Nodes with the same “representative” node are in the same strongly connected component.

This function uses Kosaraju’s algorithm.