29 Nov 2006 11:08:06 -0500

Related articles |
---|

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

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

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

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

[3 later articles] |

From: | "s1l3ntr3p" <s1l3ntR3p@gmail.com> |

Newsgroups: | comp.compilers |

Date: | 29 Nov 2006 11:08:06 -0500 |

Organization: | Compilers Central |

References: | 06-11-09606-11-117 |

Keywords: | analysis |

Amir Michail wrote:

*> s1l3ntr3p wrote:*

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

*>*

*> The idea is to consider each node in turn as a root and build a*

*> dominator tree with respect to that root. A naive way to do this is to*

*> run a dominator tree algorithm for each such root separately.*

*>*

*> But maybe there's a more efficient way (even though the relationship*

*> between these dominator trees may not be obvious in general).*

*>*

*> The application here has nothing to do with compilers: I would like to*

*> compute a dominator tree for each person in a social network to build*

*> a better social news service:*

*>*

*> http://targetyournews.com/ajax/TargetYourNews.html>md%3DMore%26link_id%3D656584*

*>*

*> Amir*

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.

So, lets say we have a graph G and cut vertices i,j,k then the cut is:

(V, V-C) where C={i,j,k}. Now if we remove i from G, we know that we

have at least 2 components. Lets call them K1 and K2. Now is it true

that i dominates each node of K2 (K1) when the root node is in K1 (K2)?

I guess it is. Then the problem in our hands is reduced to know all the

cut vertices of a graph G, and if that problem has something is many

many solutions. The naive solution runs in time O(V(G)*E(G)), a more

smart solution, still "easy" was proposed by Robert E. Tarjan (whos

work in compilers is well know) using DFS or BFS around 1970's and it

runs in O(V(G) + E(G)). But there is a lot of work on that specialy if

u know certain caracteristics of ur graph (I have read the link u

posted Amir... and Im not quite sure that the graph would follow a

predeterminate "shape"). For example, Hon-Chan Chen proposed a linear

algorithm to discover cut vertices and bridges (the same as cut

vertices but with edges) in trapeziod graphs. Etc. U can also check

parallel algoriths for that propouse, for example, u could check

Roosta's book: Seyed H. Roosta, "Parallel Processing and Parallel

Algorithms, Theory and Computation", Springer-Verlag, 2000.

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.