algorithms_fourth 0.1.10

//! 拓扑排序
//! # 使用
//! ```
//!   use algorithms_fourth::add_edge;
//!   use algorithms_fourth::digraph::topological::Topological;
//!   use algorithms_fourth::digraph::Digraph;
//!         let mut g= Digraph::new(13);
//!       add_edge!(g,0,1,5,6);
//!       add_edge!(g,2,3,0);
//!       add_edge!(g,3,5);
//!       add_edge!(g,5,4);
//!       add_edge!(g,6,4,9);
//!       add_edge!(g,7,6);
//!       add_edge!(g,8,7);
//!       add_edge!(g,9,10,11,12);
//!       add_edge!(g,11,12);
//!       let topological = Topological::new(&g);
//!       assert_eq!(topological.is_directed_non_cycler(),true);
//!       println!("{:?}",topological.order());
//!
//! ```
//!/
use super::{cycle::DirectedCycler, depth_first_order::DepthFirstOrder, Digraph};

pub struct Topological {
    order: Option<Vec<usize>>,
}
impl Topological {
    pub fn new(g: &Digraph) -> Self {
        let cycle_finder = DirectedCycler::new(g);
        let order = if !cycle_finder.has_cycle() {
            let dfs = DepthFirstOrder::new(g);
            Some(dfs.reverse_post())
        } else {
            None
        };
        Topological { order }
    }
    pub fn order(&self) -> Option<std::iter::Rev<std::slice::Iter<'_, usize>>> {
        self.order.as_ref().map(|f| f.iter().rev())
    }
    pub fn is_directed_non_cycler(&self) -> bool {
        self.order.is_some()
    }
}
#[cfg(test)]
mod test {
    use crate::{add_edge, digraph::topological::Topological};

    use super::Digraph;

    #[test]
    fn test() {
        let mut g = Digraph::new(13);
        add_edge!(g, 0, 1, 5, 6);
        add_edge!(g, 2, 3, 0);
        add_edge!(g, 3, 5);
        add_edge!(g, 5, 4);
        add_edge!(g, 6, 4, 9);
        add_edge!(g, 7, 6);
        add_edge!(g, 8, 7);
        add_edge!(g, 9, 10, 11, 12);
        add_edge!(g, 11, 12);
        let topological = Topological::new(&g);
        assert_eq!(topological.is_directed_non_cycler(), true);
        println!("{:?}", topological.order());
    }
}