Re: finding all dominator trees

Chris F Clark wrote:
> ...
>
> 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.
>


I don't understand this solution. How would it work in this example?


A -> B <-> C


The dominator tree for A:


A
|
B
|
C


The dominator tree for B:


B
|
C


The dominator tree for C:


C
|
B


Amir

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