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.

Installation

Add the following to your Cargo.toml:

[dependencies]
graaf = "0.14.0"

Usage

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

let mut adj = AdjacencyMatrix::<4>::new();

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

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

assert_eq!(adj.outdegree(0), 2);
assert_eq!(adj.outdegree(1), 1);
assert_eq!(adj.outdegree(2), 1);
assert_eq!(adj.outdegree(3), 0);

Features

Algorithms: algo

Breadth-first search: bfs

• distances_single_source
• distances
• predecessors_single_source
• predecessors

Dijkstra's algorithm: dijkstra

• distances_single_source
• distances
• predecessors_single_source
• predecessors

Operations: op

These traits are implemented for various graph representations built from standard library containers.

• 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.

Representations: repr

Adjacency matrix, unweighted

• AdjacencyMatrix: an adjacency matrix representation of an unweighted directed graph stored as a bit array.

Adjacency list, unweighted

• BTreeMap<usize, BTreeSet<usize>>
• BTreeMap<usize, Vec<usize>>
• HashMap<usize, HashSet<usize>>
• HashMap<usize, Vec<usize>>
• Vec<BTreeSet<usize>>
• Vec<HashSet<usize>>
• Vec<Vec<usize>>
• [BTreeSet<usize>; V]
• [BTreeSet<usize>]
• [HashSet<usize>; V]
• [HashSet<usize>]
• [Vec<usize>; V]
• [Vec<usize>]

Adjacency list, weighted

• BTreeMap<usize, BTreeMap<usize, W>>
• BTreeMap<usize, BTreeSet<(usize, W)>>
• BTreeMap<usize, Vec<(usize, W)>>
• HashMap<usize, HashMap<usize, W>>
• HashMap<usize, HashSet<(usize, W)>>
• HashMap<usize, Vec<(usize, W)>>
• Vec<BTreeMap<usize, W>>
• Vec<BTreeSet<(usize, W)>>
• Vec<HashMap<usize, W>>
• Vec<HashSet<(usize, W)>>
• Vec<Vec<(usize, W)>>
• [BTreeMap<usize, W>; V]
• [BTreeMap<usize, W>]
• [BTreeSet<(usize, W)>; V]
• [BTreeSet<(usize, W)>]
• [HashMap<usize, W>; V]
• [HashMap<usize, W>]
• [HashSet<(usize, W)>; V]
• [HashSet<(usize, W)>]
• [Vec<(usize, W)>; V]
• [Vec<(usize, W)>]

Edge list, unweighted

• BTreeSet<(usize, usize)>
• HashSet<(usize, usize)>
• Vec<(usize, usize)>
• [(usize, usize); V]
• [(usize, usize)]

Edge list, weighted

• HashSet<(usize, usize, W)>
• Vec<(usize, usize, W)>
• [(usize, usize, W); V]
• [(usize, usize, W)]