pathfinding/directed/
strongly_connected_components.rs

1//! Separate nodes of a directed graph into [strongly connected
2//! components](https://en.wikipedia.org/wiki/Strongly_connected_component).
3//!
4//! A [path-based strong component
5//! algorithm](https://en.wikipedia.org/wiki/Path-based_strong_component_algorithm)
6//! is used.
7
8use std::collections::{HashMap, HashSet};
9use std::hash::Hash;
10
11struct Params<N, FN>
12where
13    N: Hash + Eq,
14{
15    preorders: HashMap<N, Option<usize>>,
16    c: usize,
17    successors: FN,
18    p: Vec<N>,
19    s: Vec<N>,
20    scc: Vec<Vec<N>>,
21    scca: HashSet<N>,
22}
23
24impl<N, FN, IN> Params<N, FN>
25where
26    N: Clone + Hash + Eq,
27    FN: FnMut(&N) -> IN,
28    IN: IntoIterator<Item = N>,
29{
30    fn new(nodes: &[N], successors: FN) -> Self {
31        Self {
32            preorders: nodes
33                .iter()
34                .map(|n| (n.clone(), None))
35                .collect::<HashMap<N, Option<usize>>>(),
36            c: 0,
37            successors,
38            p: Vec::new(),
39            s: Vec::new(),
40            scc: Vec::new(),
41            scca: HashSet::new(),
42        }
43    }
44}
45
46fn recurse_onto<N, FN, IN>(v: &N, params: &mut Params<N, FN>)
47where
48    N: Clone + Hash + Eq,
49    FN: FnMut(&N) -> IN,
50    IN: IntoIterator<Item = N>,
51{
52    params.preorders.insert(v.clone(), Some(params.c));
53    params.c += 1;
54    params.s.push(v.clone());
55    params.p.push(v.clone());
56    for w in (params.successors)(v) {
57        if !params.scca.contains(&w) {
58            if let Some(pw) = params.preorders.get(&w).and_then(|w| *w) {
59                while params.preorders[&params.p[params.p.len() - 1]].unwrap() > pw {
60                    params.p.pop();
61                }
62            } else {
63                recurse_onto(&w, params);
64            }
65        }
66    }
67    if params.p[params.p.len() - 1] == *v {
68        params.p.pop();
69        let mut component = Vec::new();
70        while let Some(node) = params.s.pop() {
71            component.push(node.clone());
72            params.scca.insert(node.clone());
73            params.preorders.remove(&node);
74            if node == *v {
75                break;
76            }
77        }
78        params.scc.push(component);
79    }
80}
81
82/// Partition nodes reachable from a starting point into strongly connected components.
83///
84/// - `start` is the node we want to explore the graph from.
85/// - `successors` returns a list of successors for a given node.
86///
87/// The function returns a list of strongly connected components sets. It will contain
88/// at least one component (the one containing the `start` node).
89pub fn strongly_connected_components_from<N, FN, IN>(start: &N, successors: FN) -> Vec<Vec<N>>
90where
91    N: Clone + Hash + Eq,
92    FN: FnMut(&N) -> IN,
93    IN: IntoIterator<Item = N>,
94{
95    let mut params = Params::new(&[], successors);
96    recurse_onto(start, &mut params);
97    params.scc
98}
99
100/// Compute the strongly connected component containing a given node.
101///
102/// - `node` is the node we want the strongly connected component for.
103/// - `successors` returns a list of successors for a given node.
104///
105/// The function returns the strongly connected component containing the node,
106/// which is guaranteed to contain at least `node`.
107#[allow(clippy::missing_panics_doc)]
108pub fn strongly_connected_component<N, FN, IN>(node: &N, successors: FN) -> Vec<N>
109where
110    N: Clone + Hash + Eq,
111    FN: FnMut(&N) -> IN,
112    IN: IntoIterator<Item = N>,
113{
114    // The unwrap() cannot fail as there will always be at least one group.
115    strongly_connected_components_from(node, successors)
116        .pop()
117        .unwrap()
118}
119
120/// Partition all strongly connected components in a graph.
121///
122/// - `nodes` is a collection of nodes.
123/// - `successors` returns a list of successors for a given node.
124///
125/// The function returns a list of strongly connected components sets.
126pub fn strongly_connected_components<N, FN, IN>(nodes: &[N], successors: FN) -> Vec<Vec<N>>
127where
128    N: Clone + Hash + Eq,
129    FN: FnMut(&N) -> IN,
130    IN: IntoIterator<Item = N>,
131{
132    let mut params = Params::new(nodes, successors);
133    while let Some(node) = params.preorders.keys().find(|_| true).cloned() {
134        recurse_onto(&node, &mut params);
135    }
136    params.scc
137}
pathfinding/directed/strongly_connected_components.rs

pathfinding/directed/
strongly_connected_components.rs
