petgraph/algo/
simple_paths.rs

1use std::{
2    hash::Hash,
3    iter::{from_fn, FromIterator},
4};
5
6use indexmap::IndexSet;
7
8use crate::{
9    visit::{IntoNeighborsDirected, NodeCount},
10    Direction::Outgoing,
11};
12
13/// Returns an iterator that produces all simple paths from `from` node to `to`, which contains at least `min_intermediate_nodes` nodes
14/// and at most `max_intermediate_nodes`, if given, or limited by the graph's order otherwise. The simple path is a path without repetitions.
15///
16/// This algorithm is adapted from <https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.simple_paths.all_simple_paths.html>.
17///
18/// # Example
19/// ```
20/// use petgraph::{algo, prelude::*};
21///
22/// let mut graph = DiGraph::<&str, i32>::new();
23///
24/// let a = graph.add_node("a");
25/// let b = graph.add_node("b");
26/// let c = graph.add_node("c");
27/// let d = graph.add_node("d");
28///
29/// graph.extend_with_edges(&[(a, b, 1), (b, c, 1), (c, d, 1), (a, b, 1), (b, d, 1)]);
30///
31/// let ways = algo::all_simple_paths::<Vec<_>, _>(&graph, a, d, 0, None)
32///   .collect::<Vec<_>>();
33///
34/// assert_eq!(4, ways.len());
35/// ```
36pub fn all_simple_paths<TargetColl, G>(
37    graph: G,
38    from: G::NodeId,
39    to: G::NodeId,
40    min_intermediate_nodes: usize,
41    max_intermediate_nodes: Option<usize>,
42) -> impl Iterator<Item = TargetColl>
43where
44    G: NodeCount,
45    G: IntoNeighborsDirected,
46    G::NodeId: Eq + Hash,
47    TargetColl: FromIterator<G::NodeId>,
48{
49    // how many nodes are allowed in simple path up to target node
50    // it is min/max allowed path length minus one, because it is more appropriate when implementing lookahead
51    // than constantly add 1 to length of current path
52    let max_length = if let Some(l) = max_intermediate_nodes {
53        l + 1
54    } else {
55        graph.node_count() - 1
56    };
57
58    let min_length = min_intermediate_nodes + 1;
59
60    // list of visited nodes
61    let mut visited: IndexSet<G::NodeId> = IndexSet::from_iter(Some(from));
62    // list of childs of currently exploring path nodes,
63    // last elem is list of childs of last visited node
64    let mut stack = vec![graph.neighbors_directed(from, Outgoing)];
65
66    from_fn(move || {
67        while let Some(children) = stack.last_mut() {
68            if let Some(child) = children.next() {
69                if visited.len() < max_length {
70                    if child == to {
71                        if visited.len() >= min_length {
72                            let path = visited
73                                .iter()
74                                .cloned()
75                                .chain(Some(to))
76                                .collect::<TargetColl>();
77                            return Some(path);
78                        }
79                    } else if !visited.contains(&child) {
80                        visited.insert(child);
81                        stack.push(graph.neighbors_directed(child, Outgoing));
82                    }
83                } else {
84                    if (child == to || children.any(|v| v == to)) && visited.len() >= min_length {
85                        let path = visited
86                            .iter()
87                            .cloned()
88                            .chain(Some(to))
89                            .collect::<TargetColl>();
90                        return Some(path);
91                    }
92                    stack.pop();
93                    visited.pop();
94                }
95            } else {
96                stack.pop();
97                visited.pop();
98            }
99        }
100        None
101    })
102}
103
104#[cfg(test)]
105mod test {
106    use std::{collections::HashSet, iter::FromIterator};
107
108    use itertools::assert_equal;
109
110    use crate::{dot::Dot, prelude::DiGraph};
111
112    use super::all_simple_paths;
113
114    #[test]
115    fn test_all_simple_paths() {
116        let graph = DiGraph::<i32, i32, _>::from_edges(&[
117            (0, 1),
118            (0, 2),
119            (0, 3),
120            (1, 2),
121            (1, 3),
122            (2, 3),
123            (2, 4),
124            (3, 2),
125            (3, 4),
126            (4, 2),
127            (4, 5),
128            (5, 2),
129            (5, 3),
130        ]);
131
132        let expexted_simple_paths_0_to_5 = vec![
133            vec![0usize, 1, 2, 3, 4, 5],
134            vec![0, 1, 2, 4, 5],
135            vec![0, 1, 3, 2, 4, 5],
136            vec![0, 1, 3, 4, 5],
137            vec![0, 2, 3, 4, 5],
138            vec![0, 2, 4, 5],
139            vec![0, 3, 2, 4, 5],
140            vec![0, 3, 4, 5],
141        ];
142
143        println!("{}", Dot::new(&graph));
144        let actual_simple_paths_0_to_5: HashSet<Vec<_>> =
145            all_simple_paths(&graph, 0u32.into(), 5u32.into(), 0, None)
146                .map(|v: Vec<_>| v.into_iter().map(|i| i.index()).collect())
147                .collect();
148        assert_eq!(actual_simple_paths_0_to_5.len(), 8);
149        assert_eq!(
150            HashSet::from_iter(expexted_simple_paths_0_to_5),
151            actual_simple_paths_0_to_5
152        );
153    }
154
155    #[test]
156    fn test_one_simple_path() {
157        let graph = DiGraph::<i32, i32, _>::from_edges(&[(0, 1), (2, 1)]);
158
159        let expexted_simple_paths_0_to_1 = &[vec![0usize, 1]];
160        println!("{}", Dot::new(&graph));
161        let actual_simple_paths_0_to_1: Vec<Vec<_>> =
162            all_simple_paths(&graph, 0u32.into(), 1u32.into(), 0, None)
163                .map(|v: Vec<_>| v.into_iter().map(|i| i.index()).collect())
164                .collect();
165
166        assert_eq!(actual_simple_paths_0_to_1.len(), 1);
167        assert_equal(expexted_simple_paths_0_to_1, &actual_simple_paths_0_to_1);
168    }
169
170    #[test]
171    fn test_no_simple_paths() {
172        let graph = DiGraph::<i32, i32, _>::from_edges(&[(0, 1), (2, 1)]);
173
174        println!("{}", Dot::new(&graph));
175        let actual_simple_paths_0_to_2: Vec<Vec<_>> =
176            all_simple_paths(&graph, 0u32.into(), 2u32.into(), 0, None)
177                .map(|v: Vec<_>| v.into_iter().map(|i| i.index()).collect())
178                .collect();
179
180        assert_eq!(actual_simple_paths_0_to_2.len(), 0);
181    }
182}
petgraph/algo/simple_paths.rs

petgraph/algo/
simple_paths.rs
