petgraph/algo/
simple_paths.rs

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

petgraph/algo/
simple_paths.rs
