algorithms_fourth 0.1.10

//! 广度优先搜索
//!
//! ## 使用
//! ```
//!
//!    use algorithms_fourth::graph::{Graph, Path, Search,breadth_first_search::BreadthFirstSearch};
//!
//!    let mut g = Graph::new(10);
//!    g.add_edge(0, 1);
//!    g.add_edge(1, 4);
//!    g.add_edge(3, 1);
//!    g.add_edge(3, 4);
//!    let search = BreadthFirstSearch::new(&g, 0);
//!    if false {
//!   search.print_dot("bfs.dot");
//! }
//!    assert_eq!(search.marked(4), true);
//!    assert_eq!(search.count(), 4);
//!    assert_ne!(search.has_path_to(2), true);
//!    assert_eq!(search.has_path_to(4), true);
//!    assert!(search.path_to(2).is_none());
//!    assert_eq!(
//!        search.path_to(3).unwrap().collect::<Vec<usize>>(),
//!        vec![3, 1, 0]
//!    );
//!    assert_eq!(
//!        search.path_to(4).unwrap().collect::<Vec<usize>>(),
//!        vec![4, 1, 0]
//!    );
//!    assert_eq!(
//!        search.path_to(1).unwrap().collect::<Vec<usize>>(),
//!        vec![1, 0]
//!    );
//!    assert_eq!(search.path_to(0).unwrap().collect::<Vec<usize>>(), vec![0]);
//!
//! ```
use std::fs;

use super::{Graph, Path, Search};

pub struct BreadthFirstSearch {
    marked: Vec<bool>,
    edge_to: Vec<usize>,
    s: usize,
    count: usize,
}
impl BreadthFirstSearch {
    pub fn new(g: &Graph, s: usize) -> Self {
        let mut marked = Vec::with_capacity(g.vertex_count());
        let mut edge_to = Vec::with_capacity(g.vertex_count());
        for _ in 0..g.vertex_count() {
            marked.push(false);
            edge_to.push(usize::MAX);
        }
        let count = 0;
        let mut bfs = BreadthFirstSearch {
            marked,
            edge_to,
            s,
            count,
        };
        bfs.bfs(g, s);
        bfs
    }

    fn bfs(&mut self, g: &Graph, s: usize) {
        let mut queue = std::collections::VecDeque::new();
        self.marked[s] = true;
        queue.push_back(s);
        while let Some(v) = queue.pop_front() {
            self.count += 1;
            for w in g.adj(v).clone() {
                if !self.marked[w] {
                    self.edge_to[w] = v;
                    self.marked[w] = true;
                    queue.push_back(w);
                }
            }
        }
    }
    /// 打印dot格式的图结构
    pub fn print_dot(&self, path: &str) {
        let mut graph = r#"digraph{
            label="graph"
             bgcolor=grey
             shape=circle
             "#
        .to_string();
        for (t, f) in self
            .edge_to
            .iter()
            .enumerate()
            .filter(|(_, w)| **w != usize::MAX)
        {
            graph.push_str(&format!("{} -> {}\n", f, t));
        }
        graph.push('}');
        let _ = fs::write(path, graph);
    }
}
impl Search for BreadthFirstSearch {
    fn marked(&self, v: usize) -> bool {
        self.marked[v]
    }

    fn count(&self) -> usize {
        self.count
    }
}
impl Path for BreadthFirstSearch {
    fn has_path_to(&self, v: usize) -> bool {
        self.marked(v)
    }

    fn path_to(&self, v: usize) -> Option<Box<dyn Iterator<Item = usize>>> {
        if !self.has_path_to(v) {
            return None;
        }
        let mut ans = Vec::new();
        let mut p = v;
        while p != self.s {
            ans.push(p);
            p = self.edge_to[p];
        }
        ans.push(self.s);
        Some(Box::new(ans.into_iter()))
    }
}
#[cfg(test)]
mod test {
    use crate::graph::{Graph, Path, Search};

    use super::BreadthFirstSearch;

    #[test]
    fn test() {
        let mut g = Graph::new(10);
        g.add_edge(0, 1);
        g.add_edge(1, 4);
        g.add_edge(3, 1);
        g.add_edge(3, 4);
        let search = BreadthFirstSearch::new(&g, 0);
        // search.print_dot("bfs.dot");
        assert_eq!(search.marked(4), true);
        assert_eq!(search.count(), 4);
        assert_ne!(search.has_path_to(2), true);
        assert_eq!(search.has_path_to(4), true);
        assert!(search.path_to(2).is_none());
        assert_eq!(
            search.path_to(3).unwrap().collect::<Vec<usize>>(),
            vec![3, 1, 0]
        );
        assert_eq!(
            search.path_to(4).unwrap().collect::<Vec<usize>>(),
            vec![4, 1, 0]
        );
        assert_eq!(
            search.path_to(1).unwrap().collect::<Vec<usize>>(),
            vec![1, 0]
        );
        assert_eq!(search.path_to(0).unwrap().collect::<Vec<usize>>(), vec![0]);
    }
}