### 217 releases (72 breaking)

new 0.73.1 | Jul 22, 2024 |
---|---|

0.72.1 | Jul 21, 2024 |

0.2.3 | Mar 31, 2024 |

#**164** in Algorithms

**5,294** downloads per month

**MIT/Apache**

605KB

13K
SLoC

# Graaf

Work with directed graphs in Rust.

## Table of Contents

- Installation
- Digraph Types
- Creating Digraphs
- Operations
- Algorithms
- Naming Conventions
- Project Goals
- Changelog
- License

## Installation

Add the following to your

:`Cargo.toml`

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

## Digraph Types

Graaf provides three representations of directed graphs.

represents unweighted sparse digraphs.`adjacency_list`

represents unweighted dense digraphs.`adjacency_matrix`

represents arc-weighted sparse digraphs.`adjacency_list_weighted`

These types eagerly implement digraph operations and digraph algorithms.

## Creating Digraphs

The

module provides eight digraph generators.`gen`

generates a complete bipartite digraph.`Biclique`

generates a circuit digraph.`Circuit`

generates a complete digraph.`Complete`

generates a bidirectional circuit.`Cycle`

generates a digraph with no arcs.`Empty`

generates a path digraph.`Path`

generates a random tournament.`RandomTournament`

generates a star digraph.`Star`

## Operations

The

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.`op`

### Basic Operations

Individual digraph types implement the basic operations.

adds an arc to an arc-weighted digraph.`AddArcWeighted`

adds an arc to an unweighted digraph.`AddArc`

returns the weight of an arc.`ArcWeight`

returns the arcs and their weights in a digraph.`ArcsWeighted`

returns the arcs in a digraph.`Arcs`

returns the converse of a digraph.`Converse`

checks if an arc exists in a digraph.`HasArc`

returns the indegree of a vertex.`Indegree`

checks if a digraph contains no loops or parallel arcs.`IsSimple`

returns the number of vertices.`Order`

returns the weighted out-neighbors of a vertex.`OutNeighborsWeighted`

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

returns the outdegree of a vertex.`Outdegree`

removes an arc from a digraph.`RemoveArc`

returns the number of arcs in a digraph.`Size`

returns the vertices in a digraph.`Vertices`

### Extended Operations

The extended traits derive their implementation from the basic operations.

returns the complement of a digraph.`Complement`

returns the degree of a vertex.`Degree`

returns the degree sequence of a digraph.`DegreeSequence`

checks if an edge exists in a digraph.`HasEdge`

returns the in-neighbors of a vertex.`InNeighbors`

checks if a digraph is balanced.`IsBalanced`

checks if a digraph is complete.`IsComplete`

checks if a vertex is isolated.`IsIsolated`

checks if a digraph is oriented.`IsOriented`

checks if a vertex is a pendant.`IsPendant`

checks if a digraph is regular.`IsRegular`

checks if a digraph is semicomplete.`IsSemicomplete`

checks if a digraph is a spanning subdigraph.`IsSpanningSubdigraph`

checks if a digraph is a subdigraph.`IsSubdigraph`

checks if a digraph is a superdigraph.`IsSuperdigraph`

checks if a digraph is symmetric.`IsSymmetric`

checks if a digraph is a tournament.`IsTournament`

checks if a sequence of vertices is a walk in a digraph.`IsWalk`

## Algorithms

The

module provides digraph algorithms.`algo`

### Bellman-Ford-Moore

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

finds the shortest distances.`single_source_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.

finds the shortest distances.`distances`

finds the predecessors.`predecessors`

finds the shortest path.`shortest_path`

These functions start from one source vertex.

finds the shortest distances.`single_source_distances`

finds the predecessors.`single_source_predecessors`

finds the shortest path.`single_pair_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.

traverses the digraph.`dfsa`

finds the predecessors.`dfsa_predecessors`

generates an acyclic ordering.`acyclic_ordering`

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

finds the shortest distances.`distances`

finds the predecessors.`predecessors`

finds the shortest path.`shortest_path`

These functions start from one source vertex.

finds the shortest distances.`single_source_distances`

finds the predecessors.`single_source_predecessors`

finds the shortest path.`single_pair_shortest_path`

### Floyd-Warshall

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

finds the shortest distances.`distances`

### Tarjan

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

finds the strongly connected components.`strongly_connected_components`

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

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

finds the center of the digraph.`center`

finds the diameter of the digraph.`diameter`

returns the eccentricities of the vertices.`eccentricities`

checks if the digraph is connected.`is_connected`

finds the periphery of the digraph.`periphery`

## Naming Conventions

denotes a source vertex.`s`

denotes a target vertex.`t`

denotes a tail vertex or the first vertex in scope.`u`

denotes a head vertex or the second vertex in scope.`v`

denotes the weight of an arc.`w`

denotes a tail vertex or the third vertex in scope.`x`

denotes a head vertex or the fourth vertex in scope.`y`

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