algorithms_fourth 0.1.10

//! 加权无向图
//! # 使用
//! ```
//!    use algorithms_fourth::graph::edge_weighted::{Edge, EdgeWeightedGraph };
//!    use algorithms_fourth::add_edge_weighted;
//!  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);
//!  //g.print_dot("edge_weighted_graph.dot");
//!  ```

use std::{fmt::Display, fs};
pub mod mst;
/// 带权重的边
#[derive(Clone)]
pub struct Edge {
    v: usize,
    w: usize,
    weight: f64,
}
impl Edge {
    pub fn new(v: usize, w: usize, weight: f64) -> Self {
        Edge { v, w, weight }
    }
    pub fn weight(&self) -> f64 {
        self.weight
    }
    pub fn either(&self) -> usize {
        self.v
    }
    pub fn other(&self, v: usize) -> usize {
        if self.v == v {
            self.w
        } else if self.w == v {
            self.v
        } else {
            panic!("Inconsistent edge")
        }
    }
}
impl Display for Edge {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{} - {} {}", self.v, self.w, self.weight)
    }
}
impl PartialEq for Edge {
    fn eq(&self, other: &Self) -> bool {
        self.weight == other.weight
    }
}
impl Eq for Edge {}
impl PartialOrd for Edge {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        self.weight.partial_cmp(&other.weight)
    }
}
pub struct EdgeWeightedGraph {
    vertex_count: usize,
    edge_count: usize,
    adj: Vec<Vec<Edge>>,
}
impl EdgeWeightedGraph {
    pub fn new(vertex_count: usize) -> Self {
        assert!(vertex_count > 0);
        let mut adj = Vec::with_capacity(vertex_count);
        for _ in 0..vertex_count {
            adj.push(Vec::new());
        }
        EdgeWeightedGraph {
            vertex_count,
            edge_count: 0,
            adj,
        }
    }

    fn edges(&self) -> Vec<&Edge> {
        let ans = self.adj.iter().flatten().collect::<Vec<&Edge>>();
        ans
    }
}
impl EdgeWeightedGraph {
    pub fn vertex_count(&self) -> usize {
        self.vertex_count
    }
    pub fn edge_count(&self) -> usize {
        self.edge_count
    }
    pub fn add_edge(&mut self, e: Edge) {
        let v = e.either();
        let w = e.other(v);
        self.adj[v].push(e.clone());
        self.adj[w].push(e);
        self.edge_count += 1;
    }
    fn adj(&self, v: usize) -> &Vec<Edge> {
        &self.adj[v]
    }
    /// 打印dot格式的图结构
    pub fn print_dot(&self, path: &str) {
        let mut graph = r#"graph{
            label="graph"
             bgcolor=grey
             shape=circle
             "#
        .to_string();
        for v in 0..self.vertex_count {
            for e in self.adj(v).clone() {
                let w = if e.w == v { e.v } else { e.w };
                if w > v {
                    graph.push_str(&format!("{} -- {}[label={}]\n", v, w, e.weight()));
                }
            }
        }
        graph.push('}');
        let _ = fs::write(path, graph);
    }
}
/// 向加权图中添加n条边
///
/// `g`:图
///
/// `x`:v
///
/// `y`:v对应的n个w
#[macro_export]
macro_rules! add_edge_weighted {
    // $(...),+ 包围起来，就可以匹配一个或多个用逗号隔开的表达式
    ($g:ident,$v:expr, $w:expr,$weight:expr) => {
        ($g.add_edge($crate::graph::edge_weighted::Edge::new($v, $w, $weight)))
    };
}
#[cfg(test)]
mod test {
    use crate::graph::edge_weighted::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);
        // g.print_dot("edge_weighted_graph.dot");
    }
}