# Crate graaf

Expand description

## §Graaf

Work with directed graphs in Rust.

## §Digraph Types

Graaf provides three representations of directed graphs.

These types eagerly implement digraph operations and digraph algorithms.

## §Creating Digraphs

Graaf provides six digraph generators.

## §Operations

The `op` module provides digraph operation traits. The digraph types implement these traits. One can implement these traits for custom digraph types. Operations form the foundation for algorithms.

### §Basic operations

Individual digraph types implement the basic operations.

### §Extended operations

The extended traits derive their implementation from the basic operations.

## §Algorithms

The `algo` module provides digraph algorithms.

### §Bellman-Ford-Moore

The Bellman-Ford-Moore algorithm finds the shortest paths in a weighted digraph with negative weights.

A breadth-first search explores the vertices of an unweighted digraph in order of their distance from a source.

These functions start from one or more source vertices and allow a custom step function, target predicate, distance array, breadth-first tree, and queue, where applicable.

These functions start from one source vertex.

### §Depth-first search (DFS)

A depth-first search explores the vertices of an unweighted digraph in order of their depth from a source.

### §Dijkstra’s algorithm

Dijkstra’s algorithm finds the shortest paths from one or more source vertices in a weighted digraph.

These functions start from one or more source vertices and allow a custom step function, target predicate, distance array, and heap, where applicable.

These functions start from one source vertex.

### §Floyd-Warshall

The Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in a weighted digraph.

A breadth-first tree is the result of a breadth-first search and contains the predecessors of the vertices on the shortest paths.

These functions produce a breadth-first tree.

### §Distance matrix

A distance matrix contains the shortest distances between all pairs of vertices in a digraph.

### §Naming Conventions

• `s` denotes a source vertex.
• `t` denotes a target vertex.
• `u` denotes a tail vertex or the first vertex in scope.
• `v` denotes a head vertex or the second vertex in scope.
• `w` denotes the weight of an arc.
• `x` denotes a head vertex or the third vertex in scope.
• `y` denotes a tail vertex or the fourth vertex in scope.

### §Project Goals

• A flexible API for digraph operations
• A comprehensive set of algorithms
• Generators for common digraphs
• Competitive performance
• Full documentation
• Extensive property tests
• Complete unit test and benchmark coverage