sim_lib_discrete_graph/
connectivity.rs

1//! Connected components (undirected / weak) and strongly connected components.
2
3use crate::edge::Directedness;
4use crate::error::GraphError;
5use crate::graph::Graph;
6
7/// Build adjacency lists, optionally treating every edge as undirected.
8fn adjacency<N, W>(
9    graph: &Graph<N, W>,
10    force_undirected: bool,
11) -> Result<Vec<Vec<usize>>, GraphError> {
12    graph.validate()?;
13    let n = graph.node_count();
14    let mut adj = vec![Vec::new(); n];
15    let undirected = force_undirected || matches!(graph.directedness, Directedness::Undirected);
16    for e in &graph.edges {
17        adj[e.source].push(e.target);
18        if undirected {
19            adj[e.target].push(e.source);
20        }
21    }
22    for list in &mut adj {
23        list.sort_unstable();
24    }
25    Ok(adj)
26}
27
28/// Flood fill over undirected adjacency, returning sorted components ordered by
29/// their smallest member.
30fn flood(adj: &[Vec<usize>]) -> Vec<Vec<usize>> {
31    let n = adj.len();
32    let mut seen = vec![false; n];
33    let mut comps = Vec::new();
34    for s in 0..n {
35        if seen[s] {
36            continue;
37        }
38        let mut members = Vec::new();
39        let mut stack = vec![s];
40        seen[s] = true;
41        while let Some(u) = stack.pop() {
42            members.push(u);
43            for &w in &adj[u] {
44                if !seen[w] {
45                    seen[w] = true;
46                    stack.push(w);
47                }
48            }
49        }
50        members.sort_unstable();
51        comps.push(members);
52    }
53    comps
54}
55
56/// Connected components of an undirected graph (treats edges as undirected).
57pub fn connected_components<N, W>(graph: &Graph<N, W>) -> Result<Vec<Vec<usize>>, GraphError> {
58    Ok(flood(&adjacency(graph, true)?))
59}
60
61/// Weakly connected components of a directed graph (ignores edge direction).
62pub fn weakly_connected_components<N, W>(
63    graph: &Graph<N, W>,
64) -> Result<Vec<Vec<usize>>, GraphError> {
65    Ok(flood(&adjacency(graph, true)?))
66}
67
68/// Strongly connected components via iterative Tarjan, respecting edge
69/// direction. Each component is sorted; components are ordered by smallest
70/// member. (For undirected graphs this coincides with connected components.)
71pub fn strongly_connected_components<N, W>(
72    graph: &Graph<N, W>,
73) -> Result<Vec<Vec<usize>>, GraphError> {
74    let adj = adjacency(graph, false)?;
75    let n = adj.len();
76    const UNVISITED: usize = usize::MAX;
77    let mut index = vec![UNVISITED; n];
78    let mut low = vec![0usize; n];
79    let mut on_stack = vec![false; n];
80    let mut tstack: Vec<usize> = Vec::new();
81    let mut comps: Vec<Vec<usize>> = Vec::new();
82    let mut counter = 0usize;
83
84    for start in 0..n {
85        if index[start] != UNVISITED {
86            continue;
87        }
88        // Work stack of (node, next-child-cursor).
89        let mut work: Vec<(usize, usize)> = vec![(start, 0)];
90        while let Some(&(v, ci)) = work.last() {
91            if ci == 0 && index[v] == UNVISITED {
92                index[v] = counter;
93                low[v] = counter;
94                counter += 1;
95                tstack.push(v);
96                on_stack[v] = true;
97            }
98            if ci < adj[v].len() {
99                let w = adj[v][ci];
100                work.last_mut().unwrap().1 += 1;
101                if index[w] == UNVISITED {
102                    work.push((w, 0));
103                } else if on_stack[w] {
104                    low[v] = low[v].min(index[w]);
105                }
106            } else {
107                if low[v] == index[v] {
108                    let mut comp = Vec::new();
109                    loop {
110                        let w = tstack.pop().expect("tarjan stack non-empty");
111                        on_stack[w] = false;
112                        comp.push(w);
113                        if w == v {
114                            break;
115                        }
116                    }
117                    comp.sort_unstable();
118                    comps.push(comp);
119                }
120                work.pop();
121                if let Some(&(parent, _)) = work.last() {
122                    low[parent] = low[parent].min(low[v]);
123                }
124            }
125        }
126    }
127    comps.sort_by_key(|c| c[0]);
128    Ok(comps)
129}
130
131#[cfg(test)]
132mod tests {
133    use super::*;
134
135    #[test]
136    fn undirected_components_match_fixture() {
137        // Two clusters: {0,1,2} and {3,4}; node 5 isolated.
138        let mut g: Graph<u8, u64> =
139            Graph::with_nodes(vec![0, 1, 2, 3, 4, 5], Directedness::Undirected);
140        g.add_edge(0, 1, 1).unwrap();
141        g.add_edge(1, 2, 1).unwrap();
142        g.add_edge(3, 4, 1).unwrap();
143        let comps = connected_components(&g).unwrap();
144        assert_eq!(comps, vec![vec![0, 1, 2], vec![3, 4], vec![5]]);
145    }
146
147    #[test]
148    fn scc_finds_directed_cycle() {
149        // 0->1->2->0 is one SCC; 3 is its own; edge 2->3 does not merge them.
150        let mut g: Graph<u8, u64> = Graph::with_nodes(vec![0, 1, 2, 3], Directedness::Directed);
151        g.add_edge(0, 1, 1).unwrap();
152        g.add_edge(1, 2, 1).unwrap();
153        g.add_edge(2, 0, 1).unwrap();
154        g.add_edge(2, 3, 1).unwrap();
155        let comps = strongly_connected_components(&g).unwrap();
156        assert_eq!(comps, vec![vec![0, 1, 2], vec![3]]);
157    }
158
159    #[test]
160    fn scc_of_dag_is_singletons() {
161        let mut g: Graph<u8, u64> = Graph::with_nodes(vec![0, 1, 2], Directedness::Directed);
162        g.add_edge(0, 1, 1).unwrap();
163        g.add_edge(1, 2, 1).unwrap();
164        let comps = strongly_connected_components(&g).unwrap();
165        assert_eq!(comps, vec![vec![0], vec![1], vec![2]]);
166    }
167}
sim_lib_discrete_graph/connectivity.rs

sim_lib_discrete_graph/
connectivity.rs
