Module petgraph::algo

source ·
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§

Modules§

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 reaching to.
  • 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.
  • sccDeprecated
    Renamed to kosaraju_scc.
  • [Generic] Compute the strongly connected components using Tarjan’s algorithm.
  • [Generic] Perform a topological sort of a directed graph.