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.
Modules
Bellman-Ford algorithms.
Compute dominators of a control-flow graph.
Compute the transitive reduction and closure of a directed acyclic graph
Structs
An algorithm error: a cycle was found in the graph.
Workspace for a graph traversal.
An iterator producing a minimum spanning forest of a graph.
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).
Functions
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.
[Generic] A* shortest path algorithm.
[Generic] Compute shortest paths from node source
to all other.
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] Dijkstra’s shortest path algorithm.
[Generic] Find the path of a negative cycle reachable from node source
.
[Generic] Floyd–Warshall algorithm is an algorithm for all pairs shortest path problem
[Generic] Finds a feedback arc set: a set of edges in the given directed graph, which when removed, make the graph acyclic.
[Generic] Compute a matching using a greedy heuristic.
[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 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.
[Generic] Return true
if the input directed graph contains a cycle.
[Generic] Return true
if the input graph contains a cycle.
[Generic] Return true
if the graphs g0
and g1
are isomorphic.
[Generic] Return true
if the graphs g0
and g1
are isomorphic.
[Generic] Return true
if g0
is isomorphic to a subgraph of g1
.
[Generic] Return true
if g0
is isomorphic to a subgraph of g1
.
[Generic] k’th shortest path algorithm.
[Generic] Compute the strongly connected components using Kosaraju’s algorithm.
[Generic] Compute the maximum matching using Gabow’s algorithm.
[Generic] Compute a minimum spanning tree of a graph.
Renamed to kosaraju_scc
.
[Generic] Compute the strongly connected components using Tarjan’s algorithm.
[Generic] Perform a topological sort of a directed graph.