algae_graph/search/
bfs.rs

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

algae_graph/search/
bfs.rs
