import StdEnv, StdMaybe
import Data.Map => qualified updateAt
-:: St a = {nextindex :: Int, stack :: [a], map :: Map a Annot, sccs :: [[a]]}
-:: Annot = {index :: Int, lowlink :: Int, onstack :: Bool}
+:: St a = {nextindex :: !Int, stack :: ![a], map :: !Map a Annot, sccs :: ![[a]]}
+:: Annot = {index :: !Int, lowlink :: !Int, onstack :: !Bool}
-scc :: [(a, [a])] -> [[a]] | Eq, Ord a
+scc :: ![(a, [a])] -> [[a]] | Eq, Ord a
scc nodes = reverse (foldr (strongconnect nodes) {nextindex=zero,stack=[],map=newMap,sccs=[]} nodes).sccs
where
- strongconnect :: [(a, [a])] (a, [a]) (St a) -> St a | Eq, Ord a
+ strongconnect :: ![(a, [a])] !(a, [a]) !(St a) -> St a | Eq, Ord a
strongconnect nodes (v, suc) s
| isJust (get v s.map) = s
# s = foldr (processSucc nodes v)
, map = foldr (alter \(Just s)->Just {s & onstack=False}) s.map scc
}
where
- processSucc :: [(a, [a])] a a (St a) -> St a | Eq, Ord a
+ processSucc :: ![(a, [a])] !a !a !(St a) -> St a | Eq, Ord a
processSucc nodes v w s = case get w s.map of
Nothing
# n = filter ((==)w o fst) nodes