Module 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.

Modules

astar

bellman_ford

Bellman-Ford algorithms.

dijkstra

dominators

Compute dominators of a control-flow graph.

feedback_arc_set

floyd_warshall

ford_fulkerson

isomorphism

k_shortest_path

matching

min_spanning_tree

Minimum Spanning Tree algorithms.

page_rank

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.

Matching

Computed matching of the 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).

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

all_simple_paths

Returns an 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, or limited by the graph’s order otherwise. The simple path is a path without repetitions.

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.

find_negative_cycle

[Generic] Find the path of a negative cycle reachable from node source.

floyd_warshall

[Generic] Floyd–Warshall algorithm is an algorithm for all pairs shortest path problem

ford_fulkerson

[Generic] Ford-Fulkerson algorithm.

greedy_feedback_arc_set

[Generic] Finds a feedback arc set: a set of edges in the given directed graph, which when removed, make the graph acyclic.

greedy_matching

[Generic] Compute a matching using a greedy heuristic.

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 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.

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

[Generic] Return true if the graphs g0 and g1 are isomorphic.

is_isomorphic_matching

[Generic] Return true if the graphs g0 and g1 are isomorphic.

is_isomorphic_subgraph

[Generic] Return true if g0 is isomorphic to a subgraph of g1.

is_isomorphic_subgraph_matching

[Generic] Return true if g0 is isomorphic to a subgraph of g1.

k_shortest_path

[Generic] k’th shortest path algorithm.

kosaraju_scc

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

maximum_matching

[Generic] Compute the maximum matching using Gabow’s algorithm.

min_spanning_tree

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

page_rank

[Generic] Page Rank algorithm.

sccDeprecated

Renamed to kosaraju_scc.

subgraph_isomorphisms_iter

Using the VF2 algorithm, examine both syntactic and semantic graph isomorphism (graph structure and matching node and edge weights) and, if g0 is isomorphic to a subgraph of g1, return the mappings between them.

tarjan_scc

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

toposort

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