Dependency Queue

[Carl Banks]

On Apr 7, 1:13 pm, "Terry Reedy" <tjre... at udel.edu> wrote:
> "Carl Banks" <pavlovevide... 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.

Yes, a dynamically updating DAG is probably how I'd implement it,
that's straightforward enough.  What I'm looking for is any prior work
on uncovering properties and useful algorithms for the situations that
would come up.  Like is there a chapter of some book devoted to them?


Carl Banks