Module petgraph::algo[][src]

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.

Modules

dominators

Compute dominators of a control-flow 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.

Traits

FloatMeasure

A floating-point measure.

Measure

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

Functions

all_simple_paths

Returns iterator that produces all simple paths from from node to to, which contains at least min_intermediate_nodes nodes and at most max_intermediate_nodes, if given, limited by graph’s order otherwise Simple path is path without repetitions Algorithm is adopted from https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.simple_paths.all_simple_paths.html

astar

[Generic] A* shortest path algorithm.

bellman_ford

[Generic] Compute shortest paths from node source to all other.

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.

dijkstra

[Generic] Dijkstra’s shortest path algorithm.

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.

is_isomorphic

Graph Return true if the graphs g0 and g1 are isomorphic.

is_isomorphic_matching

Graph Return true if the graphs g0 and g1 are isomorphic.

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.