29 Nov 2006 00:51: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) |

[5 later articles] |

From: | "Amir Michail" <amichail@gmail.com> |

Newsgroups: | comp.compilers |

Date: | 29 Nov 2006 00:51:06 -0500 |

Organization: | Compilers Central |

References: | 06-11-09606-11-114 |

Keywords: | analysis |

Posted-Date: | 29 Nov 2006 00:51:06 EST |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.