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