algorithms_fourth 0.1.10

//! 可检测负环的SP(最短路径)算法
//! # 使用
//!```
//!     use algorithms_fourth::{digraph::{edge_weighted::EdgeWeigtedDigraph, bellman_for_sp::BellmanFordSP}, add_edge_weighted_for_digraph};
//!         let mut g = EdgeWeigtedDigraph::new(8);
//!         add_edge_weighted_for_digraph!(g,4,5,0.35);
//!         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,7,5,0.28);
//!         add_edge_weighted_for_digraph!(g,5,1,0.32);
//!         add_edge_weighted_for_digraph!(g,0,4,0.38);
//!         add_edge_weighted_for_digraph!(g,0,2,0.26);
//!         add_edge_weighted_for_digraph!(g,7,3,0.39);
//!         add_edge_weighted_for_digraph!(g,1,3,0.29);
//!         add_edge_weighted_for_digraph!(g,2,7,0.34);
//!         add_edge_weighted_for_digraph!(g,6,2,-1.20);
//!         add_edge_weighted_for_digraph!(g,3,6,0.52);
//!         add_edge_weighted_for_digraph!(g,6,0,-1.40);
//!         add_edge_weighted_for_digraph!(g,6,4,-1.25);
//!         let sp = BellmanFordSP::new(&g, 0);
//!         assert!(!sp.has_negative_cycle());
//!         assert!(sp.has_path_to(4));
//!         assert_eq!(sp.dist_to(4) as f32,0.26);
//!         for e in sp.path_to(4).unwrap(){
//!            println!("{:?}",e) ;
//!         }
//!         let mut g = EdgeWeigtedDigraph::new(8);
//!         add_edge_weighted_for_digraph!(g,4,5,0.35);
//!         add_edge_weighted_for_digraph!(g,5,4,-0.66);
//!         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,7,5,0.28);
//!         add_edge_weighted_for_digraph!(g,5,1,0.32);
//!         add_edge_weighted_for_digraph!(g,0,4,0.38);
//!         add_edge_weighted_for_digraph!(g,0,2,0.26);
//!         add_edge_weighted_for_digraph!(g,7,3,0.39);
//!         add_edge_weighted_for_digraph!(g,1,3,0.29);
//!         add_edge_weighted_for_digraph!(g,2,7,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);
//!         let sp = BellmanFordSP::new(&g,0);
//!         assert!(sp.has_negative_cycle());
//!         for  e in sp.negative_cycle().as_ref().unwrap(){
//!            println!("{:?}",e);
//!         }
//! ```
use std::{cell::RefCell, collections::VecDeque};

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

pub struct BellmanFordSP<'a> {
    /// 从起点到某个顶点的路径长度
    dist_to: Vec<Weight>,
    /// 从起点到某个顶点的最后一条边
    edge_to: Vec<Option<&'a DirectedEdge>>,
    /// 该顶点是否存在于队列中
    on_q: Vec<bool>,
    /// 正在被放松的顶点
    queue: VecDeque<usize>,
    /// relax()的调用次数
    cost: usize,
    cycler: RefCell<Option<Vec<DirectedEdge>>>,
}
impl<'a> BellmanFordSP<'a> {
    pub fn new(g: &'a EdgeWeigtedDigraph, s: usize) -> Self {
        let dist_to = vec![Weight::MAX; g.vertex_count()];
        let mut edge_to = Vec::with_capacity(g.vertex_count());
        for _ in 0..g.vertex_count() {
            edge_to.push(None);
        }
        let on_q = vec![false; g.vertex_count()];
        let cost = 0;
        let mut sp = BellmanFordSP {
            dist_to,
            edge_to,
            on_q,
            queue: VecDeque::new(),
            cost,
            cycler: RefCell::from(None),
        };
        sp.dist_to[s] = 0.0;
        sp.queue.push_back(s);
        while let Some(v) = sp.queue.pop_front() {
            sp.on_q[v] = true;
            sp.relax(g, v);
            if sp.has_negative_cycle() {
                break;
            }
        }
        sp
    }

    pub fn has_negative_cycle(&self) -> bool {
        self.cycler.borrow().is_some()
    }

    /// 原则上，每遍历一轮就检查有无负环，但是无法简洁准确的标记每一轮结束。
    /// 根据每一轮表示遍历完所有顶点，这里粗略以遍历的顶点数为总顶点数的倍数来表示一轮
    /// 关键是要证明放松后，队列中如果存在环则一定是负权重环
    /// ## 证明
    /// 放松的的规则是权重比较，假设当前要放松的边是环的最后一条边。那么只有负权重环的情况下，
    /// 这条边才会符合放松规则而被加入最短路径队列中。
    fn relax(&mut self, g: &'a EdgeWeigtedDigraph, v: usize) {
        for e in g.adj(v) {
            let w = e.to();
            let weight = self.dist_to[v] + e.weight();
            if self.dist_to[w] > weight {
                self.dist_to[w] = weight;
                self.edge_to[w] = Some(e);
                if !self.on_q[w] {
                    self.queue.push_back(w);
                    self.on_q[w] = true;
                }
            }
            self.cost += 1;
            if self.cost % g.vertex_count() == 0 {
                self.find_negative_cycle();
            }
        }
    }

