1 unstable release
0.1.0 | Dec 28, 2022 |
---|
#7 in #bfs
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–13MB
~177K SLoC