Algorithm for finding SCC

Andrey Bohanko <bokhanko@my-deja.com>
30 Jun 2000 00:52:58 -0400

          From comp.compilers
Related articles
Algorithm for finding SCC bokhanko@my-deja.com (Andrey Bohanko) (2000-06-30)
| List of all articles for this month |
From: Andrey Bohanko <bokhanko@my-deja.com>
Newsgroups: comp.compilers
Date: 30 Jun 2000 00:52:58 -0400
Organization: Deja.com - Before you buy.
Keywords: theory, question

Hello!


Everybody knows about classical Tarjan's algorithm for finding SCC's
(strongly connected components) of an arbitrary (both reducible and
irreducible) graph, and its application on many tasks of compiler
development (for example, loop tree construction). It has a very good
complexity (linear; i think nobody can beat it in this regard), but in
practice it's not so good (we need to maintain two stacks with
unpredictable dynamic behavior, and this may be very costly). I know
about Havlak's solution of this problem (Havlak, P., "Nesting of
reducible and irreducible loops", ACM TPLS, 16, 6), but his approach
has it's own deficiencies (we need to determine ancestor/descendant
relation of tree nodes, which in not always affordable). I think there
must be more [practically] feasible solution of this problem. What do
you think about this issue? Do you know other approaches to this
problem?


Thanks for your help!

Post a followup to this message

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