14 Aug 2002 02:16:36 -0400

Related articles |
---|

[4 earlier articles] |

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: | "Hans Aberg" <haberg@matematik.su.se> |

Newsgroups: | comp.compilers |

Date: | 14 Aug 2002 02:16:36 -0400 |

Organization: | Mathematics |

References: | 02-08-007 02-08-040 |

Keywords: | analysis |

Posted-Date: | 14 Aug 2002 02:16:36 EDT |

"VBDis" <vbdis@aol.com> wrote:

*>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... ;-)*

At least the C++ variation I sent you in the mail puts the components on a

list before writing them out.

So it seems you should merely write out the components of size > 1 plus

the singletons of functions that call themselves, if that is included in

your definition of "recursive".

It should be easy to construct a directed graph putting label on each

vertex of a function that calls itself.

Hans Aberg * Anti-spam: remove "remove." from email address.

* Email: Hans Aberg <remove.haberg@member.ams.org>

* Home Page: <http://www.matematik.su.se/~haberg/>

* AMS member listing: <http://www.ams.org/cml/>

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.