Re: finding all dominator trees

>> > > 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.


"s1l3ntr3p" <s1l3ntR3p@gmail.com> writes:
> Hi everyone:
>
> Well with the risk of sounding repetitive and I become a pain, u know
> where... Here I come...
> I hope Im not too wrong...
>
> We all have stated what a dominator is: i dominates j (i in Dom(j)) iff
> every posible path P from the entry (root) node n0 to j we have that i
> is in V(P) (Vertex set of P).
>
> What does it tell us? Well, acordding to my coffee and pizza, in Graph
> Theory it tells us that i is a cut vertex. A cut vertex is a vertex of
> a graph such that when u remove it from the graph and all edges
> incidents to it we desconects at least 2 vertices of the graph, i.e. we
> have more components.
>
...
> As a note: If we have a strongly connected graph G then we do not have
> any dominator but the nodes themselfs that it seems they wouldnt work
> for you.
>
> As I said, I dont know if Im right or Im wrong...
>
> Alfredo Cruz


Yes, there are more efficient algorithms for computing the sets of
dominators in a graph considering each vertex in the graph as a root.
Both reachable vertexes and strongly-connected-components (cycles)* are
part of the algorithm.


First, if there is one unique vertex that can reach all other vertexes
(verticies if you prefer) in the graph, consider that vertex the root.
The dominator algorithm given that root will calculate the correct
dominators (the dominator tree) for every vertex (v1) in the graph
assuming that each other vertex (v2) is the root. That is, for any
target vertex v1 and root vertex v2, some vertex in the dominator tree
of v1 will be the dominator of v1 given the root v2.


Note, in the above case, the root had no incoming edges (and is the
only vertex with no incoming edges). So, the next generallization is
to deal with multiple vertexes with no-incoming edges. If there is
more than one vertex in the graph with no-incoming edges, create a
fake-root vertex and draw an edge from that fake-root to each vertex
that has no-incoming edges. Now, run the dominator algorithm from
that root, and the algorithm will work correctly again.


We, are left now, with only the case where all of the vertexes of the
graph have incoming edges. In that case, all the vertexes in the
graph are elements of strongly-connected-components (cycles). Assume
without-loss-of generality that there is one cycle which contains all
the vertexes of the graph. We can assume that because, the second
part of this explanation showed us how to deal with disjoint graphs by
making a fake-root to join them. The only question is how to pick a
root element for a cycle. If you work through the dominator
algorithm, you will see that picking any element that is part of the
"outermost" cycle (and not part of any inner cycles), will achieve the
same results.


That should give you enough hints that you can work through the
possibilities and fill out the algortihm (and prove that it works once
you have it filled out), so I'll leave the rest to you. The basic
point is the you can either select a root from the given graph (or
construct a fake-root if no appropriate element of the given graph
exists) and from that [fake-]root, run the normal dominator algorithm
once and get the data you need. You don't need to run the dominator
algorithm n-times considering each distinct vertex a root.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------


* from above, If I recall correctly, a strongly-connected-component is
    a set of vertexes such that each element in the set is reachable
    from any other element in the set. If that is not true (because an
    scc is something else), then that set is a cycle (it is a cycle even
    if it is also known as an scc). I think the terms scc and cycle are
    synonymous, but I haven't used the term scc in so long, I may be
    incorrect on its definition (and in which case, I just mean cycle).

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