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

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

min_spanning_tree

Minimum Spanning Tree algorithms.

page_rank

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.

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

Calculate all simple paths with specified constraints from node from to node to.

astar

[Generic] A* shortest path algorithm.

bellman_ford

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

bridges

Find all bridges in a simple undirected graph.

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.

dsatur_coloring

[Generic] DStatur algorithm to properly color a non weighted undirected graph.

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 in the Edmonds-Karp variation.

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.

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.

johnson

[Generic] Johnson algorithm for all pairs shortest path problem.

k_shortest_path

[Generic] k’th shortest path algorithm.

kosaraju_scc

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

maximal_cliques

Find all maximal cliques in an undirected graph using Bron–Kerbosch algorithm with pivoting. Also works on symmetric directed graphs, see the note below.

maximum_matching

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

min_spanning_tree

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

min_spanning_tree_prim

[Generic] Compute a minimum spanning tree of a graph using Prim’s algorithm.

page_rank

[Generic] Page Rank algorithm.

sccDeprecated

Renamed to kosaraju_scc.

spfa

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

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.