algorithms_fourth 0.1.10

//! 深度优先搜索的顶点排序
//!

use super::Digraph;

use std::collections::VecDeque;
/**
# 用法
```
use algorithms_fourth::digraph::Digraph;
use algorithms_fourth::digraph::depth_first_order::DepthFirstOrder;
let mut g = Digraph::new(4);
g.add_edge(0, 1);
g.add_edge(2, 3);
let dfo = DepthFirstOrder::new(&g);
assert_eq!(dfo.post(),vec![1,0,3,2]);
assert_eq!(dfo.pre(),vec![0,1,2,3]);
assert_eq!(dfo.reverse_post(),vec![1,0,3,2]);
```
*/
pub struct DepthFirstOrder {
    marked: Vec<bool>,
    /// 所有顶点的前序排列
    pre: VecDeque<usize>,
    /// 所有顶点的后序排列
    post: VecDeque<usize>,
    /// 所有顶点的逆后序排列
    reverse_post: Vec<usize>,
}
impl DepthFirstOrder {
    pub fn new(g: &Digraph) -> Self {
        let marked = vec![false; g.vertex_count()];
        let pre = VecDeque::new();
        let post = VecDeque::new();
        let reverse_post = Vec::new();
        let mut dfo = DepthFirstOrder {
            marked,
            pre,
            post,
            reverse_post,
        };
        for v in 0..g.vertex_count() {
            if !dfo.marked[v] {
                dfo.dfs(g, v);
            }
        }
        dfo
    }

    fn dfs(&mut self, g: &Digraph, v: usize) {
        self.pre.push_back(v);
        self.marked[v] = true;
        for w in g.adj(v) {
            if !self.marked[*w] {
                self.dfs(g, *w);
            }
        }
        self.post.push_back(v);
        self.reverse_post.push(v);
    }
    /// 所有顶点的前序排列
    pub fn pre(&self) -> Vec<usize> {
        self.pre.iter().copied().collect::<Vec<usize>>()
    }
    /// 所有顶点的后序排列
    pub fn post(&self) -> Vec<usize> {
        self.post.iter().copied().collect::<Vec<usize>>()
    }
    /// 所有顶点的逆后序排列
    /// # 使用
    /// ```
    /// use algorithms_fourth::digraph::Digraph;
    /// use algorithms_fourth::digraph::depth_first_order::DepthFirstOrder;
    /// let mut g = Digraph::new(4);
    /// g.add_edge(0, 1);
    /// g.add_edge(2, 3);
    /// let dfo = DepthFirstOrder::new(&g);
    /// assert_eq!(dfo.reverse_post(),vec![1,0,3,2]);
    ///   
    ///    let mut points = dfo.reverse_post();
    ///    while let Some(s) = points.pop() {
    ///         println!("{}",s);    
    /// }
    /// ```
    pub fn reverse_post(&self) -> Vec<usize> {
        self.reverse_post.to_vec()
    }
}
#[cfg(test)]
mod test {
    use crate::digraph::Digraph;

    use super::DepthFirstOrder;

    #[test]
    fn test() {
        let mut g = Digraph::new(4);
        g.add_edge(0, 1);
        g.add_edge(2, 3);
        let dfo = DepthFirstOrder::new(&g);
        assert_eq!(dfo.post(), vec![1, 0, 3, 2]);
        assert_eq!(dfo.pre(), vec![0, 1, 2, 3]);
        assert_eq!(dfo.reverse_post(), vec![1, 0, 3, 2]);
    }
}