-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Tarjan's algorithm for computing the strongly connected components of a graph.
--   
--   Tarjan's algorithm for computing the strongly connected components of
--   a graph.
@package GraphSCC
@version 1.0

module Data.Graph.SCC

-- | Computes the strongly connected components (SCCs) of the graph in
--   O(vertices) time. The resulting tuple contains: * A (reversed)
--   topologically sorted list of SCCs. Each SCCs is assigned a unique
--   identifier of type <a>Int</a>. * An O(1) mapping from vertices in the
--   original graph to the identifier of their SCC. This mapping will raise
--   an <a>out of bounds</a> exception if it is applied to integers that do
--   not correspond to vertices in the input graph.
--   
--   This function assumes that the adjacency lists in the original graph
--   mention only nodes that are in the graph. Violating this assumption
--   will result in <a>out of bounds</a> array exception.
scc :: Graph -> ([(Int, [Vertex])], Vertex -> Int)

-- | Compute the list of strongly connected components of a graph. The
--   components are topologically sorted: if v1 in C1 points to v2 in C2,
--   then C2 will come before C1 in the list.
sccList :: Graph -> [SCC Vertex]

-- | Compute the list of strongly connected components of a graph. Each
--   component contains the adjecency information from the original graph.
--   The components are topologically sorted: if v1 in C1 points to v2 in
--   C2, then C2 will come before C1 in the list.
sccListR :: Graph -> [SCC (Vertex, [Vertex])]

-- | Quotient a graph with the relation that relates vertices that belong
--   to the same SCC. The vertices in the new graph are the SCCs of the old
--   graph, and there is an edge between two components, if there is an
--   edge between any of their vertices. The entries in the resulting list
--   are in reversed-topologically sorted: if v1 in C1 points to v2 in C2,
--   then C1 will come before C2 in the list.
sccGraph :: Graph -> [(SCC Int, Int, [Int])]
stronglyConnComp :: (Ord key) => [(node, key, [key])] -> [SCC node]
stronglyConnCompR :: (Ord key) => [(node, key, [key])] -> [SCC (node, key, [key])]