Moduledom-lt-0.2.3Haskell2010

Data.Graph.Dom

The Lengauer-Tarjan graph dominators algorithm.

1 Lengauer, Tarjan, A Fast Algorithm for Finding Dominators in a Flowgraph, 1979.

2 Muchnick, Advanced Compiler Design and Implementation, 1997.

3 Brisk, Sarrafzadeh, Interference Graphs for Procedures in Static Single Information Form are Interval Graphs, 2007.

Strictness

Unless stated otherwise all exposed functions might fully evaluate their input but are not guaranteed to do so.

5 types
16 values

Packagedom-lt-0.2.3
Exports21
LanguageHaskell2010
LicenceBSD-3-Clause
SourceDom.hs

typetype Node = Int

typetype Path = [Node]

typetype Edge = (Node, Node)

typetype Graph = IntMap IntSet

typetype Rooted = (Node, Graph)

valueidom :: Rooted -> [(Node, Node)]

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 using IntMap, it has an additional lg |V| factor somewhere in there. I'm not sure where.

valueipdom :: Rooted -> [(Node, Node)]

Immediate post-dominators. Complexity as for idom.

valuedomTree :: Rooted -> Tree Node

Dominator tree. Complexity as for idom.

valuepdomTree :: Rooted -> Tree Node

Post-dominator tree. Complexity as for idom.

valuedom :: Rooted -> [(Node, Path)]

Dominators. Complexity as for idom

valuepdom :: Rooted -> [(Node, Path)]

Post-dominators. Complexity as for idom.

valuepddfs :: Rooted -> [Node]

Post-dominated depth-first search.

valuerpddfs :: Rooted -> [Node]

Reverse post-dominated depth-first search.

valuefromAdj :: [(Node, [Node])] -> Graph

valuefromEdges :: [Edge] -> Graph

valuetoAdj :: Graph -> [(Node, [Node])]

valuetoEdges :: Graph -> [Edge]

valueasTree :: Rooted -> Tree Node

valueasGraph :: Tree Node -> Rooted

valueparents :: Tree a -> [(a, a)]

valueancestors :: Tree a -> [(a, [a])]