rs_graph/search/
bfs.rs

1/*
2 * Copyright (c) 2017, 2018, 2020, 2021 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//! Breadth-first-search.
19//!
20//! # Example
21//!
22//! ```
23//! use rs_graph::LinkedListGraph;
24//! use rs_graph::traits::*;
25//! use rs_graph::classes;
26//! use rs_graph::search::bfs;
27//!
28//! let g: LinkedListGraph = classes::peterson();
29//! let mut cnt = 0;
30//! for (u, e) in bfs::start(g.neighbors(), g.id2node(0)) {
31//!     assert_ne!(g.node_id(u), 0);
32//!     cnt += 1;
33//! }
34//! assert_eq!(cnt, g.num_nodes() - 1);
35//! ```
36
37use crate::adjacencies::Adjacencies;
38use crate::collections::{ItemMap, ItemQueue};
39use crate::traits::GraphIterator;
40use std::collections::{HashMap, VecDeque};
41use std::hash::Hash;
42
43/// BFS iterator with default data structures.
44pub type BFSDefault<'a, A> = BFS<
45    'a,
46    A,
47    HashMap<<A as Adjacencies<'a>>::Node, <A as Adjacencies<'a>>::Edge>,
48    VecDeque<<A as Adjacencies<'a>>::Node>,
49>;
50
51/// The default data structures for BFS.
52pub type DefaultData<N, E> = (HashMap<N, E>, VecDeque<N>);
53
54/// Start and return a BFS iterator using default data structures.
55///
56/// This is a convenience wrapper around [`start_with_data`] using the default
57/// data structures [`DefaultData`].
58///
59/// # Parameter
60/// - `adj`: adjacency information for the graph
61/// - `src`: the source node at which the search should start.
62pub fn start<'a, A>(adj: A, src: A::Node) -> BFSDefault<'a, A>
63where
64    A: Adjacencies<'a>,
65    A::Node: Hash,
66{
67    start_with_data(adj, src, DefaultData::default())
68}
69
70/// Start and return a BFS iterator with user defined data structures.
71///
72/// The returned iterator traverses the edges in breadth-first order. The
73/// iterator returns the next node and its incoming edge.
74///
75/// Note that the start node is *not* returned by the iterator.
76///
77/// The algorithm requires a pair `(M, Q)` with `M` implementing [`ItemMap<Node,
78/// Edge>`][crate::collections::ItemMap], and `Q` implementing
79/// [`ItemQueue<Node>`][crate::collections::ItemQueue] as internal data
80/// structures. The map is used to store the last edge of the path from the
81/// source to each reachable node. The queue is used to handle the nodes in
82/// breadth-first order. The data structures can be reused for multiple
83/// searches.
84///
85/// # Parameter
86/// - `adj`: adjacency information for the graph
87/// - `src`: the source node at which the search should start.
88/// - `data`: the data structures used in the algorithm
89///
90/// # Example
91///
92/// ```
93/// use rs_graph::LinkedListGraph;
94/// use rs_graph::traits::*;
95/// use rs_graph::classes;
96/// use rs_graph::search::bfs;
97/// use std::collections::{HashMap, VecDeque};
98///
99/// let g: LinkedListGraph = classes::peterson();
100/// let mut cnt = 0;
101/// for (u, e) in bfs::start_with_data(g.neighbors(), g.id2node(0),
102///                                    (HashMap::new(), VecDeque::new()))
103/// {
104///     assert_ne!(g.node_id(u), 0);
105///     cnt += 1;
106/// }
107/// assert_eq!(cnt, g.num_nodes() - 1);
108/// ```
109pub fn start_with_data<'a, A, S, Q>(adj: A, src: A::Node, data: (S, Q)) -> BFS<'a, A, S, Q>
110where
111    A: Adjacencies<'a>,
112    S: ItemMap<A::Node, A::Edge>,
113    Q: ItemQueue<A::Node>,
114{
115    let (mut seen, mut queue) = data;
116    queue.clear();
117    seen.clear();
118    let it = adj.neigh_iter(src);
119
120    BFS {
121        adj,
122        src,
123        seen,
124        queue,
125        it,
126    }
127}
128
129/// The BFS iterator.
130pub struct BFS<'a, A, S, Q>
131where
132    A: Adjacencies<'a>,
133    S: ItemMap<A::Node, A::Edge>,
134    Q: ItemQueue<A::Node>,
135{
136    adj: A,
137    src: A::Node,
138    seen: S,
139    queue: Q,
140    it: A::IncidenceIt,
141}
142
143impl<'a, A, S, Q> Iterator for BFS<'a, A, S, Q>
144where
145    A: Adjacencies<'a>,
146    S: ItemMap<A::Node, A::Edge>,
147    Q: ItemQueue<A::Node>,
148{
149    type Item = (A::Node, A::Edge);
150
151    fn next(&mut self) -> Option<Self::Item> {
152        loop {
153            while let Some((e, v)) = self.it.next(&self.adj) {
154                if v != self.src && self.seen.insert(v, e) {
155                    self.queue.push(v);
156                    return Some((v, e));
157                }
158            }
159            if let Some(u) = self.queue.pop() {
160                self.it = self.adj.neigh_iter(u);
161            } else {
162                return None;
163            }
164        }
165    }
166}
167
168impl<'a, A, S, Q> BFS<'a, A, S, Q>
169where
170    A: Adjacencies<'a>,
171    S: ItemMap<A::Node, A::Edge>,
172    Q: ItemQueue<A::Node>,
173{
174    /// Run the bfs completely.
175    ///
176    /// Note that this method may run forever on an infinite graph.
177    pub fn run(&mut self) {
178        while self.next().is_some() {}
179    }
180
181    /// Return the data structures used in the search.
182    pub fn into_data(self) -> (S, Q) {
183        (self.seen, self.queue)
184    }
185
186    /// Return the incoming edge of a node.
187    pub fn incoming_edge(&self, u: A::Node) -> Option<A::Edge> {
188        self.seen.get(u).cloned()
189    }
190}
rs_graph/search/bfs.rs

rs_graph/search/
bfs.rs
