algorithms_fourth 0.1.10

//! Kruskal
//!
//! ## 思路
//! 两个最小生成树用最小权重边关联，则形成新的最小生成树。
//! 所以，边优先级排序，凡是优先级最高且两个端点属于不同最小生成子树的边一定是目标边
//!
//! ## 使用
//!
//! ```
//!    use algorithms_fourth::{
//!        add_edge_weighted,
//!        graph::edge_weighted::{mst::kruskal::Kruskal, EdgeWeightedGraph},
//!    };
//!
//!     let mut g = EdgeWeightedGraph::new(8);
//!     add_edge_weighted!(g, 4, 5, 0.35);
//!     add_edge_weighted!(g, 4, 7, 0.37);
//!     add_edge_weighted!(g, 5, 7, 0.28);
//!     add_edge_weighted!(g, 0, 7, 0.16);
//!     add_edge_weighted!(g, 1, 5, 0.32);
//!     add_edge_weighted!(g, 0, 4, 0.38);
//!     add_edge_weighted!(g, 2, 3, 0.17);
//!     add_edge_weighted!(g, 1, 7, 0.19);
//!     add_edge_weighted!(g, 0, 2, 0.26);
//!     add_edge_weighted!(g, 1, 2, 0.36);
//!     add_edge_weighted!(g, 1, 3, 0.29);
//!     add_edge_weighted!(g, 2, 7, 0.34);
//!     add_edge_weighted!(g, 6, 2, 0.40);
//!     add_edge_weighted!(g, 3, 6, 0.52);
//!     add_edge_weighted!(g, 6, 0, 0.58);
//!     add_edge_weighted!(g, 6, 4, 0.93);
//!     let kruskal = Kruskal::new(&g);
//!     let mut gg = EdgeWeightedGraph::new(g.vertex_count());
//!     for e in kruskal.edges() {
//!     let v = e.either();
//!     let w = e.other(v);
//!         add_edge_weighted!(gg, v, w, e.weight());
//!     }
//!     // gg.print_dot("mst1.dot");
//!     let weight = kruskal.weight();
//!     println!("weight:{}", weight as f32);
//! ```

use std::collections::VecDeque;

use crate::{
    graph::{
        connect::UF,
        edge_weighted::{Edge, EdgeWeightedGraph},
    },
    priority_queue::PQ,
};

pub struct Kruskal<'a> {
    mst: VecDeque<&'a Edge>,
}

impl<'a> Kruskal<'a> {
    pub fn new(g: &'a EdgeWeightedGraph) -> Self {
        let mst = VecDeque::new();
        let mut pq = PQ::new_min_pq();
        for e in g.edges() {
            pq.push(e);
        }
        let mut uf = UF::new(g.vertex_count());
        let mut kruskal = Kruskal { mst };
        while let Some(e) = pq.pop() {
            let v = e.either();
            let w = e.other(v);
            if !uf.connected(v, w) {
                uf.union(v, w);
                kruskal.mst.push_back(e);
                if kruskal.mst.len() == g.vertex_count() - 1 {
                    break;
                }
            }
        }
        kruskal
    }
    pub fn edges(&self) -> std::collections::vec_deque::Iter<'_, &Edge> {
        self.mst.iter()
    }
    pub fn weight(&self) -> f64 {
        self.edges().map(|e| e.weight()).sum()
    }
}

#[cfg(test)]
mod test {
    use crate::{
        add_edge_weighted,
        graph::edge_weighted::{mst::kruskal::Kruskal, EdgeWeightedGraph},
    };

    #[test]
    fn test() {
        let mut g = EdgeWeightedGraph::new(8);
        add_edge_weighted!(g, 4, 5, 0.35);
        add_edge_weighted!(g, 4, 7, 0.37);
        add_edge_weighted!(g, 5, 7, 0.28);
        add_edge_weighted!(g, 0, 7, 0.16);
        add_edge_weighted!(g, 1, 5, 0.32);
        add_edge_weighted!(g, 0, 4, 0.38);
        add_edge_weighted!(g, 2, 3, 0.17);
        add_edge_weighted!(g, 1, 7, 0.19);
        add_edge_weighted!(g, 0, 2, 0.26);
        add_edge_weighted!(g, 1, 2, 0.36);
        add_edge_weighted!(g, 1, 3, 0.29);
        add_edge_weighted!(g, 2, 7, 0.34);
        add_edge_weighted!(g, 6, 2, 0.40);
        add_edge_weighted!(g, 3, 6, 0.52);
        add_edge_weighted!(g, 6, 0, 0.58);
        add_edge_weighted!(g, 6, 4, 0.93);
        let kruskal = Kruskal::new(&g);
        let mut gg = EdgeWeightedGraph::new(g.vertex_count());
        for e in kruskal.edges() {
            add_edge_weighted!(gg, e.v, e.w, e.weight);
        }
        // gg.print_dot("mst1.dot");
        let weight = kruskal.weight();
        println!("weight:{}", weight as f32);
    }
}