## graaf

Work with directed graphs

### 217 releases(72 breaking)

 new 0.73.1 Jul 22, 2024 Jul 21, 2024 Mar 31, 2024

#164 in Algorithms

5,294 downloads per month

MIT/Apache

605KB
13K SLoC

# Graaf

Work with directed graphs in Rust.

## Installation

Add the following to your `Cargo.toml`:

``````[dependencies]
graaf = "0.73.1"
``````

## Digraph Types

Graaf provides three representations of directed graphs.

These types eagerly implement digraph operations and digraph algorithms.

## Creating Digraphs

The `gen` module provides eight 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 an arc-weighted digraph with negative weights.

### Breadth-First Search (BFS)

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

Dijkstra's algorithm finds the shortest paths in an arc-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 an arc-weighted digraph.

### Tarjan

Tarjan's algorithm finds the strongly connected components in a digraph.

### Types

These types are produced by the algorithms.

#### Breadth-First Tree

A breadth-first tree is the result of a breadth-first search.

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 tail vertex or the third vertex in scope.
• `y` denotes a head 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

## Changelog

See CHANGELOG.md for a list of changes.

## License

Licensed under Apache License, Version 2.0 or MIT license at your option.