Re: finding all dominator trees

Amir Michail wrote:
> diablovision@yahoo.com wrote:
> > > Is there an efficient algorithm for finding all dominator trees of a
> > > graph? That is, for every node, find its dominator tree. I'm looking
> > > for something better than simply running a dominator tree algorithm
> > > for each node in the graph.
> >
> > Unless I am missing some subtlety of your situation, you should just be
> > able to run the dominator tree algorithm for the root node of the
> > graph. Dominator trees have the property that each subtree for a node
> > corresponds to the dominator tree for that node.
> >
>
> There is no root. This is an arbitrary graph.
>
> Amir
>
> > See "Efficiently Computing Static Single Assignment Form and the
> > Control Dependence Graph" by Cytron et al.




This is from Torczon's book: "In a CFG, node i <dominates> node j if
every path from the entry node to j passes through i". What this tells
us is that we need a root (entry) node.


Suppose that we have a graph G, directed or not, doesnt matter, and
lets say that i, j are in V(G) (G's vertex set), now 1) i dom j, or 2)
j dom i or 3) neither. How can we know that if we dont have a root
node from where to start?. In teo. all 3 are posible. If we take a
node "n" as a root (the node from which my paths will start) then it
could happen that i dom j. But if we take a node "m", "m \== n" it
could happen that j dom i. So either u have a root node already or u
choose one (it doesnt matter) or u try every posible node, O(V(G) *
O(Dom)). Something like that. But if u do that, I feel that many
cases are going to repeat or it could be like a fixed point algorithm
for all the graph. Domination can be computed using fix point.


Alfredo Cruz

Return to the comp.compilers page.
Search the comp.compilers archives again.