    fn find_negative_cycle(&'a self) {
        let count = self.edge_to.len();
        let mut spt = EdgeWeigtedDigraph::new(count);
        for v in 0..count {
            if let Some(e) = self.edge_to[v] {
                spt.add_edge(e.clone());
            }
        }
        let finder = EdgeWeightedDirectedCycle::new(&spt);
        *self.cycler.borrow_mut() = finder.cycle();
    }
    pub fn dist_to(&self, v: usize) -> Weight {
        self.dist_to[v]
    }
    pub fn has_path_to(&self, v: usize) -> bool {
        self.edge_to[v].is_some()
    }
    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
        }
    }
    pub fn negative_cycle(&self) -> std::cell::Ref<'_, Option<Vec<DirectedEdge>>> {
        self.cycler.borrow()
    }
}
/// # todo
///  存在性能浪费。因为没有借阅关系的图结构，所以用了多次拷贝。
/// 等待进一步了解语法，可以用同一套代码同时实现借阅和所有权图时，
/// 再做优化
pub struct EdgeWeightedDirectedCycle<'a> {
    marked: Vec<bool>,
    edge_to: Vec<Option<&'a DirectedEdge>>,
    on_stack: Vec<bool>,
    cycle: Option<Vec<DirectedEdge>>,
}
impl<'a> EdgeWeightedDirectedCycle<'a> {
    pub fn new(g: &'a EdgeWeigtedDigraph) -> Self {
        let marked = vec![false; g.vertex_count()];
        let on_stack = vec![false; g.vertex_count()];
        let mut edge_to = Vec::with_capacity(g.vertex_count());
        for _ in 0..g.vertex_count() {
            edge_to.push(None);
        }
        let cycle = None;
        let mut finder = EdgeWeightedDirectedCycle {
            marked,
            on_stack,
            edge_to,
            cycle,
        };
        for v in 0..g.vertex_count() {
            if !finder.marked[v] {
                finder.dfs(g, v);
            }
        }
        finder.check();
        finder
    }

    fn dfs(&mut self, g: &'a EdgeWeigtedDigraph, v: usize) {
        self.on_stack[v] = true;
        self.marked[v] = true;
        for e in g.adj(v) {
            if self.cycle.is_some() {
                return;
            }
            let w = e.to();
            if !self.marked[w] {
                self.edge_to[w] = Some(e);
                self.dfs(g, w);
            } else if self.on_stack[w] {
                let mut cycle = Vec::new();
                let mut f = e;
                while f.from() != w {
                    cycle.push(f.clone());
                    f = self.edge_to[f.from()].unwrap();
                }
                cycle.push(f.clone());
                cycle.reverse();
                self.cycle = Some(cycle);
                return;
            }
        }
        self.on_stack[v] = false;
    }
    pub fn has_cycle(&self) -> bool {
        self.cycle.is_some()
    }
    pub fn cycle(self) -> Option<Vec<DirectedEdge>> {
        self.cycle
    }
    pub fn check(&self) {
        if self.has_cycle() {
            let mut first = None;
            let mut last: Option<&DirectedEdge> = None;
            for e in self.cycle.as_deref().unwrap() {
                if first.is_none() {
                    first = Some(e);
                }
                if let Some(last) = last {
                    if last.to() != e.from() {
                        panic!("相邻边没有连接: {:?}  {:?}\n", last, e);
                    }
                }
                last = Some(e);
            }
            if let (Some(first), Some(last)) = (first, last) {
                if first.from() != last.to() {
                    panic!("最后一条边与第一条边没有连接 :{:?}  {:?} \n", last, first)
                }
            } else {
                panic!("环至少有两条边\n");
            }
        }
    }
}
#[cfg(test)]
mod test {

    use crate::{
        add_edge_weighted_for_digraph,
        digraph::{bellman_for_sp::BellmanFordSP, edge_weighted::EdgeWeigtedDigraph},
    };

    #[test]
    fn test() {
        let mut g = EdgeWeigtedDigraph::new(8);
        add_edge_weighted_for_digraph!(g, 4, 5, 0.35);
        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, 7, 5, 0.28);
        add_edge_weighted_for_digraph!(g, 5, 1, 0.32);
        add_edge_weighted_for_digraph!(g, 0, 4, 0.38);
        add_edge_weighted_for_digraph!(g, 0, 2, 0.26);
        add_edge_weighted_for_digraph!(g, 7, 3, 0.39);
        add_edge_weighted_for_digraph!(g, 1, 3, 0.29);
        add_edge_weighted_for_digraph!(g, 2, 7, 0.34);
        add_edge_weighted_for_digraph!(g, 6, 2, -1.20);
        add_edge_weighted_for_digraph!(g, 3, 6, 0.52);
        add_edge_weighted_for_digraph!(g, 6, 0, -1.40);
        add_edge_weighted_for_digraph!(g, 6, 4, -1.25);
        let sp = BellmanFordSP::new(&g, 0);
        assert!(!sp.has_negative_cycle());
        assert!(sp.has_path_to(4));
        assert_eq!(sp.dist_to(4) as f32, 0.26);
        for e in sp.path_to(4).unwrap() {
            println!("{:?}", e);
        }
        let mut g = EdgeWeigtedDigraph::new(8);
        add_edge_weighted_for_digraph!(g, 4, 5, 0.35);
        add_edge_weighted_for_digraph!(g, 5, 4, -0.66);
        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, 7, 5, 0.28);
        add_edge_weighted_for_digraph!(g, 5, 1, 0.32);
        add_edge_weighted_for_digraph!(g, 0, 4, 0.38);
        add_edge_weighted_for_digraph!(g, 0, 2, 0.26);
        add_edge_weighted_for_digraph!(g, 7, 3, 0.39);
        add_edge_weighted_for_digraph!(g, 1, 3, 0.29);
        add_edge_weighted_for_digraph!(g, 2, 7, 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);
        let sp = BellmanFordSP::new(&g, 0);
        assert!(sp.has_negative_cycle());
        for e in sp.negative_cycle().as_ref().unwrap() {
            println!("{:?}", e);
        }
    }
}