module Data.Graph.Inductive.Query.Dominators(
dom
) where
import Data.List
import Data.Graph.Inductive.Graph
type DomSets = [(Node,[Node],[Node])]
intersection :: [[Node]] -> [Node]
intersection cs = foldr intersect (head cs) cs
getdomv :: [Node] -> DomSets -> [[Node]]
getdomv vs ds = [z|(w,_,z)<-ds,v<-vs,v==w]
builddoms :: DomSets -> [Node] -> DomSets
builddoms ds [] = ds
builddoms ds (v:vs) = builddoms ((fs++[(n,p,sort(n:idv))])++(tail rs)) vs
where idv = intersection (getdomv p ds)
(n,p,_) = head rs
(fs,rs) = span (\(x,_,_)->x/=v) ds
domr :: DomSets -> [Node] -> DomSets
domr ds vs|xs == ds = ds
|otherwise = builddoms xs vs
where xs = (builddoms ds vs)
dom :: Graph gr => gr a b -> Node -> [(Node,[Node])]
dom g u = map (\(x,_,z)->(x,z)) (domr ld n')
where ld = (u,[],[u]):map (\v->(v,pre g v,n)) (n')
n' = n\\[u]
n = nodes g