Crate graaf

Graaf

Rust-powered directed graphs.

Table of Contents

• Representations
• Generators
• Operations
• Algorithms
  • Bellman-Ford-Moore
  • Breadth-First Search
  • Depth-First Search
  • Dijkstra
  • Distance Matrix
  • Floyd-Warshall
  • Predecessor Tree
  • Tarjan

Representations

• AdjacencyListWeighted represents arc-weighted sparse digraphs.
• AdjacencyList represents unweighted sparse digraphs.
• AdjacencyMatrix represents unweighted dense digraphs.
• EdgeList represents unweighted sparse digraphs.

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.
• ErdosRenyi generates a random digraph.
• RandomTournament generates a random tournament.
• Star generates a star digraph.
• Path generates a path 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.
• Converse returns a digraph’s converse.
• DegreeSequence iterates a digraph’s degrees.
• 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 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 returns the number of 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 returns the number of 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

Find the shortest distances from a source vertex to all other vertices in an arc-weighted digraph with negative weights.

• bellman_ford_moore::single_source_distances finds the shortest distances.

Breadth-First Search

A breadth-first search explores the vertices of an unweighted digraph 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::predecessors finds the predecessors.
• BfsPred::shortest_path finds the shortest path.

Depth-First Search

A depth-first search explores the vertices of an unweighted digraph 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 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.

Floyd-Warshall

The Floyd-Warshall algorithm finds the distance between each pair of vertices in an arc-weighted digraph.

• floyd_warshall::distances finds the shortest distances.

Predecessor Tree

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

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

Tarjan

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

• tarjan::strongly_connected_components finds strongly connected components.

Re-exports

• pub use repr::AdjacencyList;
• pub use repr::AdjacencyListWeighted;
• 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::Converse;
• pub use op::Degree;
• pub use op::DegreeSequence;
• 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::RandomTournament;
• pub use gen::Star;
• pub use gen::Wheel;
• pub use algo::bellman_ford_moore;
• pub use algo::bfs;
• pub use algo::bfs_dist;
• pub use algo::bfs_pred;
• pub use algo::dfs;
• pub use algo::dfs_dist;
• pub use algo::dfs_pred;
• pub use algo::dijkstra;
• pub use algo::dijkstra_dist;
• pub use algo::dijkstra_pred;
• pub use algo::distance_matrix;
• pub use algo::floyd_warshall;
• pub use algo::predecessor_tree;
• pub use algo::tarjan;
• pub use distance_matrix::DistanceMatrix;
• pub use predecessor_tree::PredecessorTree;

Modules

• algo
  Digraph algorithms
• gen
  Generate parameterized and random digraphs.
• op
  Operations on digraphs
• repr
  Digrpah representations.

Macros

• test_unweighted
  Common tests for unweighted digraphs.