Incremental computation of dominators

Luis Quesada <luque@info.ucl.ac.be>
13 Aug 2005 00:24:31 -0400

          From comp.compilers

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)
| List of all articles for this month |

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
Posted-Date: 13 Aug 2005 00:24:31 EDT

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.