pathfinding/directed/dfs.rs
1//! Compute a path using the [depth-first search
2//! algorithm](https://en.wikipedia.org/wiki/Depth-first_search).
3
4use std::collections::HashSet;
5use std::hash::Hash;
6use std::iter::FusedIterator;
7
8use rustc_hash::{FxHashMap, FxHashSet};
9
10/// Compute a path using the [depth-first search
11/// algorithm](https://en.wikipedia.org/wiki/Depth-first_search).
12///
13/// The path starts from `start` up to a node for which `success`
14/// returns `true` is computed and returned along with its total cost,
15/// in a `Some`. If no path can be found, `None` is returned instead.
16///
17/// - `start` is the starting node.
18/// - `successors` returns a list of successors for a given node, which will be tried in order.
19/// - `success` checks whether the goal has been reached. It is not a node as some problems require
20/// a dynamic solution instead of a fixed node.
21///
22/// A node will never be included twice in the path as determined by the `Eq` relationship.
23///
24/// The returned path comprises both the start and end node. Note that the start node ownership
25/// is taken by `dfs` as no clones are made.
26///
27/// # Example
28///
29/// We will search a way to get from 1 to 17 while only adding 1 or multiplying the number by
30/// itself.
31///
32/// If we put the adder first, an adder-only solution will be found:
33///
34/// ```
35/// use pathfinding::prelude::dfs;
36///
37/// assert_eq!(dfs(1, |&n| vec![n+1, n*n].into_iter().filter(|&x| x <= 17), |&n| n == 17),
38/// Some((1..18).collect()));
39/// ```
40///
41/// However, if we put the multiplier first, a shorter solution will be explored first:
42///
43/// ```
44/// use pathfinding::prelude::dfs;
45///
46/// assert_eq!(dfs(1, |&n| vec![n*n, n+1].into_iter().filter(|&x| x <= 17), |&n| n == 17),
47/// Some(vec![1, 2, 4, 16, 17]));
48/// ```
49pub fn dfs<N, FN, IN, FS>(start: N, mut successors: FN, mut success: FS) -> Option<Vec<N>>
50where
51 N: Clone + Eq + Hash,
52 FN: FnMut(&N) -> IN,
53 IN: IntoIterator<Item = N>,
54 FS: FnMut(&N) -> bool,
55{
56 let mut to_visit = vec![start];
57 let mut visited = FxHashSet::default();
58 let mut parents = FxHashMap::default();
59 while let Some(node) = to_visit.pop() {
60 if visited.insert(node.clone()) {
61 if success(&node) {
62 return Some(build_path(node, &parents));
63 }
64 for next in successors(&node)
65 .into_iter()
66 .collect::<Vec<_>>()
67 .into_iter()
68 .rev()
69 {
70 if !visited.contains(&next) {
71 parents.insert(next.clone(), node.clone());
72 to_visit.push(next);
73 }
74 }
75 }
76 }
77 None
78}
79
80fn build_path<N>(mut node: N, parents: &FxHashMap<N, N>) -> Vec<N>
81where
82 N: Clone + Eq + Hash,
83{
84 let mut path = vec![node.clone()];
85 while let Some(parent) = parents.get(&node).cloned() {
86 path.push(parent.clone());
87 node = parent;
88 }
89 path.into_iter().rev().collect()
90}
91
92/// Visit all nodes that are reachable from a start node. The node will be visited
93/// in DFS order, starting from the `start` node and following the order returned
94/// by the `successors` function.
95///
96/// # Examples
97///
98/// The iterator stops when there are no new nodes to visit:
99///
100/// ```
101/// use pathfinding::prelude::dfs_reach;
102///
103/// let all_nodes = dfs_reach(3, |_| (1..=5)).collect::<Vec<_>>();
104/// assert_eq!(all_nodes, vec![3, 1, 2, 4, 5]);
105/// ```
106///
107/// The iterator can be used as a generator. Here are for examples
108/// the multiples of 2 and 3 smaller than 15 (although not in
109/// natural order but in the order they are discovered by the DFS
110/// algorithm):
111///
112/// ```
113/// use pathfinding::prelude::dfs_reach;
114///
115/// let mut it = dfs_reach(1, |&n| vec![n*2, n*3].into_iter().filter(|&x| x < 15)).skip(1);
116/// assert_eq!(it.next(), Some(2)); // 1*2
117/// assert_eq!(it.next(), Some(4)); // (1*2)*2
118/// assert_eq!(it.next(), Some(8)); // ((1*2)*2)*2
119/// assert_eq!(it.next(), Some(12)); // ((1*2)*2)*3
120/// assert_eq!(it.next(), Some(6)); // (1*2)*3
121/// assert_eq!(it.next(), Some(3)); // 1*3
122/// // (1*3)*2 == 6 which has been seen already
123/// assert_eq!(it.next(), Some(9)); // (1*3)*3
124/// ```
125pub fn dfs_reach<N, FN, IN>(start: N, successors: FN) -> DfsReachable<N, FN>
126where
127 N: Eq + Hash + Clone,
128 FN: FnMut(&N) -> IN,
129 IN: IntoIterator<Item = N>,
130{
131 DfsReachable {
132 to_see: vec![start],
133 visited: HashSet::new(),
134 successors,
135 }
136}
137
138/// Struct returned by [`dfs_reach`].
139pub struct DfsReachable<N, FN> {
140 to_see: Vec<N>,
141 visited: HashSet<N>,
142 successors: FN,
143}
144
145impl<N, FN> DfsReachable<N, FN>
146where
147 N: Eq + Hash,
148{
149 /// Return a lower bound on the number of remaining reachable
150 /// nodes. Not all nodes are necessarily known in advance, and
151 /// new reachable nodes may be discovered while using the iterator.
152 pub fn remaining_nodes_low_bound(&self) -> usize {
153 self.to_see.iter().collect::<HashSet<_>>().len()
154 }
155}
156
157impl<N, FN, IN> Iterator for DfsReachable<N, FN>
158where
159 N: Eq + Hash + Clone,
160 FN: FnMut(&N) -> IN,
161 IN: IntoIterator<Item = N>,
162{
163 type Item = N;
164
165 fn next(&mut self) -> Option<Self::Item> {
166 let n = self.to_see.pop()?;
167 if self.visited.contains(&n) {
168 return self.next();
169 }
170 self.visited.insert(n.clone());
171 let mut to_insert = Vec::new();
172 for s in (self.successors)(&n) {
173 if !self.visited.contains(&s) {
174 to_insert.push(s.clone());
175 }
176 }
177 self.to_see.extend(to_insert.into_iter().rev());
178 Some(n)
179 }
180}
181
182impl<N, FN, IN> FusedIterator for DfsReachable<N, FN>
183where
184 N: Eq + Hash + Clone,
185 FN: FnMut(&N) -> IN,
186 IN: IntoIterator<Item = N>,
187{
188}