rust_igraph/algorithms/paths/
distances_from.rs

1//! Multi-source unweighted shortest distances (ALGO-SP-060).
2//!
3//! Counterpart of `igraph_distances()` (multi-source mode) from
4//! `references/igraph/src/paths/unweighted.c`.
5//!
6//! Computes shortest-path distances from a set of source vertices to
7//! all other vertices, using BFS from each source.
8
9use std::collections::VecDeque;
10
11use crate::core::{Graph, IgraphError, IgraphResult, VertexId};
12
13/// Direction mode for [`distances_from_with_mode`].
14#[derive(Debug, Clone, Copy, PartialEq, Eq)]
15pub enum DistancesFromMode {
16    /// Follow outgoing edges.
17    Out,
18    /// Follow incoming edges.
19    In,
20    /// Ignore edge direction.
21    All,
22}
23
24/// Compute shortest-path distances from multiple sources to all vertices.
25///
26/// Returns a flat `Vec<Option<u32>>` of length `sources.len() * n` in
27/// row-major order, where `result[i * n + j]` is the shortest-path
28/// distance from `sources[i]` to vertex `j`. `None` means unreachable.
29///
30/// For directed graphs, follows outgoing edges by default. Use
31/// [`distances_from_with_mode`] for direction control.
32///
33/// # Errors
34///
35/// - `InvalidArgument` if any source vertex is out of range.
36///
37/// # Examples
38///
39/// ```
40/// use rust_igraph::{Graph, distances_from};
41///
42/// let mut g = Graph::with_vertices(5);
43/// g.add_edge(0, 1).unwrap();
44/// g.add_edge(1, 2).unwrap();
45/// g.add_edge(2, 3).unwrap();
46/// g.add_edge(3, 4).unwrap();
47/// let d = distances_from(&g, &[0, 2]).unwrap();
48/// let n = 5;
49/// // Row 0 (from vertex 0):
50/// assert_eq!(d[0], Some(0));
51/// assert_eq!(d[4], Some(4));
52/// // Row 1 (from vertex 2):
53/// assert_eq!(d[n + 2], Some(0));
54/// assert_eq!(d[n], Some(2)); // vertex 2 to vertex 0
55/// ```
56pub fn distances_from(graph: &Graph, sources: &[VertexId]) -> IgraphResult<Vec<Option<u32>>> {
57    let n = graph.vcount();
58    validate_sources(sources, n)?;
59
60    if sources.is_empty() {
61        return Ok(Vec::new());
62    }
63
64    let n_us = n as usize;
65    let total = sources.len().checked_mul(n_us).ok_or_else(|| {
66        IgraphError::InvalidArgument("distances_from: result size overflows".into())
67    })?;
68    let mut result = vec![None; total];
69
70    if graph.is_directed() {
71        let adj = build_out_adj(graph, n_us)?;
72        for (row, &src) in sources.iter().enumerate() {
73            bfs_with_adj(&adj, src, n_us, row, &mut result);
74        }
75    } else {
76        for (row, &src) in sources.iter().enumerate() {
77            bfs_undirected(graph, src, n_us, row, &mut result)?;
78        }
79    }
80
81    Ok(result)
82}
83
84/// Compute shortest-path distances from multiple sources with direction control.
85///
86/// For undirected graphs, `mode` is ignored.
87///
88/// # Errors
89///
90/// - `InvalidArgument` if any source vertex is out of range.
91///
92/// # Examples
93///
94/// ```
95/// use rust_igraph::{Graph, distances_from_with_mode, DistancesFromMode};
96///
97/// // Directed: 0→1→2→3
98/// let mut g = Graph::new(4, true).unwrap();
99/// g.add_edge(0, 1).unwrap();
100/// g.add_edge(1, 2).unwrap();
101/// g.add_edge(2, 3).unwrap();
102/// let d = distances_from_with_mode(&g, &[0, 3], DistancesFromMode::Out).unwrap();
103/// let n = 4;
104/// assert_eq!(d[3], Some(3));     // 0→1→2→3
105/// assert_eq!(d[n], None);        // 3 cannot reach 0 (Out)
106/// let d_in = distances_from_with_mode(&g, &[3], DistancesFromMode::In).unwrap();
107/// assert_eq!(d_in[0], Some(3));  // follow incoming from 3 back to 0
108/// ```
109pub fn distances_from_with_mode(
110    graph: &Graph,
111    sources: &[VertexId],
112    mode: DistancesFromMode,
113) -> IgraphResult<Vec<Option<u32>>> {
114    let n = graph.vcount();
115    validate_sources(sources, n)?;
116
117    if sources.is_empty() {
118        return Ok(Vec::new());
119    }
120
121    let n_us = n as usize;
122    let total = sources.len().checked_mul(n_us).ok_or_else(|| {
123        IgraphError::InvalidArgument("distances_from: result size overflows".into())
124    })?;
125    let mut result = vec![None; total];
126
127    if !graph.is_directed() {
128        for (row, &src) in sources.iter().enumerate() {
129            bfs_undirected(graph, src, n_us, row, &mut result)?;
130        }
131        return Ok(result);
132    }
133
134    let adj = match mode {
135        DistancesFromMode::Out => build_out_adj(graph, n_us)?,
136        DistancesFromMode::In => build_in_adj(graph, n_us)?,
137        DistancesFromMode::All => build_all_adj(graph, n_us)?,
138    };
139
140    for (row, &src) in sources.iter().enumerate() {
141        bfs_with_adj(&adj, src, n_us, row, &mut result);
142    }
143
144    Ok(result)
145}
146
147fn validate_sources(sources: &[VertexId], n: u32) -> IgraphResult<()> {
148    for &s in sources {
149        if s >= n {
150            return Err(IgraphError::InvalidArgument(format!(
151                "distances_from: source {s} out of range (vcount={n})"
152            )));
153        }
154    }
155    Ok(())
156}
157
158fn bfs_undirected(
159    graph: &Graph,
160    source: VertexId,
161    n_us: usize,
162    row: usize,
163    result: &mut [Option<u32>],
164) -> IgraphResult<()> {
165    let offset = row * n_us;
166    let mut visited = vec![false; n_us];
167    let mut queue = VecDeque::new();
168
169    visited[source as usize] = true;
170    result[offset + source as usize] = Some(0);
171    queue.push_back((source, 0u32));
172
173    while let Some((cur, dist)) = queue.pop_front() {
174        let next_dist = dist + 1;
175        for nb in graph.neighbors_iter(cur)? {
176            let nb_idx = nb as usize;
177            if !visited[nb_idx] {
178                visited[nb_idx] = true;
179                result[offset + nb_idx] = Some(next_dist);
180                queue.push_back((nb, next_dist));
181            }
182        }
183    }
184
185    Ok(())
186}
187
188fn bfs_with_adj(
189    adj: &[Vec<VertexId>],
190    source: VertexId,
191    n_us: usize,
192    row: usize,
193    result: &mut [Option<u32>],
194) {
195    let offset = row * n_us;
196    let mut visited = vec![false; n_us];
197    let mut queue = VecDeque::new();
198
199    visited[source as usize] = true;
200    result[offset + source as usize] = Some(0);
201    queue.push_back((source, 0u32));
202
203    while let Some((cur, dist)) = queue.pop_front() {
204        let next_dist = dist + 1;
205        for &nb in &adj[cur as usize] {
206            let nb_idx = nb as usize;
207            if !visited[nb_idx] {
208                visited[nb_idx] = true;
209                result[offset + nb_idx] = Some(next_dist);
210                queue.push_back((nb, next_dist));
211            }
212        }
213    }
214}
215
216fn build_out_adj(graph: &Graph, n_us: usize) -> IgraphResult<Vec<Vec<VertexId>>> {
217    let m =
218        u32::try_from(graph.ecount()).map_err(|_| IgraphError::Internal("ecount overflows u32"))?;
219    let mut adj: Vec<Vec<VertexId>> = vec![Vec::new(); n_us];
220    for eid in 0..m {
221        let (from, to) = graph.edge(eid)?;
222        adj[from as usize].push(to);
223    }
224    Ok(adj)
225}
226
227fn build_in_adj(graph: &Graph, n_us: usize) -> IgraphResult<Vec<Vec<VertexId>>> {
228    let m =
229        u32::try_from(graph.ecount()).map_err(|_| IgraphError::Internal("ecount overflows u32"))?;
230    let mut adj: Vec<Vec<VertexId>> = vec![Vec::new(); n_us];
231    for eid in 0..m {
232        let (from, to) = graph.edge(eid)?;
233        adj[to as usize].push(from);
234    }
235    Ok(adj)
236}
237
238fn build_all_adj(graph: &Graph, n_us: usize) -> IgraphResult<Vec<Vec<VertexId>>> {
239    let m =
240        u32::try_from(graph.ecount()).map_err(|_| IgraphError::Internal("ecount overflows u32"))?;
241    let mut adj: Vec<Vec<VertexId>> = vec![Vec::new(); n_us];
242    for eid in 0..m {
243        let (from, to) = graph.edge(eid)?;
244        adj[from as usize].push(to);
245        if from != to {
246            adj[to as usize].push(from);
247        }
248    }
249    Ok(adj)
250}
251
252#[cfg(test)]
253mod tests {
254    use super::*;
255
256    #[test]
257    fn empty_sources() {
258        let g = Graph::with_vertices(3);
259        let d = distances_from(&g, &[]).unwrap();
260        assert!(d.is_empty());
261    }
262
263    #[test]
264    fn single_source_matches_distances() {
265        let mut g = Graph::with_vertices(4);
266        g.add_edge(0, 1).unwrap();
267        g.add_edge(1, 2).unwrap();
268        g.add_edge(2, 3).unwrap();
269        let d = distances_from(&g, &[0]).unwrap();
270        assert_eq!(d, vec![Some(0), Some(1), Some(2), Some(3)]);
271    }
272
273    #[test]
274    fn multiple_sources() {
275        let mut g = Graph::with_vertices(4);
276        g.add_edge(0, 1).unwrap();
277        g.add_edge(1, 2).unwrap();
278        g.add_edge(2, 3).unwrap();
279        let d = distances_from(&g, &[0, 3]).unwrap();
280        let n = 4;
281        // Row 0 (from 0): [0, 1, 2, 3]
282        assert_eq!(d[0], Some(0));
283        assert_eq!(d[1], Some(1));
284        assert_eq!(d[2], Some(2));
285        assert_eq!(d[3], Some(3));
286        // Row 1 (from 3): [3, 2, 1, 0]
287        assert_eq!(d[n], Some(3));
288        assert_eq!(d[n + 1], Some(2));
289        assert_eq!(d[n + 2], Some(1));
290        assert_eq!(d[n + 3], Some(0));
291    }
292
293    #[test]
294    fn disconnected() {
295        let mut g = Graph::with_vertices(4);
296        g.add_edge(0, 1).unwrap();
297        g.add_edge(2, 3).unwrap();
298        let d = distances_from(&g, &[0]).unwrap();
299        assert_eq!(d[0], Some(0));
300        assert_eq!(d[1], Some(1));
301        assert_eq!(d[2], None);
302        assert_eq!(d[3], None);
303    }
304
305    #[test]
306    fn source_out_of_range() {
307        let g = Graph::with_vertices(3);
308        assert!(distances_from(&g, &[5]).is_err());
309    }
310
311    #[test]
312    fn directed_out() {
313        let mut g = Graph::new(3, true).unwrap();
314        g.add_edge(0, 1).unwrap();
315        g.add_edge(1, 2).unwrap();
316        let d = distances_from(&g, &[0, 2]).unwrap();
317        let n = 3;
318        // Row 0 (from 0, Out): [0, 1, 2]
319        assert_eq!(d[0], Some(0));
320        assert_eq!(d[1], Some(1));
321        assert_eq!(d[2], Some(2));
322        // Row 1 (from 2, Out): [None, None, 0]
323        assert_eq!(d[n], None);
324        assert_eq!(d[n + 1], None);
325        assert_eq!(d[n + 2], Some(0));
326    }
327
328    #[test]
329    fn directed_in_mode() {
330        let mut g = Graph::new(3, true).unwrap();
331        g.add_edge(0, 1).unwrap();
332        g.add_edge(1, 2).unwrap();
333        let d = distances_from_with_mode(&g, &[2], DistancesFromMode::In).unwrap();
334        // Following incoming from 2: 2←1←0
335        assert_eq!(d[0], Some(2));
336        assert_eq!(d[1], Some(1));
337        assert_eq!(d[2], Some(0));
338    }
339
340    #[test]
341    fn directed_all_mode() {
342        let mut g = Graph::new(3, true).unwrap();
343        g.add_edge(0, 1).unwrap();
344        g.add_edge(1, 2).unwrap();
345        let d = distances_from_with_mode(&g, &[2], DistancesFromMode::All).unwrap();
346        // All mode treats as undirected
347        assert_eq!(d[0], Some(2));
348        assert_eq!(d[1], Some(1));
349        assert_eq!(d[2], Some(0));
350    }
351
352    #[test]
353    fn duplicate_sources() {
354        let mut g = Graph::with_vertices(3);
355        g.add_edge(0, 1).unwrap();
356        g.add_edge(1, 2).unwrap();
357        let d = distances_from(&g, &[0, 0]).unwrap();
358        let n = 3;
359        // Both rows should be identical
360        assert_eq!(&d[..n], &d[n..]);
361    }
362
363    #[test]
364    fn star_graph() {
365        let mut g = Graph::with_vertices(5);
366        g.add_edge(0, 1).unwrap();
367        g.add_edge(0, 2).unwrap();
368        g.add_edge(0, 3).unwrap();
369        g.add_edge(0, 4).unwrap();
370        let d = distances_from(&g, &[1, 2]).unwrap();
371        let n = 5;
372        // From vertex 1: [1, 0, 2, 2, 2]
373        assert_eq!(d[0], Some(1));
374        assert_eq!(d[1], Some(0));
375        assert_eq!(d[2], Some(2));
376        assert_eq!(d[3], Some(2));
377        assert_eq!(d[4], Some(2));
378        // From vertex 2: [1, 2, 0, 2, 2]
379        assert_eq!(d[n], Some(1));
380        assert_eq!(d[n + 1], Some(2));
381        assert_eq!(d[n + 2], Some(0));
382    }
383}
rust_igraph/algorithms/paths/distances_from.rs

rust_igraph/algorithms/paths/
distances_from.rs
