```{-# LANGUAGE CPP #-}
module Data.Graph.SCC
( scc
, sccList
, sccListR
, sccGraph
, stronglyConnComp
, stronglyConnCompR
) where

#ifdef USE_MAPS
import Data.Graph.MapSCC
#else
import Data.Graph.ArraySCC
#endif
import Data.Graph(SCC(..),Graph,Vertex,graphFromEdges')

import Data.Array as A
import Data.List(nub)

-- | 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]
sccList g = reverse \$ map (to_scc g lkp) cs
where (cs,lkp) = scc g

-- | 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])]
sccListR g = reverse \$ map cvt cs
where (cs,lkp) = scc g
cvt (n,[v]) = let adj = g ! v
in if  n `elem` map lkp adj
cvt (_,vs)  = CyclicSCC [ (v, g ! v) | v <- vs ]

-- | 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])]
sccGraph g = map to_node cs
where (cs,lkp) = scc g
to_node x@(n,this) = ( to_scc g lkp x
, n
, nub \$ concatMap (map lkp . (g !)) this
)

stronglyConnComp :: Ord key => [(node, key, [key])] -> [SCC node]
stronglyConnComp es = reverse \$ map cvt cs
where (g,back)    = graphFromEdges' es
(cs,lkp)    = scc g
cvt (n,[v]) = let (node,_,_) = back v
in if n `elem` map lkp (g ! v)
then CyclicSCC [node]
else AcyclicSCC node
cvt (_,vs)  = CyclicSCC [ node | (node,_,_) <- map back vs ]

stronglyConnCompR :: Ord key => [(node, key, [key])] -> [SCC (node, key, [key])]
stronglyConnCompR es = reverse \$ map cvt cs
where (g,back)    = graphFromEdges' es
(cs,lkp)    = scc g
cvt (n,[v]) = if n `elem` map lkp (g ! v)
then CyclicSCC [back v]
else AcyclicSCC (back v)
cvt (_,vs)  = CyclicSCC (map back vs)

--------------------------------------------------------------------------------
to_scc :: Graph -> (Vertex -> Int) -> (Int,[Vertex]) -> SCC Vertex
to_scc g lkp (n,[v]) = if n `elem` map lkp (g ! v) then CyclicSCC [v]
else AcyclicSCC v
to_scc _ _ (_,vs)    = CyclicSCC vs

```