1 use std::{
2     hash::Hash,
3     iter::{from_fn, FromIterator},
4 };
5 
6 use indexmap::IndexSet;
7 
8 use 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 /// ```
36 pub 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>
43 where
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)]
105 mod 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 }
183