Module algo 

This module contains most of petgraph’s algorithms to operate on graphs. Some, very simple search algorithms like depth-first search or breadth-first search are implemented in the visit module.

The algo module contains multiple submodules, each implementing a specific algorithm or set of algorithms. Some functions, like connected_components, are implemented directly in this module.

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 bridges::bridges;

pub use coloring::dsatur_coloring;

pub use dijkstra::bidirectional_dijkstra;

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

pub use johnson::johnson;

pub use k_shortest_path::k_shortest_path;

pub use matching::greedy_matching;

pub use matching::maximum_matching;

pub use matching::Matching;

pub use maximal_cliques::maximal_cliques;

pub use maximum_flow::dinics;

pub use maximum_flow::ford_fulkerson;

pub use min_spanning_tree::min_spanning_tree;

pub use min_spanning_tree::min_spanning_tree_prim;

pub use page_rank::page_rank;

pub use scc::scc;Deprecated

pub use scc::kosaraju_scc::kosaraju_scc;

pub use scc::tarjan_scc::tarjan_scc;

pub use scc::tarjan_scc::TarjanScc;

pub use simple_paths::all_simple_paths;

pub use simple_paths::all_simple_paths_multi;

pub use spfa::spfa;

Modules

articulation_points

astar

bellman_ford

Bellman-Ford algorithms.

bridges

coloring

dijkstra

dominators

Compute dominators of a control-flow graph.

feedback_arc_set

floyd_warshall

ford_fulkerson

isomorphism

johnson

Johnson’s algorithm implementation.

k_shortest_path

matching

maximal_cliques

maximum_flow

Collection of algorithms for the Maximum Flow Problem.

min_spanning_tree

Minimum Spanning Tree algorithms.

page_rank

scc

simple_paths

spfa

Shortest Path Faster Algorithm.

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.

NegativeCycle

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

Traits

BoundedMeasure

FloatMeasure

A floating-point measure.

Measure

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

PositiveMeasure

Some measure of positive numbers, assuming positive float-pointing numbers

UnitMeasure

A floating-point measure that can be computed from usize and with a default measure of proximity.

Functions

condensation

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

connected_components

Return the number of connected components of the graph.

has_path_connecting

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

is_bipartite_undirected

Return true if the graph* is bipartite.

is_cyclic_directed

Return true if the input directed graph contains a cycle.

is_cyclic_undirected

Return true if the input graph contains a cycle.

toposort

Perform a topological sort of a directed graph.