Safe Haskell | None |
---|---|

Language | Haskell2010 |

## Synopsis

- type Graph = Vector [Int]
- makeReversedDigraph :: Graph -> Graph
- makeInducedDigraph :: Graph -> Vector Int -> Graph
- decomposeToStronglyConnectedComponents :: Graph -> Vector Int
- topologicalSort :: Graph -> Vector Int

# Documentation

makeReversedDigraph :: Graph -> Graph Source #

decomposeToStronglyConnectedComponents :: Graph -> Vector Int Source #

`decomposeToStronglyConnectedComponents`

does SCC in \(O(V + E)\) using Kosaraju's algorithm.
It takes a digraph \(G = (V, E)\) as an adjacent list \(g : V \to V^{\lt \omega}\), and returns an mapping \(f : V \to V'\) for the SCC DAG \(G' = (V', E')\).
The indices of vertices of the SCC DAG are topologically sorted.

topologicalSort :: Graph -> Vector Int Source #

`topologicalSort`

does topological sort in \(O(V + E)\) using Tarjan's algorithm.
The input is an adjacent list of a DAG.