Dependency Queue

[Terry Reedy]

"Carl Banks" <pavlovevidence at gmail.com> wrote in message 
news:0309251d-fba9-447c-9b17-f512988103ea at e39g2000hsf.googlegroups.com...
| 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.

Perhaps what you want is a dynamic DAG (directed acyclic graph) with 
ordered labels.  At any time, only the set of sources are eligible for 
execution, so there is no reason to flatten the whole thing.  I suspect 
insertion with cycle detection would be easier, but I don't remember 
actually seeing an algorithm.

tjr