From: Gavin Kistner <gavin@...>
Date: 2005-04-07T21:40:06+09:00
Subject: Re: [ANN] Rant 0.3.2

On Apr 6, 2005, at 10:56 PM, Jim Weirich wrote:

> On Wednesday 06 April 2005 09:09 pm, Lionel Thiry wrote:
>> I have forgotten one, the way tasks are executed. You can execute the 
>> TDG
>> in such a way that you don't have to check repeatedly each task to 
>> know if
>> it has already been executed. You just begin at the right starting 
>> nodes
>> and follows the arrows.
>>
>> Well, that's what I thought until I tried to code that myself. What a
>> nightmare! :)
>
> Hmmm ... I suppose you could do a topological sort on the nodes of the 
> DAG and
> execute them in reverse order.  There might be some dynamic behavior 
> that is
> lost with that approach.  And I'm not sure you would do any /less/ 
> checking
> doing the sort.

(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.)

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

For example, if "A->B" means that B depends on A and should be 
re-evaluated if A changes, and you have a dependency list like:

A->D
B->C
A->B
C->D

Then a naive traversal when A changes might be:
D, B, C, D

...which would be inefficient.


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.

The end result are simple pre-computed chains that are fast to traverse 
when the time comes to change a node. (In my case, the problem was for 
Excel-like functionality in web pages, running and re-running multiple 
dependent formulae as values change in various fields.)

I have more information on the problem while I was solving it here:
http://phrogz.net/nodes/traversingdirectedgraph.asp
and had been thinking of porting the solution to Ruby anyhow.


--
"When I am working on a problem I never think about beauty. I only 
think about how to solve the problem. But when I have finished, if the 
solution is not beautiful, I know it is wrong."
- R. Buckminster Fuller