lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

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

┌─── ───── ─────
│ "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