30 Nov 2006 02:06:36 -0500

Related articles |
---|

[3 earlier articles] |

Re: finding all dominator trees amichail@gmail.com (Amir Michail) (2006-11-27) |

Re: finding all dominator trees s1l3ntR3p@gmail.com (s1l3ntr3p) (2006-11-28) |

Re: finding all dominator trees amichail@gmail.com (Amir Michail) (2006-11-29) |

Re: finding all dominator trees bmoses-nospam@cits1.stanford.edu (Brooks Moses) (2006-11-29) |

Re: finding all dominator trees s1l3ntR3p@gmail.com (s1l3ntr3p) (2006-11-29) |

Re: finding all dominator trees DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-11-29) |

Re: finding all dominator trees cfc@shell01.TheWorld.com (Chris F Clark) (2006-11-30) |

Re: finding all dominator trees amichail@gmail.com (Amir Michail) (2006-12-03) |

Re: finding all dominator trees diablovision@yahoo.com (2006-12-04) |

Re: finding all dominator trees amichail@gmail.com (Amir Michail) (2006-12-05) |

Re: finding all dominator trees cfc@shell01.TheWorld.com (Chris F Clark) (2006-12-05) |

Re: finding all dominator trees martin@gkc.org.uk (Martin Ward) (2006-12-05) |

Re: finding all dominator trees mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2006-12-06) |

[1 later articles] |

From: | Chris F Clark <cfc@shell01.TheWorld.com> |

Newsgroups: | comp.compilers |

Date: | 30 Nov 2006 02:06:36 -0500 |

Organization: | The World Public Access UNIX, Brookline, MA |

References: | 06-11-096 06-11-117 06-11-125 |

Keywords: | analysis |

Posted-Date: | 30 Nov 2006 02:06:36 EST |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.