Module petgraph::algo

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 isomorphism::is_isomorphic;

pub use isomorphism::is_isomorphic_matching;

pub use isomorphism::is_isomorphic_subgraph;

pub use isomorphism::is_isomorphic_subgraph_matching;

pub use k_shortest_path::k_shortest_path;

pub use matching::greedy_matching;

pub use matching::maximum_matching;

pub use matching::Matching;

pub use simple_paths::all_simple_paths;

Modules

astar

bellman_ford

Bellman-Ford algorithms.

dijkstra

dominators

Compute dominators of a control-flow graph.

feedback_arc_set

floyd_warshall

isomorphism

k_shortest_path

matching

simple_paths

tred

Compute the transitive reduction and closure of a directed acyclic graph

Structs

Cycle

An algorithm error: a cycle was found in the graph.

DfsSpace

Workspace for a graph traversal.

MinSpanningTree

An iterator producing a minimum spanning forest of a graph.

NegativeCycle

An algorithm error: a cycle of negative weights was found in the graph.

TarjanScc

A reusable state for computing the strongly connected components using Tarjan’s algorithm.

Traits

BoundedMeasure

FloatMeasure

A floating-point measure.

Measure

Associated data that can be used for measures (such as length).

Functions

condensation

Graph Condense every strongly connected component into a single node and return the result.

connected_components

[Generic] Return the number of connected components of the graph.

has_path_connecting

[Generic] Check if there exists a path starting at from and reaching to.

is_bipartite_undirected

Return true if the graph is bipartite. A graph is bipartite if it’s 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.

is_cyclic_directed

[Generic] Return true if the input directed graph contains a cycle.

is_cyclic_undirected

[Generic] Return true if the input graph contains a cycle.

kosaraju_scc

[Generic] Compute the strongly connected components using Kosaraju’s algorithm.

min_spanning_tree

[Generic] Compute a minimum spanning tree of a graph.

sccDeprecated

Renamed to kosaraju_scc.

tarjan_scc

[Generic] Compute the strongly connected components using Tarjan’s algorithm.

toposort

[Generic] Perform a topological sort of a directed graph.