rs_graph/
search.rs

1/*
2 * Copyright (c) 2019 Frank Fischer <frank-fischer@shadow-soft.de>
3 *
4 * This program is free software: you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License as
6 * published by the Free Software Foundation, either version 3 of the
7 * License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
16 */
17
18//! # Graph search algorithms.
19//!
20//! This module contains several standard search algorithms on graphs. These are
21//! algorithms that visit the nodes of a graph in some specific order.
22//!
23//! All search algorithms are implemented as iterators. The iterators produce a
24//! sequence of nodes (together with algorithm specific additional information)
25//! in the order in which they are visited by the particular search strategy.
26//! This allows search algorithms to be used on infinite graphs (represented by
27//! implementors of [`Adjacencies`][crate::adjacencies::Adjacencies]), in which
28//! case the iterator is infinite.
29
30pub mod astar;
31pub mod bfs;
32pub mod biastar;
33pub mod dfs;
34
35use std::iter::Iterator;
36use std::marker::PhantomData;
37
38/// Compute a path from a map of incoming edges for each node.
39///
40/// # Parameters
41/// - `dst`: the destination node
42/// - `incomings(v)`: return the incoming edge and preceding node for node `v`
43///   (or `None` if it does not exist)
44///
45/// # Return
46/// An iterator over the incoming edges starting from the last one.
47///
48/// # Example
49///
50/// ```
51/// // Breadth-first-search on a directed with 7 nodes.
52///
53/// use rs_graph::LinkedListGraph;
54/// use rs_graph::traits::*;
55/// use rs_graph::classes;
56/// use rs_graph::search::{path_from_incomings, bfs};
57/// use std::collections::{HashMap, VecDeque};
58///
59/// let g: LinkedListGraph = classes::cycle(7);
60///
61/// let mut incomings = HashMap::new();
62/// let mut bfs = bfs::start_with_data(g.outgoing(), g.id2node(0), (&mut incomings, VecDeque::new()));
63/// for _ in bfs {}
64///
65/// {
66///     let mut path = path_from_incomings(g.id2node(3), |u| incomings.get(&u).map(|&e| (e, g.src(e))));
67///
68///     assert_eq!(path.next().map(|e| g.edge_id(e)), Some(2));
69///     assert_eq!(path.next().map(|e| g.edge_id(e)), Some(1));
70///     assert_eq!(path.next().map(|e| g.edge_id(e)), Some(0));
71///     assert_eq!(path.next().map(|e| g.edge_id(e)), None);
72/// }
73///
74/// {
75///     let mut path = path_from_incomings(g.id2node(4), |u| incomings.get(&u).map(|&e| (e, g.src(e))));
76///
77///     assert_eq!(path.next().map(|e| g.edge_id(e)), Some(3));
78///     assert_eq!(path.next().map(|e| g.edge_id(e)), Some(2));
79///     assert_eq!(path.next().map(|e| g.edge_id(e)), Some(1));
80///     assert_eq!(path.next().map(|e| g.edge_id(e)), Some(0));
81///     assert_eq!(path.next().map(|e| g.edge_id(e)), None);
82/// }
83/// ```
84pub fn path_from_incomings<N, E, I>(dst: N, incomings: I) -> impl Iterator<Item = E>
85where
86    N: Copy,
87    E: Clone,
88    I: Fn(N) -> Option<(E, N)>,
89{
90    PathIter {
91        incomings,
92        u: dst,
93        phantom: PhantomData,
94    }
95}
96
97#[doc(hidden)]
98struct PathIter<N, E, I>
99where
100    I: Fn(N) -> Option<(E, N)>,
101{
102    incomings: I,
103    u: N,
104    phantom: PhantomData<E>,
105}
106
107impl<N, E, I> Iterator for PathIter<N, E, I>
108where
109    N: Clone,
110    I: Fn(N) -> Option<(E, N)>,
111{
112    type Item = E;
113
114    fn next(&mut self) -> Option<E> {
115        if let Some((e, v)) = (self.incomings)(self.u.clone()) {
116            self.u = v;
117            Some(e)
118        } else {
119            None
120        }
121    }
122}
rs_graph/search.rs

rs_graph/
search.rs
