algorithms_fourth 0.1.10

//!  第四章: 有向图算法
use std::{collections::HashSet, fs};

use crate::generate_vec_with;
pub mod acyclic_sp;
pub mod bellman_for_sp;
pub mod connect;
pub mod cycle;
pub mod depth_first_order;
pub mod dijkstra_sp;
pub mod directed_dfs;
pub mod edge_weighted;
pub mod topological;
type Bag = HashSet<usize>;
/// 向加权有向图中添加n条边
///
/// `g`:图
///
/// `x`:v
///
/// `y`:v对应的n个w
#[macro_export]
macro_rules! add_edge_weighted_for_digraph {
    // $(...),+ 包围起来，就可以匹配一个或多个用逗号隔开的表达式
    ($g:ident,$v:expr, $w:expr,$weight:expr) => {
        ($g.add_edge($crate::digraph::edge_weighted::DirectedEdge::new(
            $v, $w, $weight,
        )))
    };
}

/// 有向图
///
/// #用法
/// ```
/// use algorithms_fourth::digraph::Digraph;
/// let mut  g = Digraph::new(2);
///  g.add_edge(0,1);
/// ```
pub struct Digraph {
    vertex_count: usize,
    edge_count: usize,
    adj: Vec<Bag>,
}
impl Digraph {
    pub fn new(vertex_count: usize) -> Self {
        let adj = generate_vec_with!(Bag::new(), vertex_count);
        Digraph {
            vertex_count,
            edge_count: 0,
            adj,
        }
    }
    pub fn vertex_count(&self) -> usize {
        self.vertex_count
    }
    pub fn adge_count(&self) -> usize {
        self.edge_count
    }
    pub fn add_edge(&mut self, v: usize, w: usize) {
        self.adj[v].insert(w);
        self.edge_count += 1;
    }
    pub fn adj(&self, v: usize) -> &Bag {
        &self.adj[v]
    }
    pub fn reverse(&self) -> Self {
        let mut r = Digraph::new(self.vertex_count);
        for v in 0..self.vertex_count {
            for w in &self.adj[v] {
                r.add_edge(*w, v);
            }
        }
        r
    }
}
impl Digraph {
    /// 打印dot格式的图结构
    pub fn print_dot(&self, path: &str) {
        self.print_dot_with(path, None)
    }
    pub fn print_dot_with(&self, path: &str, labels: Option<Vec<String>>) {
        let mut graph = r#"digraph{
                label="graph"
                 bgcolor=grey
                 shape=circle
                 "#
        .to_string();
        if let Some(labels) = labels {
            labels.iter().enumerate().for_each(|(i, label)| {
                graph.push_str(&format!("\t{}[label=\"{}\"]\n", i, label));
            });
        }
        for v in 0..self.vertex_count {
            for w in self.adj(v).clone() {
                graph.push_str(&format!("{} -> {}\n", v, w));
            }
        }
        graph.push('}');
        let _ = fs::write(path, graph);
    }
}