weavatrix_graph/algo/components/
scc.rs

1use crate::Vec;
2use crate::{EdgeEndpoints, IndexGraphView};
3
4#[must_use]
5pub fn strongly_connected_components<G>(graph: &G) -> Vec<Vec<G::Node>>
6where
7    G: IndexGraphView,
8{
9    with_filter(graph, &|_| true)
10}
11
12#[must_use]
13pub fn strongly_connected_components_filtered<G, F>(graph: &G, allows_edge: F) -> Vec<Vec<G::Node>>
14where
15    G: IndexGraphView,
16    F: Fn(G::Edge) -> bool,
17{
18    with_filter(graph, &allows_edge)
19}
20
21pub(super) fn with_filter<G, F>(graph: &G, allows_edge: &F) -> Vec<Vec<G::Node>>
22where
23    G: IndexGraphView,
24    F: Fn(G::Edge) -> bool,
25{
26    let mut seen = vec![false; graph.node_bound()];
27    let mut finish = Vec::with_capacity(graph.node_count());
28    for start in graph.node_indices() {
29        finish_from(graph, start, allows_edge, &mut seen, &mut finish);
30    }
31
32    seen.fill(false);
33    let mut components = Vec::new();
34    for start in finish.into_iter().rev() {
35        if seen[G::node_slot(start)] {
36            continue;
37        }
38        let mut component = Vec::new();
39        let mut stack = vec![start];
40        seen[G::node_slot(start)] = true;
41        while let Some(node) = stack.pop() {
42            component.push(node);
43            for edge in graph.incoming_edges(node) {
44                if !allows_edge(edge) {
45                    continue;
46                }
47                let Some(source) = graph.edge_endpoints(edge).map(EdgeEndpoints::source) else {
48                    continue;
49                };
50                let slot = G::node_slot(source);
51                if !seen[slot] {
52                    seen[slot] = true;
53                    stack.push(source);
54                }
55            }
56        }
57        components.push(component);
58    }
59    components
60}
61
62fn finish_from<G, F>(
63    graph: &G,
64    start: G::Node,
65    allows_edge: &F,
66    seen: &mut [bool],
67    finish: &mut Vec<G::Node>,
68) where
69    G: IndexGraphView,
70    F: Fn(G::Edge) -> bool,
71{
72    if seen[G::node_slot(start)] {
73        return;
74    }
75    let mut stack = vec![(start, false)];
76    while let Some((node, exiting)) = stack.pop() {
77        let slot = G::node_slot(node);
78        if exiting {
79            finish.push(node);
80            continue;
81        }
82        if seen[slot] {
83            continue;
84        }
85        seen[slot] = true;
86        stack.push((node, true));
87        for edge in graph.outgoing_edges(node) {
88            if !allows_edge(edge) {
89                continue;
90            }
91            let Some(target) = graph.edge_endpoints(edge).map(EdgeEndpoints::target) else {
92                continue;
93            };
94            if !seen[G::node_slot(target)] {
95                stack.push((target, false));
96            }
97        }
98    }
99}
weavatrix_graph/algo/components/scc.rs

weavatrix_graph/algo/components/
scc.rs
