Digraph-rs

用于与有向图玩耍的沙盒。

描述

一套用于处理和可视化针对有向图的不同方法和算法的方法。

创建

内部结构

• 有向图

• 图构建器：一组宏，用于构建或扩展图

• 将图可视化成dot格式

• Dijkstra

• AStar

• BFS

• DFS

• 随机图

  • Erdős-Rényi模型
  • Watts Strogatz模型

lib.rs:

该库允许创建和操作有向图。

描述

主要结构是DiGraph，它由三种类型定义

• NId - 节点id。应该是唯一的，并实现Eq + Hash
• NL - 节点负载（默认为EmptyPayload）
• EL - 边负载（默认为EmptyPayload）

结构示例

use digraph_rs::{DiGraph,EmptyPayload};
use std::collections::HashMap;
fn simple_creation_graph(){
  let mut graph:DiGraph<usize, EmptyPayload,EmptyPayload> = DiGraph::empty();
  graph.add_bare_node(1);  
  graph.add_bare_node(2);  
  graph.add_bare_node(3);
  graph.add_bare_node(4);
  
  graph.add_bare_edge(1, 2);
  graph.add_bare_edge(2, 3);
  graph.add_bare_edge(3, 4);
  graph.add_bare_edge(4, 1);
  assert_eq!(graph.start(), &Some(1));
       assert_eq!(
           graph.successors(1),
           Some(&HashMap::from_iter(
               vec![(2usize, EmptyPayload)].into_iter()
          ))
      );
  
    
}

模块

• builder：该模块允许使用定义的模板（宏）创建图
• analyzer：该模块允许执行一系列默认算法
• visualizer：该模块允许以graphviz格式可视化图和一些额外信息
• generator：该模块允许根据不同的模块生成随机图

模块示例

 
   use digraph_rs::{DiGraph,EmptyPayload,digraph, extend_edges, extend_nodes,};
   use digraph_rs::analyzer::dijkstra::{DijkstraPath, MinPathProcessor};
    #[test]
     fn complex_example() {
         let mut graph = digraph!((usize,_,usize) => [1,2,3,4,5,6,7,8] => {
           1 => [(2,3),(3,1),(4,2)];
           [2,3,4] => (5,2);
           5 => (6,1);
           6 => [(7,2),(8,3)];
         });
 
         let v_res = graph.visualize().str_to_dot_file("dots/graph.svg");
         assert!(v_res.is_ok());
 
         assert!(graph.analyze().edge(&1, &2).is_some());
         assert!(graph.analyze().edge(&1, &6).is_none());
 
         let mut path_finder = DijkstraPath::new(&graph);
         let paths = path_finder.on_edge(1);
         let trail = paths.trail(&8).unwrap();
         assert_eq!(trail, vec![1, 3, 5, 6, 8]);
         let r = graph
             .visualize()
             .to_dot_file("dots/graph_path_1_8.svg", MinPathProcessor::new(trail));
         assert!(r.is_ok());
 }