algorithms_fourth 0.1.10

//! 深度优先搜索
//!
//! ## 使用
//! ```
//! use algorithms_fourth::graph::depth_first_search::DepthFirstSearch;
//! use algorithms_fourth::graph::Graph;
//! use crate::algorithms_fourth::graph::Path;
//!use crate::algorithms_fourth::graph::Search;
//!
//!        let mut g = Graph::new(10);
//!        g.add_edge(0, 1);
//!        g.add_edge(3, 1);
//!        g.add_edge(1, 4);
//!        g.add_edge(3, 4);
//!        let search = DepthFirstSearch::new(&g, 0);
//!        if false {
//!             search.print_dot("dfs.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_eq!(
//!            search.path_to(3).unwrap().collect::<Vec<usize>>(),
//!            vec![3, 1, 0]
//!        );
//!        assert!(search.path_to(2).is_none());
//!        assert_eq!(
//!            search.path_to(4).unwrap().collect::<Vec<usize>>(),
//!            vec![4, 3, 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 DepthFirstSearch {
    marked: Vec<bool>,
    edge_to: Vec<usize>,
    s: usize,
    count: usize,
}
impl DepthFirstSearch {
    /// Creates a new [`DepthFirstSearch`].
    pub fn new(g: &Graph, s: usize) -> Self {
        let marked: Vec<bool> = vec![false; g.vertex_count()];
        let count = 0;
        let edge_to = vec![usize::MAX; g.vertex_count()];
        let mut search = DepthFirstSearch {
            s,
            marked,
            count,
            edge_to,
        };
        search.dfs(g, s);
        search
    }

    /// 深度优先搜索逻辑
    fn dfs(&mut self, g: &Graph, v: usize) {
        self.marked[v] = true;
        self.count += 1;
        let a = g.adj(v).iter();
        let mut a = a.collect::<Vec<&usize>>();
        a.sort();
        for w in a {
            if !self.marked[*w] {
                self.edge_to[*w] = v;
                self.dfs(g, *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 DepthFirstSearch {
    fn marked(&self, v: usize) -> bool {
        self.marked[v]
    }

    fn count(&self) -> usize {
        self.count
    }
}
impl Path for DepthFirstSearch {
    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::DepthFirstSearch;

    #[test]
    fn test() {
        let mut g = Graph::new(10);
        g.add_edge(0, 1);
        g.add_edge(3, 1);
        g.add_edge(1, 4);
        g.add_edge(3, 4);
        let search = DepthFirstSearch::new(&g, 0);
        // search.print_dot("dfs.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_eq!(
            search.path_to(3).unwrap().collect::<Vec<usize>>(),
            vec![3, 1, 0]
        );
        assert!(search.path_to(2).is_none());
        assert_eq!(
            search.path_to(4).unwrap().collect::<Vec<usize>>(),
            vec![4, 3, 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]);
    }
}