Dependency Queue

[Carl Banks]

I'm looking for any information about a certain kind of dynamic data
structure.  Not knowing if it has some well-known name that I could
have Googled, I'll just call it a dependency queue.  It's like a
priority queue except instead of a strict ordering of items by
priority, there is only a topological ordering (like you would have in
a directed acyclic graph).

To date I've been generating a dependency graph in advance every
iteration through my main loop, doing a topsort, and executing the
values in order (the values are callable objects--this is a
scheduler).

However, I'd like a dynamic dependency queue for two reasons: it would
simplify things to not have to generate the whole graph in advance,
and it could improve performance to run some tasks of the next
iteration in the present one (this could potentially make better use
of the dual-core and graphics hardware).

I'm pretty sure I could hack out this structure on my own, but I'd
like to see any prior information if there is any, in case anyone's
figured out things like, Is there an easy way to detect cycles on
insertion? and so on.


Carl Banks