Crate graaf

Graaf

Functions and types for working with graphs

Operations

Build and query graphs made with standard collections, or implement the operation traits for your types.

use {
    graaf::{
        gen::EmptyConst,
        op::*,
    },
    std::collections::BTreeSet,
};

let mut graph = <[BTreeSet<usize>; 3]>::empty();

graph.add_arc(0, 1);
graph.add_arc(0, 2);

assert_eq!(graph.degree(0), 2);
assert_eq!(graph.degree(1), 1);
assert_eq!(graph.degree(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_arc(0, 1);
graph.add_arc(1, 1);

assert!(!graph.is_simple());

Generators

Generate parameterized graphs.

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]]
);

Modules

• algo
  Graph algorithms
• gen
  Graph generators
• op
  Operations on graphs
• prop
  Cross-module properties and strategies.
• repr
  Custom graph representations