[−][src]Crate toposort_scc
An implementation of Kahn's algorithm for topological sorting and Kosaraju's algorithm for strongly connected components.
This crate provides:
- an adjacency-list based graph data structure (
IndexGraph
) - an implementation of a topological sorting algorithm that runs in
O(V + E)
time andO(V)
additional space (Kahn's algorithm) - an implementation of an algorithm that finds the strongly connected
components of a graph in
O(V + E)
time andO(V)
additional space (Kosaraju's algorithm) - both algorithms are available via the
.toposort_or_scc()
method onIndexGraph
The id-arena
feature adds an additional wrapper type (ArenaGraph
) that
allows topological sorting and finding of strongly connected components on
arbitrary graph structures built with the id-arena
crate by creating a
proxy graph that is sorted and returning a list of indices into the original
graph.
Structs
ArenaGraph | An adjacency-list-based graph data structure wrapping an |
ArenaGraphBuilder | A builder object that allows to easily add edges to a graph |
IndexGraph | An adjacency-list-based graph data structure |
IndexGraphBuilder | A builder object that allows to easily add edges to a graph |
Vertex | A vertex in an |