1 unstable release

0.1.0 Dec 28, 2022

#6 in #bfs

Custom license

64KB
2K SLoC

Digraph-rs

Sandbox for playing with digraphs.

Description

A set of methods to handle and visualize the different approaches and algorithms in an appliance to directed graphs.

Create

What is inside

  • Di Graph

  • Graph builder: a set of macros to construct or extend graphs

  • Graph visualization to dot format

  • Dijkstra

  • AStar

  • BFS

  • DFS

  • Random graphs

    • Erdős-Rényi model
    • Watts Strogatz model

lib.rs:

The library allows creating and manipulating with directed graphs.

Description:

The main structure is DiGraph that is defined in terms of three types:

  • NId - id of the node. Should be unique and implement Eq + Hash
  • NL - node payload (EmptyPayload) by default
  • EL - edge payload (EmptyPayload) by default

Example of the struct:

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()
          ))
      );
  
    
}

Modules

  • builder: the module allows creating graph using defined templates(macroses)
  • analyzer: the module allows performing a set of default algorithms
  • visualizer: the module allows visualizing the graph and some extra information in graphviz format
  • generator: the module allows generating random graphs according to the different modules

Example with modules:

 
   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());
 }

Dependencies

~5–15MB
~195K SLoC