From: Jim Weirich <jim@...>
Date: 2005-04-07T23:38:09+09:00
Subject: Re: [ANN] Rant 0.3.2


Gavin Kistner said:
> (I'm sorry, I deleted earlier messages in this thread and suddenly
> spotted these lines, so ignore me if what I'm about to say has nothing
> to do with the above context.)

No, it sounds like you are right on context.

> It sounds like you may be trying to solve something I worked on for
> another project long ago - how to traverse a directed graph of
> dependencies with minimal visitation. (If I know that I'm going to have
> to visit another node later on anyhow, don't do it now.)
[...]
> My solution to this problem was to pre-crawl the graph (and my graph
> allowed for cyclic sections, so I had to detect them) and create, for
> each node, an "update chain" of all the nodes that need to be visited
> for each node that may change. You can then walk that chain from back
> to front and throw out any nodes which have already been seen.
[...]
> I have more information on the problem while I was solving it here:
> http://phrogz.net/nodes/traversingdirectedgraph.asp

Thanks Gavin.  I took a look at your reference.  Indeed, it looks like you
are doing a topological sort of the nodes before executing (cf.
http://www.cs.sunysb.edu/~algorith/files/topological-sorting.shtml).  The
algorithm is a bit different than what I have used in the past, but the
result is the same: an ordering of nodes where all the dependents of node
x are to the right of node x.

(Aside: Rubygems uses a topological sort to determine the best order to
remove a set of installed gems.  Look at the dependency_order method here:
http://rubyurl.com/wRkVa [1])

The key is that you have to pre-crawl the graph (i.e. sort the nodes)
before using the resulting ordered node list.

Rake does not do a pre-crawl, but marks nodes as visited as it traverses
the DAG.   This is similar to the topological sort, except that Rake does
it depth-first rather than breadth-first.  The end amount of overall work
is about the same, its just that Rake interweaves the two phases into one.

-- 
-- Jim Weirich     jim@weirichhouse.org    http://onestepback.org
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)

[1]
http://rubyforge.org/cgi-bin/viewcvs.cgi/rubygems/lib/rubygems/dependency_list.rb?rev=1.3&cvsroot=rubygems&content-type=text/vnd.viewcvs-markup).