[−][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
- 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)
The id-arena
feature adds an additional wrapper type 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 |