Module algo

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§

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§

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_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.
with_dfs 🔒: Create a Dfs if it’s needed

Type Aliases§