Functions and types for working with graphs

Graaf is Dutch for

1. graph
2. count
3. dig

This crate is in alpha, and the API will change. See the changelog for a provisional roadmap.

Installation

Add the following to your Cargo.toml:

[dependencies]
graaf = "0.23.0"

Usage

use {
    graaf::{
        algo::bfs::single_pair_shortest_path,
        op::{
            AddEdge,
            Indegree,
        },
    },
    std::collections::HashSet,
};

let mut graph = [
    HashSet::new(), 
    HashSet::new(), 
    HashSet::new(), 
    HashSet::new()
];

// ╭───╮       ╭───╮
// │ 0 │   →   │ 1 │
// ╰───╯       ╰───╯
//   ↑           ↓
// ╭───╮       ╭───╮
// │ 3 │       │ 2 │
// ╰───╯       ╰───╯

graph.add_edge(3, 0);
graph.add_edge(0, 1);
graph.add_edge(1, 2);

assert_eq!(graph.indegree(0), 1);
assert_eq!(graph.indegree(1), 1);
assert_eq!(graph.indegree(2), 1);
assert_eq!(graph.indegree(3), 0);

let path = single_pair_shortest_path(&graph, 3, 2);

assert_eq!(path, Some(vec![3, 0, 1, 2]));

Overview

Algorithms

Common graph algorithms:

• bfs: breadth-first search
• dijkstra: Dijkstra's algorithm
• predecessor: predecessor search

Operations

Graph operation traits and implementations:

• AddEdge adds an unweighted edge.
• AddWeightedEdge adds a weighted edge.
• CountAllEdges counts all edges.
• CountAllVertices counts all vertices.
• EdgeWeight gets the weight of an edge.
• Indegree returns the indegree of a vertex.
• IsEdge returns whether an edge exists.
• IsSimple returns whether a graph is simple.
• IterAllEdges iterates over all unweighted edges.
• IterAllWeightedEdges iterates over all weighted edges.
• IterEdges iterates over all unweighted edges of a source vertex.
• IterVertices iterates over all vertices.
• IterWeightedEdges iterates over all weighted edges of a source vertex.
• Outdegree returns the outdegree of a vertex.
• RemoveEdge removes an edge.

Features

• adjacency_matrix: a representation for dense graphs, enabled by default.
• nightly: required for adjacency_matrix.

To disable these features, add the following to your Cargo.toml:

[dependencies]
graaf = { version = "0.23.0", default-features = false }