[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Dependency tree resolver in Lua?
- From: David Given <dg@...>
- Date: Mon, 07 Feb 2011 20:28:12 +0000
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:
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
┌─── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ───── http://www.cowlark.com ─────
│ "I have a mind like a steel trap. It's rusty and full of dead mice."
│ --- Anonymous, on rasfc
Description: OpenPGP digital signature