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