108 releases (41 breaking)
new 0.42.3 | May 12, 2024 |
---|---|
0.41.0 | May 11, 2024 |
0.2.3 | Mar 31, 2024 |
#137 in Data structures
9,978 downloads per month
500KB
13K
SLoC
Algorithms, operations, generators, and representations for directed graphs
Installation
Add the following to your Cargo.toml
:
[dependencies]
graaf = "0.42.3"
Overview
Operations
Build and query graphs made with standard collections, or implement the operation traits for your own types.
use {
graaf::{
gen::EmptyConst,
op::*,
},
std::collections::BTreeSet,
};
let mut graph = <[BTreeSet<usize>; 3]>::empty();
graph.add_edge(0, 1);
graph.add_edge(0, 2);
assert_eq!(graph.outdegree(0), 2);
assert_eq!(graph.indegree(1), 1);
assert_eq!(graph.indegree(2), 1);
graph.remove_edge(0, 1);
assert_eq!(graph.outdegree(0), 1);
assert_eq!(graph.indegree(1), 0);
assert_eq!(graph.indegree(2), 1);
Algorithms
Search, traverse, and analyze graphs built from the types that implement the operation traits.
use graaf::algo::bfs::single_pair_shortest_path as spsp;
// 0 ← 1
// ↑ ↑
// 3 → 2
let graph = [Vec::new(), vec![0], vec![1], vec![0, 2]];
assert_eq!(spsp(&graph, 3, 0), Some(vec![3, 0]));
assert_eq!(spsp(&graph, 3, 1), Some(vec![3, 2, 1]));
assert_eq!(spsp(&graph, 3, 2), Some(vec![3, 2]));
assert_eq!(spsp(&graph, 0, 3), None);
Representations
An adjacency matrix representation is available with the adjacency_matrix
feature.
use graaf::{
op::*,
repr::AdjacencyMatrix,
};
let mut graph = AdjacencyMatrix::<3>::new();
graph.add_edge(0, 1);
graph.add_edge(1, 1);
assert!(!graph.is_simple());
Generators
Generate parameterized graphs.
use graaf::gen::Cycle;
let graph = Vec::<Vec<usize>>::cycle(4);
assert_eq!(graph, vec![vec![1], vec![2], vec![3], vec![0]]);
Features
adjacency_matrix
enables the adjacency matrix representation. Requires nightly.
Changelog
See CHANGELOG.md.
License
Licensed under either the Apache License, Version 2.0 or the MIT license at your option.