Re: Dependency tree resolver in Lua?

[Steve Litt <slitt@...>]

On Monday 07 February 2011 06:58:51 David Given wrote:
> On 07/02/11 11:27, Alexander Gladysh wrote:

> > Is there a generic-enough dependency tree resolver module for Lua?
> 
> Oddly enough, I just wrote one --- I don't know whether it's *right*,
> but it appears to do the job I need.
> 
> The code is trivial: construct a directed graph of dependencies, where
> each node has edges pointing at the nodes it depends on. Now search the
> graph for a node with no parents. Remove the node (while building,
> logging, outputting it, or whatever). Repeat until there are no nodes
> left. For extra credit check the graph for cycles first.

That is soooooo cool. I never took computer science courses so I'd rather ask 
a dumb question than make a dumb mistake: Can I assume by "directed graph" you 
mean this:

http://en.wikipedia.org/wiki/Directed_graph

Can I safely assume that besides keeping nodes in your directed graph, you 
keep those same nodes as keys in a table for quick lookup in case several 
things depend on one node?

Thanks

SteveT

Steve Litt
Recession Relief Package
http://www.recession-relief.US
Twitter: http://www.twitter.com/stevelitt