petgraph/algo/
simple_paths.rs

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

petgraph/algo/
simple_paths.rs
