[−][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.
Example
This example creates an IndexGraph
of the example graph from the
Wikipedia page for
Topological sorting.
A copy of the graph with cycles in it is created to demonstrate finding of strongly connected components.
use toposort_scc::IndexGraph; let g = IndexGraph::from_adjacency_list(&vec![ vec![3], vec![3, 4], vec![4, 7], vec![5, 6, 7], vec![6], vec![], vec![], vec![] ]); let mut g2 = g.clone(); g2.add_edge(0, 0); // trivial cycle [0] g2.add_edge(6, 2); // cycle [2, 4, 6] assert_eq!(g.toposort_or_scc(), Ok(vec![0, 1, 2, 3, 4, 5, 7, 6])); assert_eq!(g2.toposort_or_scc(), Err(vec![vec![0], vec![4, 2, 6]]));
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 |