Crate graaf

Graaf

Work with directed graphs in Rust.

Table of Contents

• 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
• Naming Conventions
• Project Goals

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.

• The search method finds a vertex by value.
• The search_by method finds a vertex by predicate.

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

• adjacency_list
  An adjacency list representation of an unweighted digraph.
• adjacency_list_weighted
  An adjacency list representation of a weighted digraph.
• adjacency_matrix
  An adjacency matrix representation of an unweighted digraph.
• algo
  Digraph algorithms
• gen
  Digraph generators
• op
  Operations on digraphs