algorithms_fourth 0.1.10

//! ## 加权有向图
//! ```
//!
//!     use algorithms_fourth::add_edge_weighted_for_digraph;
//!
//!     use algorithms_fourth::digraph::edge_weighted::{DirectedEdge, EdgeWeigtedDigraph};
//!
//!         let mut g = EdgeWeigtedDigraph::new(8);
//!         add_edge_weighted_for_digraph!(g,0,2,0.26);
//!         add_edge_weighted_for_digraph!(g,0,4,0.38);
//!         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,3,6,0.52);
//!         add_edge_weighted_for_digraph!(g,4,7,0.37);
//!         add_edge_weighted_for_digraph!(g,4,5,0.35);
//!         add_edge_weighted_for_digraph!(g,5,1,0.32);
//!         add_edge_weighted_for_digraph!(g,5,7,0.28);
//!         add_edge_weighted_for_digraph!(g,5,4,0.35);
//!         add_edge_weighted_for_digraph!(g,6,4,0.93);
//!         add_edge_weighted_for_digraph!(g,6,0,0.58);
//!         add_edge_weighted_for_digraph!(g,6,2,0.40);
//!         add_edge_weighted_for_digraph!(g,7,3,0.39);
//!         add_edge_weighted_for_digraph!(g,7,5,0.28);
//!         if false {
//!             g.print_dot("edge_weighted_for_digraph.dot");
//!         }
//! ```
use std::{fmt::Display, fs};

use super::Digraph;

pub type Weight = f64;
/// ## 有向图的权重边
/// ```
/// use algorithms_fourth::digraph::edge_weighted::DirectedEdge;
///         let edge = DirectedEdge::new(0,1,1.2);
///         assert_eq!(edge.to_string(),"0 -> 1 [label=1.2]".to_string());
///
/// ```

#[derive(Clone, Debug)]
pub struct DirectedEdge {
    /// 起点
    v: usize,
    /// 重点
    w: usize,
    weight: Weight,
}
impl DirectedEdge {
    pub fn new(v: usize, w: usize, weight: Weight) -> Self {
        DirectedEdge { v, w, weight }
    }
    /// 起点
    pub fn from(&self) -> usize {
        self.v
    }
    /// 终点
    pub fn to(&self) -> usize {
        self.w
    }
    pub fn weight(&self) -> f64 {
        self.weight
    }
}
impl Display for DirectedEdge {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(
            f,
            "{} -> {} [label={}]",
            self.from(),
            self.to(),
            self.weight()
        )
    }
}
type Bag<T> = Vec<T>;
pub struct EdgeWeigtedDigraph {
    vertex_count: usize,
    edge_count: usize,
    adj: Vec<Bag<DirectedEdge>>,
}
impl EdgeWeigtedDigraph {
    pub fn new(vertex_count: usize) -> Self {
        let mut adj = Vec::with_capacity(vertex_count);
        for _ in 0..vertex_count {
            adj.push(Bag::new());
        }
        EdgeWeigtedDigraph {
            vertex_count,
            edge_count: 0,
            adj,
        }
    }
    pub fn add_edge(&mut self, e: DirectedEdge) {
        self.adj[e.from()].push(e);
        self.edge_count += 1;
    }
    pub fn adj(&self, v: usize) -> std::slice::Iter<'_, DirectedEdge> {
        self.adj[v].iter()
    }
    pub fn edges(&self) -> Vec<&DirectedEdge> {
        self.adj.iter().flatten().collect()
    }
    pub fn vertex_count(&self) -> usize {
        self.vertex_count
    }
    pub fn edge_count(&self) -> usize {
        self.edge_count
    }

    pub(crate) fn convert_to_digraph(&self) -> super::Digraph {
        let mut g = Digraph::new(self.vertex_count());
        for e in self.edges() {
            g.add_edge(e.from(), e.to());
        }
        g
    }
}
impl EdgeWeigtedDigraph {
    /// 打印dot格式的图结构
    pub fn print_dot(&self, path: &str) {
        let mut graph = r#"digraph{
                label="graph"
                 bgcolor=grey
                 shape=circle
                 "#
        .to_string();
        for v in 0..self.vertex_count {
            for w in self.adj(v).clone() {
                graph.push_str(&w.to_string());
            }
        }
        graph.push('}');
        let _ = fs::write(path, graph);
    }
}

#[cfg(test)]
mod test {
    use crate::add_edge_weighted_for_digraph;

    use super::EdgeWeigtedDigraph;

    #[test]
    fn test() {
        let mut g = EdgeWeigtedDigraph::new(8);
        add_edge_weighted_for_digraph!(g, 0, 2, 0.26);
        add_edge_weighted_for_digraph!(g, 0, 4, 0.38);
        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, 3, 6, 0.52);
        add_edge_weighted_for_digraph!(g, 4, 7, 0.37);
        add_edge_weighted_for_digraph!(g, 4, 5, 0.35);
        add_edge_weighted_for_digraph!(g, 5, 1, 0.32);
        add_edge_weighted_for_digraph!(g, 5, 7, 0.28);
        add_edge_weighted_for_digraph!(g, 5, 4, 0.35);
        add_edge_weighted_for_digraph!(g, 6, 4, 0.93);
        add_edge_weighted_for_digraph!(g, 6, 0, 0.58);
        add_edge_weighted_for_digraph!(g, 6, 2, 0.40);
        add_edge_weighted_for_digraph!(g, 7, 3, 0.39);
        add_edge_weighted_for_digraph!(g, 7, 5, 0.28);
        if false {
            g.print_dot("edge_weighted_for_digraph.dot");
        }
    }
}