algorithms_fourth 0.1.10

//! 无环有向图的最短路径算法
//!
//! ## 思路
//! 最优的算法：如果遍历到一个节点时，节点的所有父节点都已经遍历，
//! 那么此时节点一定可以获取最短路径（权重）
//!
//! 而拓扑排序刚好提供了所需的节点遍历顺序
//!
//! ## 使用
//! ```
//!     use algorithms_fourth::{
//!         add_edge_weighted_for_digraph,
//!         digraph::{acyclic_sp::AcyclicSP, edge_weighted::EdgeWeigtedDigraph},
//!     };
//!
//!         let mut g = EdgeWeigtedDigraph::new(8);
//!         add_edge_weighted_for_digraph!(g, 5, 4, 0.35);
//!         add_edge_weighted_for_digraph!(g, 4, 7, 0.37);
//!         add_edge_weighted_for_digraph!(g, 5, 7, 0.28);
//!         add_edge_weighted_for_digraph!(g, 5, 1, 0.32);
//!         add_edge_weighted_for_digraph!(g, 4, 0, 0.38);
//!         add_edge_weighted_for_digraph!(g, 0, 2, 0.26);
//!         add_edge_weighted_for_digraph!(g, 3, 7, 0.39);
//!         add_edge_weighted_for_digraph!(g, 1, 3, 0.29);
//!         add_edge_weighted_for_digraph!(g, 7, 2, 0.34);
//!         add_edge_weighted_for_digraph!(g, 6, 2, 0.40);
//!         add_edge_weighted_for_digraph!(g, 3, 6, 0.52);
//!         add_edge_weighted_for_digraph!(g, 6, 0, 0.58);
//!         add_edge_weighted_for_digraph!(g, 6, 4, 0.93);
//!         if false {
//!             g.print_dot("e.dot");
//!         }
//!         let sp = AcyclicSP::new(&g, 5);
//!         assert_eq!(sp.dist_to(6), 1.13);
//!         assert_eq!(sp.dist_to(4), 0.35);
//!         assert_eq!(sp.dist_to(2) as f32, 0.62);
//!         for e in sp.path_to(2).unwrap(){
//!             println!("{:?}",e);
//!         }
//!
//! ```
use crate::generate_vec_with;

use super::{
    edge_weighted::{DirectedEdge, EdgeWeigtedDigraph, Weight},
    topological::Topological,
};

pub struct AcyclicSP<'a> {
    edge_to: Vec<Option<&'a DirectedEdge>>,
    dist_to: Vec<Weight>,
}
impl<'a> AcyclicSP<'a> {
    pub fn new(g: &'a EdgeWeigtedDigraph, s: usize) -> Self {
        let edge_to = generate_vec_with!(None, g.vertex_count());
        let dist_to = vec![Weight::MAX; g.vertex_count()];
        let mut sp = AcyclicSP { edge_to, dist_to };
        sp.dist_to[s] = 0.0;
        //    权宜之计，因为Topological 依赖于Digraph,Digraph 暂时与EdgeWeightedDigraph的没有统一的trait
        let top = Topological::new(&g.convert_to_digraph());
        for v in top.order().unwrap() {
            sp.relax(g, *v);
        }
        sp
    }

    fn relax(&mut self, g: &'a EdgeWeigtedDigraph, v: usize) {
        for e in g.adj(v) {
            let w = e.to();
            let p = self.dist_to[v] + e.weight();
            if self.dist_to[w] > p {
                self.dist_to[w] = p;
                self.edge_to[w] = Some(e);
            }
        }
    }
    pub fn dist_to(&self, v: usize) -> Weight {
        self.dist_to[v]
    }
    pub fn has_path_to(&self, v: usize) -> bool {
        self.dist_to(v) < Weight::MAX
    }
    pub fn path_to(&self, v: usize) -> Option<std::iter::Rev<std::vec::IntoIter<&DirectedEdge>>> {
        if self.has_path_to(v) {
            let mut path = Vec::new();
            let mut c = self.edge_to.get(v);
            while let Some(&Some(e)) = c {
                path.push(e);
                c = self.edge_to.get(e.from());
            }
            Some(path.into_iter().rev())
        } else {
            None
        }
    }
}
#[cfg(test)]
mod test {
    use crate::{
        add_edge_weighted_for_digraph,
        digraph::{acyclic_sp::AcyclicSP, edge_weighted::EdgeWeigtedDigraph},
    };

    #[test]
    fn test() {
        let mut g = EdgeWeigtedDigraph::new(8);
        add_edge_weighted_for_digraph!(g, 5, 4, 0.35);
        add_edge_weighted_for_digraph!(g, 4, 7, 0.37);
        add_edge_weighted_for_digraph!(g, 5, 7, 0.28);
        add_edge_weighted_for_digraph!(g, 5, 1, 0.32);
        add_edge_weighted_for_digraph!(g, 4, 0, 0.38);
        add_edge_weighted_for_digraph!(g, 0, 2, 0.26);
        add_edge_weighted_for_digraph!(g, 3, 7, 0.39);
        add_edge_weighted_for_digraph!(g, 1, 3, 0.29);
        add_edge_weighted_for_digraph!(g, 7, 2, 0.34);
        add_edge_weighted_for_digraph!(g, 6, 2, 0.40);
        add_edge_weighted_for_digraph!(g, 3, 6, 0.52);
        add_edge_weighted_for_digraph!(g, 6, 0, 0.58);
        add_edge_weighted_for_digraph!(g, 6, 4, 0.93);
        if false {
            g.print_dot("e.dot");
        }
        let sp = AcyclicSP::new(&g, 5);
        assert_eq!(sp.dist_to(6), 1.13);
        assert_eq!(sp.dist_to(4), 0.35);
        assert_eq!(sp.dist_to(2) as f32, 0.62);
        for e in sp.path_to(2).unwrap() {
            println!("{:?}", e);
        }
    }
}