10 Aug 2002 02:03:18 -0400

Related articles |
---|

[2 earlier articles] |

Re: Finding the set of recursive calls dietz@dls.net (Paul F. Dietz) (2002-07-24) |

Re: Finding the set of recursive calls Martin.Ward@durham.ac.uk (Martin Ward) (2002-07-24) |

Re: Finding the set of recursive calls vbdis@aol.com (VBDis) (2002-07-24) |

Re: Finding the set of recursive calls jeremy.wright@microfocus.com (Jeremy Wright) (2002-07-25) |

Re: Finding the set of recursive calls vbdis@aol.com (VBDis) (2002-07-31) |

Re: Finding the set of recursive calls haberg@matematik.su.se (Hans Aberg) (2002-08-04) |

Re: Finding the set of recursive calls vbdis@aol.com (VBDis) (2002-08-10) |

Re: Finding the set of recursive calls vbdis@aol.com (VBDis) (2002-08-10) |

Re: Finding the set of recursive calls haberg@matematik.su.se (Hans Aberg) (2002-08-14) |

From: | "VBDis" <vbdis@aol.com> |

Newsgroups: | comp.compilers |

Date: | 10 Aug 2002 02:03:18 -0400 |

Organization: | AOL Bertelsmann Online GmbH & Co. KG http://www.germany.aol.com |

References: | 02-08-007 |

Keywords: | analysis |

Posted-Date: | 10 Aug 2002 02:03:18 EDT |

"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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.