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

Download history 1222/week @ 2024-04-01 1342/week @ 2024-04-08 2502/week @ 2024-04-15 2256/week @ 2024-04-22 2875/week @ 2024-04-29 2078/week @ 2024-05-06 1382/week @ 2024-05-13 1543/week @ 2024-05-20 1511/week @ 2024-05-27 2277/week @ 2024-06-03 1154/week @ 2024-06-10 985/week @ 2024-06-17 611/week @ 2024-06-24 2309/week @ 2024-07-01 1151/week @ 2024-07-08 1178/week @ 2024-07-15

5,294 downloads per month

MIT/Apache

605KB
13K SLoC

Graaf   Crates.io Build status API reference Coverage Status

Work with directed graphs in Rust.

Table of Contents

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.

  • Biclique generates a complete bipartite digraph.
  • Circuit generates a circuit digraph.
  • Complete generates a complete digraph.
  • Cycle generates a bidirectional circuit.
  • Empty generates a digraph with no arcs.
  • Path generates a path digraph.
  • RandomTournament generates a random tournament.
  • Star 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.

  • AddArcWeighted adds an arc to an arc-weighted digraph.
  • AddArc adds an arc to an unweighted digraph.
  • ArcWeight returns the weight of an arc.
  • ArcsWeighted returns the arcs and their weights in a digraph.
  • Arcs returns the arcs in a digraph.
  • Converse returns the converse of a digraph.
  • HasArc checks if an arc exists in a digraph.
  • Indegree returns the indegree of a vertex.
  • IsSimple checks if a digraph contains no loops or parallel arcs.
  • Order returns the number of vertices.
  • OutNeighborsWeighted returns the weighted out-neighbors of a vertex.
  • OutNeighbors returns the out-neighbors of a vertex.
  • Outdegree returns the outdegree of a vertex.
  • RemoveArc removes an arc from a digraph.
  • Size returns the number of arcs in a digraph.
  • Vertices returns the vertices in a digraph.

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.

No runtime deps