Re: Finding the set of recursive calls

"Hans Aberg" <haberg@matematik.su.se> schreibt:


>So in an undirected graph, Tarjan's algorithm (if hooked up this way)
>merely produces the connected components .


Thanks for the reference to Tarjan's algorithm. AFAIR I had problems,
at least with the implementation of Cristina Cifuentes, and therefore
forgot about that algorithm. Now I read the lecture, which you
mentioned in one of your previous posts, and found it quite easy to
understand. (BTW, how to refer to the other lecture notes?)


[some time later]


I'm not convinced of the implementation, given in the lecture
notes. One paragraph reads:


>>
We use one more simple data structure, a stack L (represented as a list) which
we use to identify the subtree rooted at a vertex. We simply push each new
vertex onto L as we visit it; then when we have finished visiting a vertex, its
subtree will be everything pushed after it onto L. If v is a head, and we've
already deleted the other heads in that subtree, the remaining vertices left on
L will be exactly the component [v].
<<


This algorithm will, as I understand it, include all successors of v
into the component. This means, that all vertices following the vertex
u with the back edge u->v will be included, even if the successors of
u can not reach v! This means that another test must be added, which
ensures that only vertices u with low(u) = v are added to the
component.


From Cristina Cifuentes classification of loops I also remember very
strange cases, which fail to be recognized correctly by various
algorithms. Perhaps somebody can verify, that Tarjan's method, or some
other algorithm, produces the correct components for the following 3
graphs:


G1 contains a loop a-b-a, and another edge b-c. Then IMO the algorithm
described will erroneously include c into the component.


G2 contains 2 loops, a-b-a and a-c-a, i.e. there exist 2 back edges,
in different subtrees of a. A correct algorithm must include both b
and c into the component.


G3 also contains 2 loops, a-b-c-a and b-c-d-b. A correct algorithm
must detect a as the head of the component, and must include into the
component all the nodes, also d!




In addition I still have a problem with the implementation of the
described algorithm, because it removes nodes from the given
graph. Doesn't this removing require a copy of the graph, from which
nodes can be removed as required? And when a node is removed from a
graph, then also all edges to this node must be removed. Doesn't this
increase the order of the algorithm, since then all predecessors of
the removed node are involved?


Wouldn't a better implementation use one more flag, which is set when
a node is removed from the graph, and which must be tested for the
target of every edge, to identify edges to removed nodes?




This leads to the more general question: how to implement methods on
graphs in real life? Most algorithms require specific attributes for
all nodes (dfsnum...), so how can these attributes be implemented in
an efficient way? In most OO languages the properties of an object are
enumerated in the according class declaration, and adding more
properties results in new classes. Otherwise, when properties can be
added dynamically, all references to these properties result in an
overhead to locate that property.


Or does there exist another method, which allows to reference
dynamically added properties as fast as statically defined properties
(runtime behaviour), and to (automatically) remove these properties as
soon as they are no more needed (memory consumption)?




Another question, perhaps the reason for my ignorance of Tarjan's
algorithm:


How to determine the range of a Switch statement in a CFG? In
contrast to loops such a statement (subgraph) has no back-edge. Once
the end point (common successor) of the Switch is determined, a
synthetic edge from that node to the Switch header can be added, and
Tarjan's method can be used to find all nodes in the statement. But
how to find that common successor? In real life CFGs some branches of
the Switch can leave the statement (immediatley or later) with
back-edges or even cross-edges, depending on the optimization of the
compiler.




Thanks for your patience, this thread has inspired me a lot :-)


DoDi

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