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
  • Johnson’s Circuit-Finding Algorithm
  • Predecessor Tree
  • Tarjan

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