### 11 releases (4 breaking)

0.5.4 | Jul 24, 2020 |
---|---|

0.5.3 | Jul 24, 2020 |

0.4.0 | Jul 24, 2020 |

0.3.1 | Jul 24, 2020 |

0.1.1 | Jul 23, 2020 |

#**889** in Algorithms

**85** downloads per month

**MIT/Apache**

32KB

305 lines

`toposort-scc`

`toposort-scc`

An implementation of Kahn's algorithm for topological sorting and Kosaraju's algorithm for strongly connected components.

- an adjacency-list based graph data structure (

)`IndexGraph` - an implementation of a topological sorting algorithm that runs in

time and`O``(`V`+`E`)`

additional space (Kahn's algorithm)`O``(`V`)` - an implementation of an algorithm that finds the strongly connected
components of a graph in

time and`O``(`V`+`E`)`

additional space (Kosaraju's algorithm)`O``(`V`)` - both algorithms are available either as single methods (

and`.``toposort``(``)`

) or as a combined method (`.``scc``(``)`

) on`.``toposort_or_scc``(``)``IndexGraph`

The

feature adds an additional wrapper type (`id-arena`

) that
allows topological sorting and finding of strongly connected components on
arbitrary graph structures built with the `ArenaGraph`

crate by creating a
proxy graph that is sorted and returning a list of indices into the original
graph.`id-arena`

## Example

This example creates an

of the example graph from the
Wikipedia page for
Topological sorting.`IndexGraph`

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``]``]``)``)``;`

## Documentation

Documentation is provided via rustdoc, and can be built with

, or
viewed online at
docs.rs/toposort-scc/.`cargo`` doc`

## License

Licensed under either of

- Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

## Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.