Re: finding all dominator trees

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

Return to the comp.compilers page.
Search the comp.compilers archives again.