# [−][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 and `O(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 and `O(V)` additional space (Kosaraju's algorithm)
• both algorithms are available either as single methods (`.toposort()` and `.scc()`) or as a combined method (`.toposort_or_scc()`) on `IndexGraph`

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;

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 `Arena` from the `id-arena` crate. 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 `IndexGraph`