The Tarjan-Lengauer graph dominators algorithm.
 Lengauer, Tarjan, A Fast Algorithm for Finding Dominators in a Flowgraph, 1979.
 Muchnick, Advanced Compiler Design and Implementation, 1997.
 Brisk, Sarrafzadeh, Interference Graphs for Procedures in Static Single Information Form are Interval Graphs, 2007.
TODO: An ST version.
- type Node = Int
- type Path = [Node]
- type Edge = (Node, Node)
- type Graph = IntMap IntSet
- type Rooted = (Node, Graph)
- idom :: Rooted -> [(Node, Node)]
- ipdom :: Rooted -> [(Node, Node)]
- domTree :: Rooted -> Tree Node
- pdomTree :: Rooted -> Tree Node
- dom :: Rooted -> [(Node, Path)]
- pdom :: Rooted -> [(Node, Path)]
- pddfs :: Rooted -> [Node]
- rpddfs :: Rooted -> [Node]
- fromAdj :: [(Node, [Node])] -> Graph
- fromEdges :: [Edge] -> Graph
- toAdj :: Graph -> [(Node, [Node])]
- toEdges :: Graph -> [Edge]
- asTree :: Rooted -> Tree Node
- asGraph :: Tree Node -> Rooted
- parents :: Tree a -> [(a, a)]
- ancestors :: Tree a -> [(a, [a])]
Immediate dominators. O(|E|*alpha(|E|,|V|)), where alpha(m,n) is "a functional inverse of Ackermann's function".
This Complexity bound assumes O(1) indexing. Since we're
IntMap, it has an additional lg |V| factor
somewhere in there. I'm not sure where.