128 releases (51 breaking)
new 0.52.0 | May 26, 2024 |
---|---|
0.50.2 | May 24, 2024 |
0.2.3 | Mar 31, 2024 |
#116 in Data structures
8,005 downloads per month
525KB
14K
SLoC
Work with directed graphs.
Installation
Add the following to your Cargo.toml
:
[dependencies]
graaf = "0.52.0"
Overview
Operations
Build and query digraphs.
use {
graaf::{
gen::EmptyConst,
op::*,
},
std::collections::BTreeSet,
};
let mut digraph = <[BTreeSet<usize>; 3]>::empty();
digraph.add_arc(0, 1);
digraph.add_arc(0, 2);
assert_eq!(digraph.degree(0), 2);
assert_eq!(digraph.degree(1), 1);
assert_eq!(digraph.degree(2), 1);
Algorithms
Search, traverse, and analyze digraphs.
use graaf::algo::bfs::single_pair_shortest_path as spsp;
let digraph = [Vec::new(), vec![0], vec![1], vec![0, 2]];
assert_eq!(spsp(&digraph, 3, 0), Some(vec![3, 0]));
assert_eq!(spsp(&digraph, 3, 1), Some(vec![3, 2, 1]));
assert_eq!(spsp(&digraph, 3, 2), Some(vec![3, 2]));
assert_eq!(spsp(&digraph, 0, 3), None);
Generators
Generate parameterized digraphs.
use graaf::gen::*;
assert_eq!(
Vec::<Vec<usize>>::empty(2),
vec![Vec::new(), Vec::new()]
);
assert_eq!(
Vec::<Vec<usize>>::cycle(3),
vec![vec![1], vec![2], vec![0]]
);
assert_eq!(
<[Vec::<usize>; 3]>::complete(),
[vec![1, 2], vec![0, 2], vec![0, 1]]
);
Generate random digraphs.
use {
graaf::{
gen::RandomTournament,
op::*,
},
std::collections::BTreeSet,
};
let tournament = Vec::<BTreeSet<usize>>::random_tournament(4);
assert_eq!(tournament.size(), 6);
assert_eq!(tournament.order(), 4);
for s in tournament.iter_vertices() {
assert_eq!(tournament.degree(s), 3);
assert!((0..3).contains(&tournament.outdegree(s)));
assert!((0..3).contains(&tournament.indegree(s)));
}
Representations
An adjacency matrix representation is available with the adjacency_matrix
feature.
use graaf::{
op::*,
repr::AdjacencyMatrix,
};
let mut digraph = AdjacencyMatrix::<3>::new();
digraph.add_arc(0, 1);
digraph.add_arc(1, 1);
assert!(!digraph.is_simple());
Project goals
- A flexible API for digraph operations
- A comprehensive set of algorithms
- Generators for common digraphs
- Competitive performance
- Complete documentation
- Full unit test coverage
- Full benchmark coverage
- Extensive property tests
Features
These features require nightly Rust.
adjacency_matrix
enables the adjacency matrix representation.
Changelog
See CHANGELOG.md for a list of changes.
License
Licensed under Apache License, Version 2.0 or MIT license at your option.