Graaf  

Work with directed graphs in Rust.

Table of Contents

• Installation
• Digraph Types
• Creating Digraphs
• Operations
  • Basic Operations
  • Extended Operations
• Algorithms
  • Bellman-Ford-Moore
  • Breadth-First Search (BFS)
  • Depth-First Search (DFS)
  • Dijkstra's Algorithm
  • Floyd-Warshall Algorithm
  • Breath-First Tree
  • Distance Matrix
• Project Goals
• Changelog
• License

Installation

Add the following to your Cargo.toml:

[dependencies]
graaf = "0.64.6"

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

The gen module provides four digraph generators.

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

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

Extended Operations

The extended traits derive their implementation from the basic operations.

• Degree returns the degree of a vertex.
• HasEdge checks if an edge exists in a digraph.
• InNeighbors returns the in-neighbors of a vertex.
• IsBalanced checks if a digraph is balanced.
• IsComplete checks if a digraph is complete.
• IsIsolated checks if a vertex is isolated.
• IsOriented checks if a digraph is oriented.
• IsPendant checks if a vertex is a pendant.
• IsRegular checks if a digraph is regular.
• IsSemicomplete checks if a digraph is semicomplete.
• IsSubdigraph checks if a digraph is a subdigraph of another digraph.
• IsSuperdigraph checks if a digraph is a superdigraph of another digraph.
• IsSymmetric checks if a digraph is symmetric.
• IsWalk checks if a sequence of vertices is a walk in a digraph.

Algorithms

The algo module provides digraph algorithms.

Bellman-Ford-Moore

bellman_ford_moore finds the shortest paths in a weighted digraph with negative weights.

• single_source_distances finds the shortest distances from one source vertex to all other vertices.

Breadth-First Search (BFS)

bfs 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 value, where applicable.

• distances finds the shortest distances to all other vertices.
• predecessors finds the predecessors of the vertices on the shortest paths.
• shortest_path finds the shortest path to a target vertex.

These functions start from one source vertex.

• single_source_distances finds the distances to all other vertices.
• single_source_predecessors finds the predecessors on the shortest paths.
• single_pair_shortest_path finds the shortest path between two vertices.

Depth-First Search (DFS)

dfs explores the vertices of an unweighted digraph in order of their depth from a source.

• dfsa traverses the digraph, collecting an acyclic ordering and the times of each vertex's first and last visit.
• dfsa_predecessors collects an acyclic ordering, the predecessors, and the times of each vertex's first and last visit.
• acyclic_ordering generates an acyclic ordering of the vertices.

Dijkstra's Algorithm

dijkstra 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 value, where applicable.

• distances finds the shortest distances to all other vertices.
• predecessors finds the predecessors of the vertices on the shortest paths.
• shortest_path finds the shortest path to a target vertex.

These functions start from one source vertex.

• single_source_distances finds the shortest distances to all other vertices.
• single_source_predecessors finds the predecessors of the vertices on the shortest paths.
• single_pair_shortest_path finds the shortest path between two vertices.

Floyd-Warshall

floyd_warshall finds the shortest paths between all pairs of vertices in a weighted digraph.

• distances finds the shortest distances between all pairs of vertices.

Breadth-First Tree

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

• search finds the path to a target vertex.
• search_by finds the path to a vertex that satisfies a predicate.

These functions produce a BreadthFirstTree.

• bfs::single_source_predecessors
• bfs::predecessors
• dijkstra::single_source_predecessors
• dijkstra::predecessors

Distance Matrix

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

• center finds the center of the digraph.
• diameter finds the diameter of the digraph.
• eccentricities returns the eccentricities of the vertices.
• is_connected checks if the digraph is connected.

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.