rust_igraph/algorithms/paths/
distances_cutoff.rs

1//! Unweighted shortest-path distances with cutoff (ALGO-SP-061).
2//!
3//! Counterpart of `igraph_i_distances_unweighted_cutoff()` from
4//! `references/igraph/src/paths/unweighted.c:102-219`. BFS that stops
5//! exploring vertices beyond a caller-specified distance limit.
6//!
7//! Single-source entry points mirror [`super::distances::distances`]
8//! with an added `cutoff` parameter; multi-source entry points mirror
9//! [`super::distances_from::distances_from`] with cutoff.
10
11use std::collections::VecDeque;
12
13use crate::core::{Graph, IgraphError, IgraphResult, VertexId};
14
15/// Direction mode for cutoff-aware unweighted distance functions.
16#[derive(Debug, Clone, Copy, PartialEq, Eq)]
17pub enum DistancesCutoffMode {
18    /// Follow outgoing edges.
19    Out,
20    /// Follow incoming edges.
21    In,
22    /// Ignore edge direction.
23    All,
24}
25
26/// Unweighted shortest-path lengths from `source` to every vertex,
27/// ignoring paths longer than `cutoff`.
28///
29/// Vertices beyond the cutoff (or in a different component) get `None`.
30/// `cutoff == None` behaves identically to [`super::distances::distances`].
31///
32/// Counterpart of `igraph_distances_cutoff(_, NULL, _, source, all,
33/// IGRAPH_OUT, cutoff)`.
34///
35/// # Examples
36///
37/// ```
38/// use rust_igraph::{Graph, distances_cutoff};
39///
40/// let mut g = Graph::with_vertices(5);
41/// g.add_edge(0, 1).unwrap();
42/// g.add_edge(1, 2).unwrap();
43/// g.add_edge(2, 3).unwrap();
44/// g.add_edge(3, 4).unwrap();
45///
46/// let d = distances_cutoff(&g, 0, Some(2)).unwrap();
47/// assert_eq!(d, vec![Some(0), Some(1), Some(2), None, None]);
48///
49/// // No cutoff — same as `distances`.
50/// let d_all = distances_cutoff(&g, 0, None).unwrap();
51/// assert_eq!(d_all, vec![Some(0), Some(1), Some(2), Some(3), Some(4)]);
52/// ```
53pub fn distances_cutoff(
54    graph: &Graph,
55    source: VertexId,
56    cutoff: Option<u32>,
57) -> IgraphResult<Vec<Option<u32>>> {
58    distances_cutoff_with_mode(graph, source, cutoff, DistancesCutoffMode::Out)
59}
60
61/// Mode-aware [`distances_cutoff`]. For undirected graphs `mode` is
62/// ignored.
63///
64/// # Examples
65///
66/// ```
67/// use rust_igraph::{Graph, distances_cutoff_with_mode, DistancesCutoffMode};
68///
69/// // Directed: 0→1→2→3
70/// let mut g = Graph::new(4, true).unwrap();
71/// g.add_edge(0, 1).unwrap();
72/// g.add_edge(1, 2).unwrap();
73/// g.add_edge(2, 3).unwrap();
74///
75/// let d = distances_cutoff_with_mode(&g, 0, Some(1), DistancesCutoffMode::Out).unwrap();
76/// assert_eq!(d, vec![Some(0), Some(1), None, None]);
77///
78/// let d_in = distances_cutoff_with_mode(&g, 3, Some(2), DistancesCutoffMode::In).unwrap();
79/// assert_eq!(d_in, vec![None, Some(2), Some(1), Some(0)]);
80/// ```
81pub fn distances_cutoff_with_mode(
82    graph: &Graph,
83    source: VertexId,
84    cutoff: Option<u32>,
85    mode: DistancesCutoffMode,
86) -> IgraphResult<Vec<Option<u32>>> {
87    let n = graph.vcount();
88    if n == 0 {
89        return Ok(Vec::new());
90    }
91    if source >= n {
92        return Err(IgraphError::InvalidArgument(format!(
93            "distances_cutoff: source {source} out of range (vcount={n})"
94        )));
95    }
96
97    if !graph.is_directed() {
98        return bfs_cutoff_undirected(graph, source, n as usize, cutoff);
99    }
100
101    let n_us = n as usize;
102    let adj = match mode {
103        DistancesCutoffMode::Out => build_out_adj(graph, n_us)?,
104        DistancesCutoffMode::In => build_in_adj(graph, n_us)?,
105        DistancesCutoffMode::All => build_all_adj(graph, n_us)?,
106    };
107    Ok(bfs_cutoff_with_adj(&adj, source, n_us, cutoff))
108}
109
110/// Multi-source unweighted distances with cutoff, direction-aware.
111///
112/// Returns a flat `Vec<Option<u32>>` of length `sources.len() * n` in
113/// row-major order, where `result[i * n + j]` is the shortest-path
114/// distance from `sources[i]` to vertex `j` (or `None` if unreachable /
115/// past the cutoff).
116///
117/// # Examples
118///
119/// ```
120/// use rust_igraph::{Graph, distances_cutoff_multi, DistancesCutoffMode};
121///
122/// let mut g = Graph::with_vertices(5);
123/// g.add_edge(0, 1).unwrap();
124/// g.add_edge(1, 2).unwrap();
125/// g.add_edge(2, 3).unwrap();
126/// g.add_edge(3, 4).unwrap();
127/// let d = distances_cutoff_multi(&g, &[0, 2], Some(1), DistancesCutoffMode::Out).unwrap();
128/// let n = 5;
129/// // Row 0 (from 0, cutoff 1): only 0 and 1 reachable
130/// assert_eq!(d[0], Some(0));
131/// assert_eq!(d[1], Some(1));
132/// assert_eq!(d[2], None);
133/// // Row 1 (from 2, cutoff 1): 1, 2, 3
134/// assert_eq!(d[n + 1], Some(1));
135/// assert_eq!(d[n + 2], Some(0));
136/// assert_eq!(d[n + 3], Some(1));
137/// assert_eq!(d[n + 4], None);
138/// ```
139pub fn distances_cutoff_multi(
140    graph: &Graph,
141    sources: &[VertexId],
142    cutoff: Option<u32>,
143    mode: DistancesCutoffMode,
144) -> IgraphResult<Vec<Option<u32>>> {
145    let n = graph.vcount();
146    for &s in sources {
147        if s >= n {
148            return Err(IgraphError::InvalidArgument(format!(
149                "distances_cutoff_multi: source {s} out of range (vcount={n})"
150            )));
151        }
152    }
153
154    if sources.is_empty() {
155        return Ok(Vec::new());
156    }
157
158    let n_us = n as usize;
159    let total = sources.len().checked_mul(n_us).ok_or_else(|| {
160        IgraphError::InvalidArgument("distances_cutoff_multi: result size overflows".into())
161    })?;
162    let mut result = vec![None; total];
163
164    if !graph.is_directed() {
165        for (row, &src) in sources.iter().enumerate() {
166            bfs_cutoff_undirected_into(graph, src, n_us, cutoff, row, &mut result)?;
167        }
168        return Ok(result);
169    }
170
171    let adj = match mode {
172        DistancesCutoffMode::Out => build_out_adj(graph, n_us)?,
173        DistancesCutoffMode::In => build_in_adj(graph, n_us)?,
174        DistancesCutoffMode::All => build_all_adj(graph, n_us)?,
175    };
176
177    for (row, &src) in sources.iter().enumerate() {
178        bfs_cutoff_with_adj_into(&adj, src, n_us, cutoff, row, &mut result);
179    }
180
181    Ok(result)
182}
183
184// ---- internal BFS helpers ----
185
186fn bfs_cutoff_undirected(
187    graph: &Graph,
188    source: VertexId,
189    n_us: usize,
190    cutoff: Option<u32>,
191) -> IgraphResult<Vec<Option<u32>>> {
192    let mut dist: Vec<Option<u32>> = vec![None; n_us];
193    let mut queue: VecDeque<(VertexId, u32)> = VecDeque::new();
194
195    dist[source as usize] = Some(0);
196    queue.push_back((source, 0));
197
198    while let Some((v, d)) = queue.pop_front() {
199        if let Some(c) = cutoff {
200            if d >= c {
201                continue;
202            }
203        }
204        let next = d.checked_add(1).ok_or(IgraphError::Internal(
205            "distance overflow (graph diameter exceeds u32::MAX)",
206        ))?;
207        for w in graph.neighbors_iter(v)? {
208            if dist[w as usize].is_none() {
209                dist[w as usize] = Some(next);
210                queue.push_back((w, next));
211            }
212        }
213    }
214
215    Ok(dist)
216}
217
218fn bfs_cutoff_undirected_into(
219    graph: &Graph,
220    source: VertexId,
221    n_us: usize,
222    cutoff: Option<u32>,
223    row: usize,
224    result: &mut [Option<u32>],
225) -> IgraphResult<()> {
226    let offset = row * n_us;
227    let mut visited = vec![false; n_us];
228    let mut queue: VecDeque<(VertexId, u32)> = VecDeque::new();
229
230    visited[source as usize] = true;
231    result[offset + source as usize] = Some(0);
232    queue.push_back((source, 0));
233
234    while let Some((v, d)) = queue.pop_front() {
235        if let Some(c) = cutoff {
236            if d >= c {
237                continue;
238            }
239        }
240        let next = d + 1;
241        for w in graph.neighbors_iter(v)? {
242            let w_idx = w as usize;
243            if !visited[w_idx] {
244                visited[w_idx] = true;
245                result[offset + w_idx] = Some(next);
246                queue.push_back((w, next));
247            }
248        }
249    }
250
251    Ok(())
252}
253
254fn bfs_cutoff_with_adj(
255    adj: &[Vec<VertexId>],
256    source: VertexId,
257    n_us: usize,
258    cutoff: Option<u32>,
259) -> Vec<Option<u32>> {
260    let mut dist: Vec<Option<u32>> = vec![None; n_us];
261    let mut queue: VecDeque<(VertexId, u32)> = VecDeque::new();
262
263    dist[source as usize] = Some(0);
264    queue.push_back((source, 0));
265
266    while let Some((v, d)) = queue.pop_front() {
267        if let Some(c) = cutoff {
268            if d >= c {
269                continue;
270            }
271        }
272        let next = d + 1;
273        for &w in &adj[v as usize] {
274            if dist[w as usize].is_none() {
275                dist[w as usize] = Some(next);
276                queue.push_back((w, next));
277            }
278        }
279    }
280
281    dist
282}
283
284fn bfs_cutoff_with_adj_into(
285    adj: &[Vec<VertexId>],
286    source: VertexId,
287    n_us: usize,
288    cutoff: Option<u32>,
289    row: usize,
290    result: &mut [Option<u32>],
291) {
292    let offset = row * n_us;
293    let mut visited = vec![false; n_us];
294
295    visited[source as usize] = true;
296    result[offset + source as usize] = Some(0);
297    let mut queue: VecDeque<(VertexId, u32)> = VecDeque::new();
298    queue.push_back((source, 0));
299
300    while let Some((v, d)) = queue.pop_front() {
301        if let Some(c) = cutoff {
302            if d >= c {
303                continue;
304            }
305        }
306        let next = d + 1;
307        for &w in &adj[v as usize] {
308            let w_idx = w as usize;
309            if !visited[w_idx] {
310                visited[w_idx] = true;
311                result[offset + w_idx] = Some(next);
312                queue.push_back((w, next));
313            }
314        }
315    }
316}
317
318fn build_out_adj(graph: &Graph, n_us: usize) -> IgraphResult<Vec<Vec<VertexId>>> {
319    let m =
320        u32::try_from(graph.ecount()).map_err(|_| IgraphError::Internal("ecount overflows u32"))?;
321    let mut adj: Vec<Vec<VertexId>> = vec![Vec::new(); n_us];
322    for eid in 0..m {
323        let (from, to) = graph.edge(eid)?;
324        adj[from as usize].push(to);
325    }
326    Ok(adj)
327}
328
329fn build_in_adj(graph: &Graph, n_us: usize) -> IgraphResult<Vec<Vec<VertexId>>> {
330    let m =
331        u32::try_from(graph.ecount()).map_err(|_| IgraphError::Internal("ecount overflows u32"))?;
332    let mut adj: Vec<Vec<VertexId>> = vec![Vec::new(); n_us];
333    for eid in 0..m {
334        let (from, to) = graph.edge(eid)?;
335        adj[to as usize].push(from);
336    }
337    Ok(adj)
338}
339
340fn build_all_adj(graph: &Graph, n_us: usize) -> IgraphResult<Vec<Vec<VertexId>>> {
341    let m =
342        u32::try_from(graph.ecount()).map_err(|_| IgraphError::Internal("ecount overflows u32"))?;
343    let mut adj: Vec<Vec<VertexId>> = vec![Vec::new(); n_us];
344    for eid in 0..m {
345        let (from, to) = graph.edge(eid)?;
346        adj[from as usize].push(to);
347        if from != to {
348            adj[to as usize].push(from);
349        }
350    }
351    Ok(adj)
352}
353
354#[cfg(test)]
355mod tests {
356    use super::*;
357
358    // ---- distances_cutoff (single-source) ----
359
360    #[test]
361    fn empty_graph() {
362        let g = Graph::with_vertices(0);
363        assert_eq!(
364            distances_cutoff(&g, 0, Some(5)).unwrap(),
365            Vec::<Option<u32>>::new()
366        );
367    }
368
369    #[test]
370    fn single_vertex_no_edges() {
371        let g = Graph::with_vertices(1);
372        assert_eq!(distances_cutoff(&g, 0, Some(0)).unwrap(), vec![Some(0)]);
373    }
374
375    #[test]
376    fn cutoff_zero_returns_only_source() {
377        let mut g = Graph::with_vertices(3);
378        g.add_edge(0, 1).unwrap();
379        g.add_edge(1, 2).unwrap();
380        let d = distances_cutoff(&g, 0, Some(0)).unwrap();
381        assert_eq!(d, vec![Some(0), None, None]);
382    }
383
384    #[test]
385    fn cutoff_one_returns_direct_neighbors() {
386        let mut g = Graph::with_vertices(4);
387        g.add_edge(0, 1).unwrap();
388        g.add_edge(1, 2).unwrap();
389        g.add_edge(2, 3).unwrap();
390        let d = distances_cutoff(&g, 0, Some(1)).unwrap();
391        assert_eq!(d, vec![Some(0), Some(1), None, None]);
392    }
393
394    #[test]
395    fn cutoff_covers_entire_graph() {
396        let mut g = Graph::with_vertices(4);
397        g.add_edge(0, 1).unwrap();
398        g.add_edge(1, 2).unwrap();
399        g.add_edge(2, 3).unwrap();
400        let d = distances_cutoff(&g, 0, Some(100)).unwrap();
401        assert_eq!(d, vec![Some(0), Some(1), Some(2), Some(3)]);
402    }
403
404    #[test]
405    fn none_cutoff_same_as_no_limit() {
406        let mut g = Graph::with_vertices(5);
407        g.add_edge(0, 1).unwrap();
408        g.add_edge(1, 2).unwrap();
409        g.add_edge(2, 3).unwrap();
410        g.add_edge(3, 4).unwrap();
411        let d = distances_cutoff(&g, 0, None).unwrap();
412        assert_eq!(d, vec![Some(0), Some(1), Some(2), Some(3), Some(4)]);
413    }
414
415    #[test]
416    fn disconnected_components() {
417        let mut g = Graph::with_vertices(4);
418        g.add_edge(0, 1).unwrap();
419        g.add_edge(2, 3).unwrap();
420        let d = distances_cutoff(&g, 0, Some(10)).unwrap();
421        assert_eq!(d, vec![Some(0), Some(1), None, None]);
422    }
423
424    #[test]
425    fn invalid_source() {
426        let g = Graph::with_vertices(3);
427        assert!(distances_cutoff(&g, 5, Some(1)).is_err());
428    }
429
430    #[test]
431    fn directed_out_cutoff() {
432        let mut g = Graph::new(4, true).unwrap();
433        g.add_edge(0, 1).unwrap();
434        g.add_edge(1, 2).unwrap();
435        g.add_edge(2, 3).unwrap();
436        let d = distances_cutoff(&g, 0, Some(2)).unwrap();
437        assert_eq!(d, vec![Some(0), Some(1), Some(2), None]);
438    }
439
440    #[test]
441    fn directed_in_mode_cutoff() {
442        let mut g = Graph::new(4, true).unwrap();
443        g.add_edge(0, 1).unwrap();
444        g.add_edge(1, 2).unwrap();
445        g.add_edge(2, 3).unwrap();
446        let d = distances_cutoff_with_mode(&g, 3, Some(1), DistancesCutoffMode::In).unwrap();
447        assert_eq!(d, vec![None, None, Some(1), Some(0)]);
448    }
449
450    #[test]
451    fn directed_all_mode_cutoff() {
452        let mut g = Graph::new(3, true).unwrap();
453        g.add_edge(0, 1).unwrap();
454        g.add_edge(1, 2).unwrap();
455        let d = distances_cutoff_with_mode(&g, 2, Some(1), DistancesCutoffMode::All).unwrap();
456        assert_eq!(d, vec![None, Some(1), Some(0)]);
457    }
458
459    #[test]
460    fn cycle_with_cutoff() {
461        let mut g = Graph::with_vertices(6);
462        for i in 0..5u32 {
463            g.add_edge(i, i + 1).unwrap();
464        }
465        g.add_edge(5, 0).unwrap();
466        let d = distances_cutoff(&g, 0, Some(2)).unwrap();
467        assert_eq!(d, vec![Some(0), Some(1), Some(2), None, Some(2), Some(1)]);
468    }
469
470    #[test]
471    fn self_loop_with_cutoff() {
472        let mut g = Graph::with_vertices(2);
473        g.add_edge(0, 0).unwrap();
474        g.add_edge(0, 1).unwrap();
475        let d = distances_cutoff(&g, 0, Some(1)).unwrap();
476        assert_eq!(d, vec![Some(0), Some(1)]);
477    }
478
479    // ---- distances_cutoff_multi ----
480
481    #[test]
482    fn multi_empty_sources() {
483        let g = Graph::with_vertices(3);
484        assert!(
485            distances_cutoff_multi(&g, &[], Some(1), DistancesCutoffMode::Out)
486                .unwrap()
487                .is_empty()
488        );
489    }
490
491    #[test]
492    fn multi_basic() {
493        let mut g = Graph::with_vertices(5);
494        g.add_edge(0, 1).unwrap();
495        g.add_edge(1, 2).unwrap();
496        g.add_edge(2, 3).unwrap();
497        g.add_edge(3, 4).unwrap();
498        let d = distances_cutoff_multi(&g, &[0, 4], Some(2), DistancesCutoffMode::Out).unwrap();
499        let n = 5;
500        // Row 0 (from 0): 0,1,2,None,None
501        assert_eq!(d[0], Some(0));
502        assert_eq!(d[1], Some(1));
503        assert_eq!(d[2], Some(2));
504        assert_eq!(d[3], None);
505        assert_eq!(d[4], None);
506        // Row 1 (from 4): None,None,2,1,0
507        assert_eq!(d[n], None);
508        assert_eq!(d[n + 1], None);
509        assert_eq!(d[n + 2], Some(2));
510        assert_eq!(d[n + 3], Some(1));
511        assert_eq!(d[n + 4], Some(0));
512    }
513
514    #[test]
515    fn multi_directed_in() {
516        let mut g = Graph::new(3, true).unwrap();
517        g.add_edge(0, 1).unwrap();
518        g.add_edge(1, 2).unwrap();
519        let d = distances_cutoff_multi(&g, &[2], Some(1), DistancesCutoffMode::In).unwrap();
520        assert_eq!(d, vec![None, Some(1), Some(0)]);
521    }
522
523    #[test]
524    fn multi_invalid_source() {
525        let g = Graph::with_vertices(3);
526        assert!(distances_cutoff_multi(&g, &[0, 10], Some(1), DistancesCutoffMode::Out).is_err());
527    }
528
529    #[test]
530    fn consistency_with_uncutoff_distances() {
531        let mut g = Graph::with_vertices(6);
532        g.add_edge(0, 1).unwrap();
533        g.add_edge(1, 2).unwrap();
534        g.add_edge(2, 3).unwrap();
535        g.add_edge(3, 4).unwrap();
536        g.add_edge(4, 5).unwrap();
537        g.add_edge(5, 0).unwrap();
538
539        let full = crate::algorithms::paths::distances::distances(&g, 0).unwrap();
540        let cutoff_large = distances_cutoff(&g, 0, Some(100)).unwrap();
541        assert_eq!(full, cutoff_large);
542    }
543}
rust_igraph/algorithms/paths/distances_cutoff.rs

rust_igraph/algorithms/paths/
distances_cutoff.rs
