16 Aug 2005 11:13:20 -0400

Related articles |
---|

Incremental computation of dominators luque@info.ucl.ac.be (Luis Quesada) (2005-08-13) |

Re: Incremental computation of dominators luque@info.ucl.ac.be (Luis Quesada) (2005-08-16) |

Re: Incremental computation of dominators jeffrey.kenton@comcast.net (Jeff Kenton) (2005-08-24) |

Re: Incremental computation of dominators luque@info.ucl.ac.be (Luis Quesada) (2005-08-31) |

From: | Luis Quesada <luque@info.ucl.ac.be> |

Newsgroups: | comp.compilers |

Date: | 16 Aug 2005 11:13:20 -0400 |

Organization: | Compilers Central |

References: | 05-08-049 |

Keywords: | analysis |

Posted-Date: | 16 Aug 2005 11:13:20 EDT |

Luis Quesada wrote:

*> Dear all,*

*>*

*> I need to compute the vector CN, where CN(i)=CutNodes(g,source,i) (i.e.,*

*> the set of vertexes appearing in all paths from source to i in the*

*> directed graph g). The algorithm that I currently have is the following:*

*>*

*> T0:=DFS(g,source)*

*> for i \in vertexes(g) do*

*> CN(i):= if i \in vertexes(T0) then \emptyset else vertexes(g) end*

*> end*

*> for i \in vertexes(T0) do*

*> T1:=DFS(RemoveVertex(g,i),source)*

*> for j \in vertexes(T0)-vertexes(T1) do*

*> CN(j):=CN(j) \cup {i}*

*> end*

*> end*

*>*

*> Assume that DFS returns the reachability tree. CN(i) is initialized with*

*> \emptyset or vertexes(g) depending on whether i is reached from the*

*> source (the point is that, under our definition, any vertex is a cut*

*> node between the source and i if i is not reached from the source).*

*> Then, we simply try each potential cut node and update the corresponding*

*> sets. So our computation of cut nodes is O(V*(V+E)).*

*>*

*> Eugene Ressler (in comp.theory) made me realize that I am actually*

*> computing dominators. So, my first question is: is my current approach*

*> efficient?*

I found this article that answers this question:

@Article{lengauer79,

author = {T. Lengauer and R. Tarjan},

title = {A Fast Algorithm for Finding Dominators in a Flowgraph},

journal = {ACM Transactions on Programming Languages and Systems},

year = {1979},

*}*

*> I am also looking for an incremental approach since I don't want to*

*> recompute this information from scratch whenever a set of edges is*

*> removed.*

I found this other article that addresses this issue:

@article{sreedhar97incremental,

author = "Vugranam C. Sreedhar and Guang R. Gao and Yong-Fong Lee",

title = "Incremental Computation of Dominator Trees",

journal = "ACM Transactions on Programming Languages and Systems",

volume = "19",

number = "2",

month = "March",

publisher = "ACM Press",

pages = "239--252",

year = "1997",

url = "citeseer.ist.psu.edu/sreedhar95incremental.html" }

Once again, many thanks to Eugene Ressler for pushing me in the right

direction!

Luis

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.