Crate graaf

Source
Expand description

§Graaf

Rust-powered directed graphs.

§Table of Contents

§Representations

§Arc-Weighted Sparse Digraphs

§Unweighted Dense Digraphs

§Unweighted Sparse Digraphs

§Generators

§Operations

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

A breadth-first search explores an unweighted digraph’s vertices in order of their distance from a source.

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.

§Distance Matrix

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

§Floyd-Warshall

§Johnson’s Circuit-Finding Algorithm

§Predecessor Tree

A PredecessorTree is the result of a search and contains the vertices’ predecessors.

§Tarjan

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 with Complement
proptest_empty_complete
Empty proptests with Complement and Complete
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