rust_igraph/algorithms/connectivity/
is_connected.rs

1//! Connectivity predicate (ALGO-CC-050).
2//!
3//! Checks whether a graph is connected without computing full component structure.
4//! Counterpart of `igraph_is_connected`.
5
6use crate::core::{Graph, IgraphResult};
7
8/// Connectivity mode for directed graphs.
9#[derive(Debug, Clone, Copy, PartialEq, Eq)]
10pub enum ConnectednessMode {
11    /// Weak connectivity (ignore edge directions).
12    Weak,
13    /// Strong connectivity (respect edge directions).
14    Strong,
15}
16
17/// Tests whether the graph is connected.
18///
19/// For undirected graphs, `mode` is ignored and the function checks
20/// whether all vertices are reachable from each other.
21///
22/// For directed graphs:
23/// - `Weak`: checks if the underlying undirected graph is connected.
24/// - `Strong`: checks if every vertex is reachable from every other vertex
25///   following edge directions.
26///
27/// An empty graph (0 vertices) is considered connected. A graph with
28/// a single vertex is always connected.
29///
30/// # Examples
31///
32/// ```
33/// use rust_igraph::{Graph, is_connected, ConnectednessMode};
34///
35/// let mut g = Graph::with_vertices(4);
36/// g.add_edge(0, 1).unwrap();
37/// g.add_edge(1, 2).unwrap();
38/// g.add_edge(2, 3).unwrap();
39/// assert!(is_connected(&g, ConnectednessMode::Weak).unwrap());
40///
41/// // Disconnected graph
42/// let g = Graph::with_vertices(4);
43/// assert!(!is_connected(&g, ConnectednessMode::Weak).unwrap());
44///
45/// // Directed: weakly but not strongly connected
46/// let mut g = Graph::new(3, true).unwrap();
47/// g.add_edge(0, 1).unwrap();
48/// g.add_edge(1, 2).unwrap();
49/// assert!(is_connected(&g, ConnectednessMode::Weak).unwrap());
50/// assert!(!is_connected(&g, ConnectednessMode::Strong).unwrap());
51/// ```
52pub fn is_connected(graph: &Graph, mode: ConnectednessMode) -> IgraphResult<bool> {
53    let n = graph.vcount();
54
55    if n <= 1 {
56        return Ok(true);
57    }
58
59    if mode == ConnectednessMode::Strong && graph.is_directed() {
60        return is_strongly_connected(graph);
61    }
62
63    is_weakly_connected(graph)
64}
65
66fn is_weakly_connected(graph: &Graph) -> IgraphResult<bool> {
67    let n = graph.vcount();
68    let nn = n as usize;
69
70    // Build symmetric adjacency list from all edges
71    let mut adj: Vec<Vec<u32>> = vec![Vec::new(); nn];
72    let ecount = graph.ecount();
73    for eid in 0..ecount {
74        #[allow(clippy::cast_possible_truncation)]
75        let (src, tgt) = graph.edge(eid as u32)?;
76        if src != tgt {
77            adj[src as usize].push(tgt);
78            adj[tgt as usize].push(src);
79        }
80    }
81
82    // BFS from vertex 0
83    let mut visited = vec![false; nn];
84    let mut queue = std::collections::VecDeque::new();
85
86    visited[0] = true;
87    queue.push_back(0u32);
88    let mut count = 1u32;
89
90    while let Some(v) = queue.pop_front() {
91        for &nb in &adj[v as usize] {
92            if !visited[nb as usize] {
93                visited[nb as usize] = true;
94                count += 1;
95                queue.push_back(nb);
96            }
97        }
98    }
99
100    Ok(count == n)
101}
102
103fn is_strongly_connected(graph: &Graph) -> IgraphResult<bool> {
104    let n = graph.vcount();
105    let nn = n as usize;
106    let ecount = graph.ecount();
107
108    // Build forward and reverse adjacency lists
109    let mut fwd: Vec<Vec<u32>> = vec![Vec::new(); nn];
110    let mut rev: Vec<Vec<u32>> = vec![Vec::new(); nn];
111    for eid in 0..ecount {
112        #[allow(clippy::cast_possible_truncation)]
113        let (src, tgt) = graph.edge(eid as u32)?;
114        if src != tgt {
115            fwd[src as usize].push(tgt);
116            rev[tgt as usize].push(src);
117        }
118    }
119
120    // Forward BFS from vertex 0
121    let forward_count = bfs_count_adj(&fwd, n, 0);
122    if forward_count != n {
123        return Ok(false);
124    }
125
126    // Backward BFS from vertex 0 (using reverse adj)
127    let backward_count = bfs_count_adj(&rev, n, 0);
128    Ok(backward_count == n)
129}
130
131fn bfs_count_adj(adj: &[Vec<u32>], n: u32, start: u32) -> u32 {
132    let mut visited = vec![false; n as usize];
133    let mut queue = std::collections::VecDeque::new();
134
135    visited[start as usize] = true;
136    queue.push_back(start);
137    let mut count = 1u32;
138
139    while let Some(v) = queue.pop_front() {
140        for &nb in &adj[v as usize] {
141            if !visited[nb as usize] {
142                visited[nb as usize] = true;
143                count += 1;
144                queue.push_back(nb);
145            }
146        }
147    }
148
149    count
150}
151
152#[cfg(test)]
153mod tests {
154    use super::*;
155
156    #[test]
157    fn test_empty_graph() {
158        let g = Graph::with_vertices(0);
159        assert!(is_connected(&g, ConnectednessMode::Weak).unwrap());
160    }
161
162    #[test]
163    fn test_single_vertex() {
164        let g = Graph::with_vertices(1);
165        assert!(is_connected(&g, ConnectednessMode::Weak).unwrap());
166        assert!(is_connected(&g, ConnectednessMode::Strong).unwrap());
167    }
168
169    #[test]
170    fn test_two_connected() {
171        let mut g = Graph::with_vertices(2);
172        g.add_edge(0, 1).unwrap();
173        assert!(is_connected(&g, ConnectednessMode::Weak).unwrap());
174    }
175
176    #[test]
177    fn test_two_disconnected() {
178        let g = Graph::with_vertices(2);
179        assert!(!is_connected(&g, ConnectednessMode::Weak).unwrap());
180    }
181
182    #[test]
183    fn test_path_connected() {
184        let mut g = Graph::with_vertices(5);
185        g.add_edge(0, 1).unwrap();
186        g.add_edge(1, 2).unwrap();
187        g.add_edge(2, 3).unwrap();
188        g.add_edge(3, 4).unwrap();
189        assert!(is_connected(&g, ConnectednessMode::Weak).unwrap());
190    }
191
192    #[test]
193    fn test_two_components() {
194        let mut g = Graph::with_vertices(4);
195        g.add_edge(0, 1).unwrap();
196        g.add_edge(2, 3).unwrap();
197        assert!(!is_connected(&g, ConnectednessMode::Weak).unwrap());
198    }
199
200    #[test]
201    fn test_directed_weakly_connected() {
202        let mut g = Graph::new(3, true).unwrap();
203        g.add_edge(0, 1).unwrap();
204        g.add_edge(1, 2).unwrap();
205        assert!(is_connected(&g, ConnectednessMode::Weak).unwrap());
206    }
207
208    #[test]
209    fn test_directed_not_strongly_connected() {
210        let mut g = Graph::new(3, true).unwrap();
211        g.add_edge(0, 1).unwrap();
212        g.add_edge(1, 2).unwrap();
213        assert!(!is_connected(&g, ConnectednessMode::Strong).unwrap());
214    }
215
216    #[test]
217    fn test_directed_strongly_connected() {
218        let mut g = Graph::new(3, true).unwrap();
219        g.add_edge(0, 1).unwrap();
220        g.add_edge(1, 2).unwrap();
221        g.add_edge(2, 0).unwrap();
222        assert!(is_connected(&g, ConnectednessMode::Strong).unwrap());
223    }
224
225    #[test]
226    fn test_complete_graph() {
227        let mut g = Graph::with_vertices(5);
228        for i in 0..5u32 {
229            for j in (i + 1)..5 {
230                g.add_edge(i, j).unwrap();
231            }
232        }
233        assert!(is_connected(&g, ConnectednessMode::Weak).unwrap());
234    }
235
236    #[test]
237    fn test_star_connected() {
238        let mut g = Graph::with_vertices(5);
239        for i in 1..5u32 {
240            g.add_edge(0, i).unwrap();
241        }
242        assert!(is_connected(&g, ConnectednessMode::Weak).unwrap());
243    }
244
245    #[test]
246    fn test_directed_star_weak_not_strong() {
247        let mut g = Graph::new(4, true).unwrap();
248        g.add_edge(0, 1).unwrap();
249        g.add_edge(0, 2).unwrap();
250        g.add_edge(0, 3).unwrap();
251        assert!(is_connected(&g, ConnectednessMode::Weak).unwrap());
252        assert!(!is_connected(&g, ConnectednessMode::Strong).unwrap());
253    }
254}
rust_igraph/algorithms/connectivity/is_connected.rs

rust_igraph/algorithms/connectivity/
is_connected.rs
