Re: Finding the set of recursive calls

"VBDis" <vbdis@aol.com>10 Aug 2002 02:32:49 -0400

From comp.compilers

Related articles
[3 earlier articles]
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)
| List of all articles for this month |

 From: "VBDis" Newsgroups: comp.compilers Date: 10 Aug 2002 02:32:49 -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:32:49 EDT

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

>In a directed graph, the equivalence relation used to define strongly
>connected components is that there are paths both ways between vertices.

In a discussion with Prof. Eppstein it turned out, that a vertex can
form a strongly connected component, even if no explicit path exists
from the vertex back to itself. This is due to the reflexive property
of equivalence relations. Thus the set of recursive procedures is
only a subset of the strongly connected components of an graph.

So in the case of the set of recursive calls I'm not sure, which
algorithms really are applicable without modificiations. The set of
strongly connected components can be used as a base, from which all
single-vertex components must be removed, which have no edges to
themselves.

(I knew that there was a problem... ;-)

DoDi

Post a followup to this message