algorithms_fourth 0.1.10

use super::Graph;

/// 检测图是否存在环
///
/// # 检测方法
/// 深度优先遍历，只要遇到一个节点已遍历过，且该节点不是它来自的节点，则说明必然存在环
/// ## 证明方法
/// 反证：如果一个图非环，那么它就是森林。深度优先遍历的情况下，一个节点遇到的已遍历节点
/// 只能是它的父节点。
pub struct Cycle {
    marked: Vec<bool>,
    has_cycle: bool,
}
impl Cycle {
    pub fn new(g: &Graph) -> Self {
        let marked = vec![false; g.vertex_count()];
        let mut cycle = Cycle {
            marked,
            has_cycle: false,
        };
        for v in 0..g.vertex_count() {
            if !cycle.marked[v] {
                cycle.dfs(g, v, v);
            }
            if cycle.has_cycle {
                break;
            }
        }
        cycle
    }
    /// `v`:下一个要遍历的节点
    ///
    /// `p`:v来自的节点
    fn dfs(&mut self, g: &Graph, v: usize, p: usize) {
        self.marked[v] = true;
        for w in g.adj(v).clone() {
            if !self.marked[w] {
                self.dfs(g, w, v);
            } else if w != p {
                self.has_cycle = true;
                break;
            }
        }
    }
    pub fn has_cycle(&self) -> bool {
        self.has_cycle
    }
}
#[cfg(test)]
mod test {
    use crate::{
        add_edge,
        graph::{cycle::Cycle, Graph},
    };

    #[test]
    fn test() {
        let mut g = Graph::new(5);
        add_edge!(g, 0, 1, 2, 3, 4);
        let cycle = Cycle::new(&g);
        assert_eq!(cycle.has_cycle(), false);
        add_edge!(g, 1, 4);
        let cycle = Cycle::new(&g);
        assert_eq!(cycle.has_cycle(), true);
    }
}