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

Usage

use graaf::{
    op::{
        AddEdge,
        Indegree,
        Outdegree,
    },
    repr::AdjacencyMatrix,
};

let mut graph = AdjacencyMatrix::<3>::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

AdjacencyMatrix

An adjacency matrix representation of unweighted directed graphs, stored as a bit array. This feature is enabled by default. To opt out, remove the adjacency_matrix feature from your Cargo.toml:

[dependencies]
graaf = { version = "0.18.0", features = [] }