Work with directed graphs in Rust.
- Installation
- Digraph Types
- Creating Digraphs
- Operations
- Algorithms
- Naming Conventions
- Project Goals
- Changelog
- License
Add the following to your Cargo.toml
:
[dependencies]
graaf = "0.75.3"
Graaf provides three representations of directed graphs.
adjacency_list
represents unweighted sparse digraphs.adjacency_matrix
represents unweighted dense digraphs.adjacency_list_weighted
represents arc-weighted sparse digraphs.
These types eagerly implement digraph operations and digraph algorithms.
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.
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.
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.
The extended traits derive their implementation from the basic operations.
Complement
returns the complement of a digraph.Degree
returns the degree of a vertex.HasEdge
checks if an edge exists in a digraph.IndegreeSequence
returns the indegree sequence of 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.IsSpanningSubdigraph
checks if a digraph is a spanning subdigraph.IsSubdigraph
checks if a digraph is a subdigraph.IsSuperdigraph
checks if a digraph is a superdigraph.IsSymmetric
checks if a digraph is symmetric.IsTournament
checks if a digraph is a tournament.IsWalk
checks if a sequence of vertices is a walk in a digraph.OutdegreeSequence
returns the outdegree sequence of a digraph.SemidegreeSequence
returns the semidegree sequence of a digraph.Sinks
returns the sinks in a digraph.Sources
returns the sources in a digraph.
The algo
module provides digraph algorithms.
The Bellman-Ford-Moore algorithm finds the shortest paths in an arc-weighted digraph with negative weights.
single_source_distances
finds the shortest distances.
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.
distances
finds the shortest distances.predecessors
finds the predecessors.shortest_path
finds the shortest path.
These functions start from one source vertex.
single_source_distances
finds the shortest distances.single_source_predecessors
finds the predecessors.single_pair_shortest_path
finds the shortest path.
A depth-first search explores the vertices of an unweighted digraph in order of their depth from a source.
dfsa
traverses the digraph.dfsa_predecessors
finds the predecessors.acyclic_ordering
generates an acyclic ordering.
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.
distances
finds the shortest distances.predecessors
finds the predecessors.shortest_path
finds the shortest path.
These functions start from one source vertex.
single_source_distances
finds the shortest distances.single_source_predecessors
finds the predecessors.single_pair_shortest_path
finds the shortest path.
The Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in an arc-weighted digraph.
distances
finds the shortest distances.
Tarjan's algorithm finds the strongly connected components in a digraph.
strongly_connected_components
finds the strongly connected components.
These types are produced by the algorithms.
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
A distance matrix 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.periphery
finds the periphery of the digraph.
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.
- 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
See CHANGELOG.md for a list of changes.
Licensed under Apache License, Version 2.0 or MIT license at your option.