Expand description
Graph algorithms.
It is a goal to gradually migrate the algorithms to be based on graph traits
so that they are generally applicable. For now, some of these still require
the Graph
type.
Re-exports§
pub use astar::astar;
pub use bellman_ford::bellman_ford;
pub use bellman_ford::find_negative_cycle;
pub use dijkstra::dijkstra;
pub use feedback_arc_set::greedy_feedback_arc_set;
pub use floyd_warshall::floyd_warshall;
pub use ford_fulkerson::ford_fulkerson;
pub use isomorphism::is_isomorphic;
pub use isomorphism::is_isomorphic_matching;
pub use isomorphism::is_isomorphic_subgraph;
pub use isomorphism::is_isomorphic_subgraph_matching;
pub use isomorphism::subgraph_isomorphisms_iter;
pub use k_shortest_path::k_shortest_path;
pub use matching::greedy_matching;
pub use matching::maximum_matching;
pub use matching::Matching;
pub use min_spanning_tree::min_spanning_tree;
pub use page_rank::page_rank;
pub use simple_paths::all_simple_paths;
Modules§
- Bellman-Ford algorithms.
- Compute dominators of a control-flow graph.
- Minimum Spanning Tree algorithms.
- Compute the transitive reduction and closure of a directed acyclic graph
Structs§
- An algorithm error: a cycle was found in the graph.
- Workspace for a graph traversal.
- An algorithm error: a cycle of negative weights was found in the graph.
- A reusable state for computing the strongly connected components using Tarjan’s algorithm.
Traits§
- A floating-point measure.
- Associated data that can be used for measures (such as length).
- Some measure of positive numbers, assuming positive float-pointing numbers
- A floating-point measure that can be computed from
usize
and with a default measure of proximity.
Functions§
- Graph Condense every strongly connected component into a single node and return the result.
- [Generic] Return the number of connected components of the graph.
- [Generic] Check if there exists a path starting at
from
and reachingto
. - Return
true
if the graph is bipartite. A graph is bipartite if its nodes can be divided into two disjoint and indepedent sets U and V such that every edge connects U to one in V. This algorithm implements 2-coloring algorithm based on the BFS algorithm. - [Generic] Return
true
if the input directed graph contains a cycle. - [Generic] Return
true
if the input graph contains a cycle. - [Generic] Compute the strongly connected components using Kosaraju’s algorithm.
- sccDeprecatedRenamed to
kosaraju_scc
. - [Generic] Compute the strongly connected components using Tarjan’s algorithm.
- [Generic] Perform a topological sort of a directed graph.