## Expand description

## §Graaf

Work with directed graphs in Rust.

## §Table of Contents

## §Digraph Types

Graaf provides three representations of directed graphs.

- The Adjacency List type represents unweighted sparse digraphs.
- The Adjacency Matrix type represents unweighted dense digraphs.
- The Weighted Adjacency List type represents weighted sparse digraphs.

These types eagerly implement digraph operations and digraph algorithms.

## §Creating Digraphs

Graaf provides six digraph generators.

- The
`Biclique`

trait generates a complete bipartite digraph. - The
`Complete`

trait generates a digraph in which an arc connects every ordered pair of distinct vertices. - The
`Cycle`

trait generates a digraph with a cycle of a given length. - The
`Empty`

trait generates a digraph with no arcs. - The
`RandomTournament`

trait generates a random digraph in which an arc connects every unordered pair of distinct vertices. - The
`Star`

trait generates a star digraph.

## §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.

- The
`AddArcWeighted`

adds an arc to a weighted digraph. - The
`AddArc`

adds an arc to an unweighted digraph. - The
`ArcWeight`

returns the weight of an arc. - The
`ArcsWeighted`

returns the arcs and their weights in a digraph. - The
`Arcs`

returns the arcs in a digraph. - The
`Converse`

returns the converse of a digraph. - The
`HasArc`

trait checks if an arc exists in a digraph. - The
`Indegree`

returns the indegree of a vertex. - The
`IsSimple`

trait checks if a digraph contains no loops or parallel arcs. - The
`Order`

returns the number of vertices. - The
`OutNeighborsWeighted`

returns the weighted out-neighbors of a vertex. - The
`OutNeighbors`

returns the out-neighbors of a vertex. - The
`Outdegree`

returns the outdegree of a vertex. - The
`RemoveArc`

removes an arc from a digraph. - The
`Size`

returns the number of arcs in a digraph. - The
`Vertices`

returns the vertices in a digraph.

### §Extended operations

The extended traits derive their implementation from the basic operations.

- The
`Degree`

returns the degree of a vertex. - The
`DegreeSequence`

returns the degree sequence of a digraph. - The
`HasEdge`

trait checks if an edge exists in a digraph. - The
`InNeighbors`

gets the in-neighbors of a vertex. - The
`IsBalanced`

trait checks if a digraph is balanced. - The
`IsComplete`

trait checks if a digraph is complete. - The
`IsIsolated`

trait checks if a vertex is isolated. - The
`IsOriented`

trait checks if a digraph is oriented. - The
`IsPendant`

trait checks if a vertex is a pendant. - The
`IsRegular`

trait checks if a digraph is regular. - The
`IsSemicomplete`

trait checks if a digraph is semicomplete. - The
`IsSubdigraph`

trait checks if a digraph is a subdigraph. - The
`IsSuperdigraph`

trait checks if a digraph is a superdigraph. - The
`IsSymmetric`

trait checks if a digraph is symmetric. - The
`IsTournament`

trait checks if a digraph is a tournament. - The
`IsWalk`

trait checks if a sequence of vertices is a walk in a digraph.

## §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.

- The
`single_source_distances`

function finds the shortest distances.

### §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.

- The
`distances`

function finds the shortest distances. - The
`predecessors`

function finds the predecessors. - The
`shortest_path`

function finds the shortest path.

These functions start from one source vertex.

- The
`single_source_distances`

function finds the shortest distances. - The
`single_source_predecessors`

function finds the predecessors. - The
`single_pair_shortest_path`

function finds the shortest path.

### §Depth-first search (DFS)

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

- The
`dfsa`

function traverses the digraph. - The
`dfsa_predecessors`

function finds the predecessors. - The
`acyclic_ordering`

function generates an acyclic ordering.

### §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.

- The
`distances`

function finds the shortest distances. - The
`predecessors`

function finds the predecessors. - The
`shortest_path`

function finds the shortest path.

These functions start from one source vertex.

- The
`single_source_distances`

function finds the shortest distances. - The
`single_source_predecessors`

function finds the predecessors. - The
`single_pair_shortest_path`

function finds the shortest path.

### §Floyd-Warshall

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

- The
`distances`

function finds the shortest distances.

### §Breadth-first tree

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.

`bfs::single_source_predecessors`

`bfs::predecessors`

`dijkstra::single_source_predecessors`

`dijkstra::predecessors`

### §Distance matrix

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

- The
`center`

method finds the center of the digraph. - The
`diameter`

method finds the diameter of the digraph. - The
`eccentricities`

method returns the eccentricities of the vertices. - The
`is_connected`

method checks if the digraph is connected.

### §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

## Modules§

- An adjacency list representation of an unweighted digraph.
- An adjacency list representation of a weighted digraph.
- An adjacency matrix representation of an unweighted digraph.
- Digraph algorithms
- Digraph generators
- Operations on digraphs