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.21.0"

Usage

use graaf::{
    op::{
        AddEdge,
        Indegree,
        Outdegree,
    },
    std::collections::HashSet,
};

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

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

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

assert_eq!(graph.outdegree(0), 2);
assert_eq!(graph.outdegree(1), 1);
assert_eq!(graph.outdegree(2), 0);

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

• nightly: required for the adjacency_matrix feature.
• adjacency_matrix: an adjacency matrix representation stored as a bit array.

To enable the adjacency_matrix feature, add the following to your Cargo.toml:

[dependencies]
graaf = { version = "0.21.0", features = ["adjacency_matrix", "nightly"] }