algae_graph/search/
dfs.rs

1/*
2    Appellation: dfs <module>
3    Contrib: FL03 <jo3mccain@icloud.com>
4    Description: ... Summary ...
5*/
6use super::Searcher;
7use crate::{Contain, Graph, Node, Weight};
8
9#[derive(Clone, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
10pub struct DepthFirstSearch<N: Node> {
11    stack: Vec<N>,
12    visited: Vec<N>,
13}
14
15impl<N: Node> DepthFirstSearch<N> {
16    pub fn new() -> Self {
17        Self {
18            stack: Vec::new(),
19            visited: Vec::new(),
20        }
21    }
22}
23
24impl<N: Node> Contain<N> for DepthFirstSearch<N> {
25    fn contains(&self, elem: &N) -> bool {
26        self.visited.contains(elem)
27    }
28}
29
30impl<N, V> Searcher<N, V> for DepthFirstSearch<N>
31where
32    N: Node,
33    V: Weight,
34{
35    fn reset(&mut self) {
36        self.stack.clear();
37        self.visited.clear();
38    }
39
40    fn search(&mut self, graph: impl Graph<N, V>, start: N) -> Vec<N> {
41        self.stack.push(start);
42        while let Some(node) = self.stack.pop() {
43            if !self.visited.contains(&node) {
44                self.visited.push(node.clone());
45                if let Ok(neighbor) = graph.neighbors(node) {
46                    for (node, _) in neighbor {
47                        self.stack.push(node.clone());
48                    }
49                }
50            }
51        }
52        self.visited.clone()
53    }
54}
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59    use crate::{DirectedGraph, Edge};
60
61    const TEST_EDGES: [(&str, &str, usize); 5] = [
62        ("a", "b", 5),
63        ("c", "a", 7),
64        ("b", "c", 10),
65        ("d", "c", 10),
66        ("e", "f", 10),
67    ];
68
69    #[test]
70    fn test_dfs_directed() {
71        let mut graph = DirectedGraph::<&str, usize>::new();
72        for i in TEST_EDGES {
73            graph.add_edge(Edge::from(i));
74        }
75        //
76        let mut dfs = DepthFirstSearch::new();
77        //
78        dfs.search(graph, "a");
79        //
80        assert!(dfs.contains_all(["b", "c", "a"]));
81    }
82}
algae_graph/search/dfs.rs

algae_graph/search/
dfs.rs
