algorithms_fourth 0.1.10

//! 有向图的环检测
use std::slice::Iter;

use super::Digraph;
/// 有向图环检测
///
/// # 用法
///```
/// use algorithms_fourth::digraph::Digraph;

/// use algorithms_fourth::digraph::cycle::DirectedCycler;
///
///        let mut g = Digraph::new(6);
///        g.add_edge(0, 5);
///        g.add_edge(3, 5);
///        g.add_edge(4, 3);
///        g.add_edge(5, 4);
///        let dc = DirectedCycler::new(&g);
///        assert_eq!(dc.has_cycle(),true);
///        assert_eq!(dc.cycle().collect::<Vec<_>>(),vec![&3,&4,&5,&3]);
/// ```
pub struct DirectedCycler {
    marked: Vec<bool>,
    edge_to: Vec<usize>,
    cycle: Vec<usize>,
    on_stack: Vec<bool>,
}
impl DirectedCycler {
    pub fn new(g: &Digraph) -> Self {
        let on_stack = vec![false; g.vertex_count()];
        let marked = vec![false; g.vertex_count()];
        let edge_to = vec![usize::MAX; g.vertex_count()];
        let mut dc = DirectedCycler {
            marked,
            edge_to,
            cycle: Vec::new(),
            on_stack,
        };
        for v in 0..g.vertex_count() {
            if !dc.marked[v] {
                dc.dfs(g, v);
            }
        }
        dc
    }

    fn dfs(&mut self, g: &Digraph, v: usize) {
        self.on_stack[v] = true;
        self.marked[v] = true;
        for w in g.adj(v) {
            if self.has_cycle() {
                return;
            } else if !self.marked[*w] {
                self.edge_to[*w] = v;
                self.dfs(g, *w);
            } else if self.on_stack[*w] {
                let mut x = v;
                while x != *w {
                    if x == usize::MAX {
                        panic!("error:{:?} v:{},w:{}", self.cycle(), v, w)
                    }
                    self.cycle.push(x);
                    x = self.edge_to[x];
                }
                self.cycle.push(*w);
                self.cycle.push(v);
            }
        }
        self.on_stack[v] = false;
    }

    pub fn has_cycle(&self) -> bool {
        !self.cycle.is_empty()
    }
    pub fn cycle(&self) -> Iter<usize> {
        self.cycle.iter()
    }
}
#[cfg(test)]
mod test {
    use crate::digraph::Digraph;

    use super::DirectedCycler;

    #[test]
    fn test() {
        let mut g = Digraph::new(6);
        g.add_edge(0, 5);
        g.add_edge(3, 5);
        g.add_edge(4, 3);
        g.add_edge(5, 4);
        let dc = DirectedCycler::new(&g);
        assert_eq!(dc.has_cycle(), true);
        assert_eq!(dc.cycle().collect::<Vec<_>>(), vec![&3, &4, &5, &3]);
    }
}