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

petgraph/algo/
simple_paths.rs
