| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Jikka.Common.Graph
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.