13 Aug 2005 00:24:31 -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: | 13 Aug 2005 00:24:31 -0400 |

Organization: | -= Belgacom Usenet Service =- |

Keywords: | analysis, question |

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 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. One alternative could be to come up with an incremental

implementation of DFS (since we only need to look at the DFS tree).

However, I still don't know how to implement DFS incrementally.

Thanks in advance for your help!

Luis

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.