Crate graaf

Graaf

Rust-powered directed graphs.

Table of Contents

• Digraph Types
• Creating Digraphs
• Operations
• Algorithms
  • Bellman-Ford-Moore
  • Breadth-First Search (BFS)
  • Depth-First Search (DFS)
  • Dijkstra
  • Floyd-Warshall
  • Tarjan
  • Breath-First Tree
  • Distance Matrix
• Naming Conventions

Digraph Types

Graaf provides directed graphs representations. These types eagerly implement digraph operations and algorithms.

• adjacency_list represents unweighted sparse digraphs.
• adjacency_matrix represents unweighted dense digraphs.
• adjacency_list_weighted represents arc-weighted sparse digraphs.
• edge_list represents unweighted sparse digraphs.

Creating Digraphs

The gen module provides digraph generators. Each digraph representation can be constructed with the operations in the op module.

• 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.
• ErdosRenyi generates a random digraph.
• RandomTournament generates a random tournament.
• Star generates a star digraph.
• Path generates a path 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.

• AddArcWeighted adds an arc to an arc-weighted digraph.
• AddArc adds an arc to an unweighted digraph.
• ArcWeight returns an arc’s weight.
• ArcsWeighted returns a digraph’s weighted arcs.
• Arcs returns a digraph’s arcs.
• Complement returns a digraph’s complement.
• Converse returns a digraph’s converse.
• DegreeSequence returns a digraph’s degree sequence.
• Degree returns a vertex’s degree.
• HasArc checks whether a digraph contains an arc.
• HasEdge checks whether a digraph contains an edge.
• HasWalk checks whether a digraph contains a walk.
• InNeighbors returns a vertex’s in-neighbors.
• IndegreeSequence returns a digraph’s indegree sequence.
• Indegree a vertex’s indegree.
• IsBalanced checks whether a digraph is balanced.
• IsComplete checks whether a digraph is complete.
• IsIsolated checks whether a vertex is isolated.
• IsOriented checks whether a digraph is oriented.
• IsPendant checks whether a vertex is a pendant.
• IsRegular checks whether a digraph is regular.
• IsSemicomplete checks whether a digraph is semicomplete.
• IsSimple checks whether a digraph is simple.
• IsSpanningSubdigraph checks whether a digraph spans a superdigraph.
• IsSubdigraph checks whether a digraph is a subdigraph.
• IsSuperdigraph checks whether a digraph is a superdigraph.
• IsSymmetric checks whether a digraph is symmetric.
• IsTournament checks whether a digraph is a tournament.
• Order returns the number of vertices in a digraph.
• OutNeighborsWeighted returns a vertex’s weighted out-neighbors.
• OutNeighbors returns a vertex’s out-neighbors.
• OutdegreeSequence returns a digraph’s outdegree sequence.
• Outdegree returns a vertex’s outdegree.
• RemoveArc removes an arc from a digraph.
• SemidegreeSequence returns a digraph’s semidegree sequence.
• Sinks returns a digraph’s sinks.
• Size returns the number of arcs in a digraph.
• Sources returns a digraph’s sources.
• Vertices returns a digraph’s vertices.

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.

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

• bfs::Bfs iterates over the vertices.
• bfs_dist::Bfs iterates over the vertices and their distance from the source.
• bfs_pred::Bfs iterates over the vertices and their predecessors.
• bfs_dist::Bfs::distances finds the shortest distances.
• bfs_pred::Bfs::predecessors finds the predecessors.
• bfs_pred::Bfs::shortest_path finds the shortest path.

Depth-First Search (DFS)

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

• dfs::Dfs iterates over the vertices.
• dfs_dist::Dfs iterates over the vertices and their distance from the source.

Dijkstra

Dijkstra’s algorithm finds the shortest paths from one or more source vertices in an arc-weighted digraph.

• dijkstra::Dijkstra iterates over the vertices.
• dijkstra_dist::Dijkstra iterates over the vertices and their distance from the source.
• dijkstra_pred::Dijkstra iterates over the vertices and their predecessors.
• dijkstra_dist::Dijkstra::distances finds the shortest distances.
• dijkstra_pred::Dijkstra::predecessors finds the predecessors.
• dijkstra_pred::Dijkstra::shortest_path finds the shortest path.

Floyd-Warshall

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

• distances finds the shortest distances.

Tarjan

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

• strongly_connected_components finds the strongly connected components.

Predecessor Tree

A PredecessorTree is the result of a breadth-first search and contains the predecessors of the vertices on the shortest paths.

• PredecessorTree::search finds a vertex by value.
• PredecessorTree::search_by finds a vertex by predicate.

These functions produce a predecessor tree.

• bfs_pred::Bfs::predecessors
• dijkstra_pred::Dijkstra::predecessors

Distance Matrix

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

• DistanceMatrix::center finds the center of the digraph.
• DistanceMatrix::diameter finds the diameter of the digraph.
• DistanceMatrix::eccentricities returns the eccentricities of the vertices.
• DistanceMatrix::is_connected checks if the digraph is connected.
• DistanceMatrix::periphery finds the periphery of the 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.

Modules

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