Expand description
§Graaf
Rust-powered directed graphs.
§Table of Contents
§Representations
§Arc-Weighted Sparse Digraphs
AdjacencyListWeighted
represents a digraph as a vector of maps.
§Unweighted Dense Digraphs
AdjacencyMatrix
represents a digraph as a matrix using a bit vector.
§Unweighted Sparse Digraphs
AdjacencyList
represents a digraph as a vector of sets.AdjacencyMap
represents a digraph as a map of sets.EdgeList
represents a digraph as a vector of tuples.
§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 without arcs.ErdosRenyi
generates a random digraph.RandomRecursiveTree
generates a random recursive tree.Path
generates a path digraph.RandomTournament
generates a random tournament.Star
generates a star digraph.Wheel
generates a wheel digraph.
§Operations
AddArcWeighted
adds an arc to an arc-weighted digraph.AddArc
adds an arc to an unweighted digraph.ArcWeight
returns an arc’s weight.ArcsWeighted
iterates a digraph’s weighted arcs.Arcs
iterates a digraph’s arcs.Complement
returns a digraph’s complement.ContiguousOrder
returns a contiguous digraph’s order.Converse
returns a digraph’s converse.DegreeSequence
iterates a digraph’s degrees.Degree
returns a vertex’s degree.FilterVertices
filters a digraph’s vertices.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
iterates a vertex’s in-neighbors.IndegreeSequence
iterates a digraph’s indegrees.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
counts the vertices in a digraph.OutNeighborsWeighted
iterates a vertex’s weighted out-neighbors.OutNeighbors
iterates a vertex’s out-neighbors.OutdegreeSequence
iterates a digraph’s outdegrees.Outdegree
returns a vertex’s outdegree.RemoveArc
removes an arc from a digraph.SemidegreeSequence
iterates a digraph’s semidegrees.Sinks
iterates a digraph’s sinks.Size
counts the arcs in a digraph.Sources
iterates a digraph’s sources.Union
returns the union of two digraphs.Vertices
iterates a digraph’s vertices.
§Algorithms
§Bellman-Ford-Moore
BellmanFordMoore::distances
finds the shortest distances from a source vertex to all other vertices in an arc-weighted digraph with negative weights.
§Breadth-First Search
A breadth-first search explores an unweighted digraph’s vertices in order of their distance from a source.
Bfs
iterates the vertices.BfsDist
iterates the vertices and their distance from the source.BfsPred
iterates the vertices and their predecessors.BfsDist::distances
finds the shortest distances.BfsPred::cycles
returns the cycles along the shortest path.BfsPred::predecessors
finds the predecessors.BfsPred::shortest_path
finds the shortest path.
§Depth-First Search
A depth-first search explores an unweighted digraph’s vertices in order of their distance from a source.
Dfs
iterates the vertices.DfsDist
iterates the vertices and their distance from the source.DfsPred
iterates the vertices and their predecessors.DfsPred::predecessors
finds the predecessors.
§Dijkstra
Dijkstra’s algorithm finds the shortest paths from one or more source vertices in an arc-weighted digraph.
Dijkstra
iterates the vertices.DijkstraDist
iterates the vertices and their distance from the source.DijkstraPred
iterates the vertices and their predecessors.DijkstraDist::distances
finds the shortest distances.DijkstraPred::predecessors
finds the predecessors.DijkstraPred::shortest_path
finds the shortest path.
§Distance Matrix
A DistanceMatrix
contains the shortest distances between all vertex
pairs in a digraph.
DistanceMatrix::center
finds the digraph’s center.DistanceMatrix::diameter
finds the digraph’s diameter.DistanceMatrix::eccentricities
the vertices’ eccentricities.DistanceMatrix::is_connected
checks the digraph’s connectedness.DistanceMatrix::periphery
finds the digraph’s periphery.
§Floyd-Warshall
FloydWarshall::distances
finds the distance between each vertex pair in an arc-weighted digraph.
§Johnson’s Circuit-Finding Algorithm
Johnson75::circuits
finds a digraph’s circuits.
§Predecessor Tree
A PredecessorTree
is the result of a search and contains the vertices’
predecessors.
PredecessorTree::search
finds a vertex by value.PredecessorTree::search_by
finds a vertex by predicate.
§Tarjan
Tarjan::components
finds strongly connected components in a digraph.
Re-exports§
pub use repr::AdjacencyList;
pub use repr::AdjacencyListWeighted;
pub use repr::AdjacencyMap;
pub use repr::AdjacencyMatrix;
pub use repr::EdgeList;
pub use op::AddArc;
pub use op::AddArcWeighted;
pub use op::ArcWeight;
pub use op::Arcs;
pub use op::ArcsWeighted;
pub use op::Complement;
pub use op::ContiguousOrder;
pub use op::Converse;
pub use op::Degree;
pub use op::DegreeSequence;
pub use op::FilterVertices;
pub use op::HasArc;
pub use op::HasEdge;
pub use op::HasWalk;
pub use op::InNeighbors;
pub use op::Indegree;
pub use op::IndegreeSequence;
pub use op::IsBalanced;
pub use op::IsComplete;
pub use op::IsIsolated;
pub use op::IsOriented;
pub use op::IsPendant;
pub use op::IsRegular;
pub use op::IsSemicomplete;
pub use op::IsSimple;
pub use op::IsSpanningSubdigraph;
pub use op::IsSubdigraph;
pub use op::IsSuperdigraph;
pub use op::IsSymmetric;
pub use op::IsTournament;
pub use op::Order;
pub use op::OutNeighbors;
pub use op::OutNeighborsWeighted;
pub use op::Outdegree;
pub use op::OutdegreeSequence;
pub use op::RemoveArc;
pub use op::SemidegreeSequence;
pub use op::Sinks;
pub use op::Size;
pub use op::Sources;
pub use op::Union;
pub use op::Vertices;
pub use gen::Biclique;
pub use gen::Circuit;
pub use gen::Complete;
pub use gen::Cycle;
pub use gen::Empty;
pub use gen::ErdosRenyi;
pub use gen::Path;
pub use gen::RandomRecursiveTree;
pub use gen::RandomTournament;
pub use gen::Star;
pub use gen::Wheel;
pub use algo::bellman_ford_moore::BellmanFordMoore;
pub use algo::bfs::Bfs;
pub use algo::bfs_dist::BfsDist;
pub use algo::bfs_pred::BfsPred;
pub use algo::dfs::Dfs;
pub use algo::dfs_dist::DfsDist;
pub use algo::dfs_pred::DfsPred;
pub use algo::dijkstra::Dijkstra;
pub use algo::dijkstra_dist::DijkstraDist;
pub use algo::dijkstra_pred::DijkstraPred;
pub use algo::distance_matrix::DistanceMatrix;
pub use algo::floyd_warshall::FloydWarshall;
pub use algo::johnson_75::Johnson75;
pub use algo::predecessor_tree::PredecessorTree;
pub use algo::tarjan::Tarjan;
Modules§
- algo
- Digraph algorithms
- gen
- Generate parameterized and random digraphs.
- op
- Operations on digraphs
- repr
- Digraph representations.
Macros§
- proptest_
add_ arc AddArc
proptests- proptest_
add_ arc_ weighted AddArcWeighted
proptests- proptest_
biclique Biclique
proptests- proptest_
circuit Circuit
proptests- proptest_
complete Complete
proptests- proptest_
contiguous_ order ContiguousOrder
proptests- proptest_
cycle Cycle
proptests- proptest_
empty Empty
proptests- proptest_
empty_ complement Empty
proptests withComplement
- proptest_
empty_ complete Empty
proptests withComplement
andComplete
- proptest_
erdos_ renyi ErdosRenyi
proptests- proptest_
has_ arc HasArc
proptests- proptest_
path Path
proptests- proptest_
random_ recursive_ tree RandomRecursiveTree
proptests- proptest_
random_ tournament RandomTournament
proptests- proptest_
star Star
proptests- proptest_
union Union
proptests- proptest_
wheel Wheel
proptests- test_
add_ arc_ out_ of_ bounds AddArc
out-of-bounds tests- test_
add_ arc_ self_ loop AddArc
self-loop tests- test_
arcs Arcs
tests- test_
biclique Biclique
tests- test_
circuit Circuit
tests- test_
complete Complete
tests- test_
converse Converse
tests- test_
cycle Cycle
tests- test_
degree Degree
tests- test_
degree_ sequence DegreeSequence
tests- test_
empty Empty
tests- test_
erdos_ renyi ErdosRenyi
tests- test_
has_ walk HasWalk
tests- test_
in_ neighbors InNeighbors
tests- test_
indegree Indegree
tests- test_
indegree_ sequence IndegreeSequence
tests- test_
is_ balanced IsBalanced
tests- test_
is_ complete IsComplete
tests- test_
is_ isolated IsIsolated
tests- test_
is_ oriented IsOriented
tests- test_
is_ pendant IsPendant
tests- test_
is_ regular IsRegular
tests- test_
is_ semicomplete IsSemicomplete
tests- test_
is_ simple IsSimple
tests- test_
is_ symmetric IsSymmetric
tests- test_
is_ tournament IsTournament
tests- test_
order Order
tests- test_
out_ neighbors OutNeighbors
tests- test_
outdegree Outdegree
tests- test_
outdegree_ sequence OutdegreeSequence
tests- test_
path Path
tests- test_
random_ recursive_ tree RandomRecursiveTree
tests- test_
random_ tournament RandomTournament
tests- test_
remove_ arc RemoveArc
tests- test_
semidegree_ sequence SemidegreeSequence
tests- test_
sinks Sinks
tests- test_
size Size
tests- test_
sources Sources
tests- test_
star Star
tests- test_
wheel Wheel
tests