From: Massimiliano Mirra <list@...>
Date: 2002-09-17T10:30:30+09:00
Subject: Re: Dependency "trees" - suggestions?

On Tue, Sep 17, 2002 at 01:37:33AM +0900, Paul Brannan wrote:
> On Tue, Sep 17, 2002 at 12:52:49AM +0900, Massimiliano Mirra wrote:
> > Right now, each time a node is added, an array containing all the
> > possible paths is updated.  If adding the node causes a cycle in one
> > of the paths, an exception is raised.
> 
> You could raise an exception only when you encounter a cycle while
> traversing the graph; if you do this, you need only a Hash containing
> all the nodes (or their ids), so you can tell if you've visited a
> particular node before.

Yes.  This means that for each node I add, the entire graph has to be
traversed again looking checking for cycles.

I'm wondering whether a less expensive method exists (and less
convoluted than the one I'm using now) maybe involving some tricks
with adiancency or incidence matrices.

Massimiliano