rs_graph/search/
dfs.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//! Depth-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::dfs;
27//!
28//! let g: LinkedListGraph = classes::peterson();
29//! let mut cnt = 0;
30//! for (u, e) in dfs::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, ItemStack};
39use crate::traits::GraphIterator;
40use std::collections::HashMap;
41use std::hash::Hash;
42use std::marker::PhantomData;
43
44/// DFS iterator with default data structures.
45pub type DFSDefault<'a, A> = DFS<
46    'a,
47    A,
48    HashMap<<A as Adjacencies<'a>>::Node, <A as Adjacencies<'a>>::Edge>,
49    Vec<<A as Adjacencies<'a>>::IncidenceIt>,
50>;
51
52pub type DefaultData<N, E, I> = (HashMap<N, E>, Vec<I>);
53
54/// Start and return a DFS 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) -> DFSDefault<'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 DFS iterator with user defined data structures.
71///
72/// The returned iterator traverses the edges in depth-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, S)` with `M` implementing [`ItemMap<Node,
78/// Edge>`][crate::collections::ItemMap], and `S` implementing
79/// [`ItemStack<_>`][crate::collections::ItemStack] 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 stack is used to handle the nodes in
82/// depth-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::dfs;
97/// use std::collections::HashMap;
98///
99/// let g: LinkedListGraph = classes::peterson();
100/// let mut cnt = 0;
101/// for (u, e) in dfs::start_with_data(g.neighbors(), g.id2node(0),
102///                                    (HashMap::new(), Vec::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, St>(adj: A, src: A::Node, data: (S, St)) -> DFS<'a, A, S, St>
110where
111    A: Adjacencies<'a>,
112    S: ItemMap<A::Node, A::Edge>,
113    St: ItemStack<A::IncidenceIt>,
114{
115    let (mut seen, mut stack) = data;
116    seen.clear();
117    stack.clear();
118
119    stack.push(adj.neigh_iter(src));
120
121    DFS {
122        adj,
123        src,
124        seen,
125        stack,
126        phantom: PhantomData,
127    }
128}
129
130pub struct DFS<'a, A, S, St>
131where
132    A: Adjacencies<'a>,
133    S: ItemMap<A::Node, A::Edge>,
134    St: ItemStack<A::IncidenceIt>,
135{
136    adj: A,
137    src: A::Node,
138    seen: S,
139    stack: St,
140    phantom: PhantomData<&'a ()>,
141}
142
143impl<'a, A, S, St> Iterator for DFS<'a, A, S, St>
144where
145    A: Adjacencies<'a>,
146    S: ItemMap<A::Node, A::Edge>,
147    St: ItemStack<A::IncidenceIt>,
148{
149    type Item = (A::Node, A::Edge);
150
151    fn next(&mut self) -> Option<Self::Item> {
152        while let Some(mut it) = self.stack.pop() {
153            if let Some((e, v)) = it.next(&self.adj) {
154                self.stack.push(it);
155                if v != self.src && self.seen.insert(v, e) {
156                    self.stack.push(self.adj.neigh_iter(v));
157                    return Some((v, e));
158                }
159            }
160        }
161        None
162    }
163}
164
165impl<'a, A, S, St> DFS<'a, A, S, St>
166where
167    A: Adjacencies<'a>,
168    S: ItemMap<A::Node, A::Edge>,
169    St: ItemStack<A::IncidenceIt>,
170{
171    /// Run the dfs completely.
172    ///
173    /// Note that this method may run forever on an infinite graph.
174    pub fn run(&mut self) {
175        while self.next().is_some() {}
176    }
177
178    /// Return the data structures used in the search.
179    pub fn into_data(self) -> (S, St) {
180        (self.seen, self.stack)
181    }
182
183    /// Return the incoming edge of a node.
184    pub fn incoming_edge(&self, u: A::Node) -> Option<A::Edge> {
185        self.seen.get(u).cloned()
186    }
187}
rs_graph/search/dfs.rs

rs_graph/search/
dfs.rs
