Re: Dependency tree resolver in Lua?

[David Given <dg@...>]

On 07/02/11 17:51, Steve Litt wrote:
[...]
> 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

Yes, that's it.

Graphs in their myriad forms are one of the key data structures in any
program; learnéd academics can, and indeed have, spent lifetimes
studying them and producing numerous useful algorithms for doing stuff
to them. Once you can cast your data into a graph the main problem is
figuring what the various tools are called; hence why I had to come up
with my own algorithm for this rather than just googling for
'topological sort'. Sigh. If it helps, a lot of the stuff on that
wikipedia page I've never heard of (quivers? tournaments?).

> 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?

Yes, I am (and in fact my search-for-nodes-with-no-parents code just
does a brute force scan of said table until it finds one; I said it was
crude).

-- 
┌─── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ───── http://www.cowlark.com ─────
│
│ "I have a mind like a steel trap. It's rusty and full of dead mice."
│ --- Anonymous, on rasfc

Attachment: signature.asc
Description: OpenPGP digital signature