Dependency Queue

[Stefan Behnel]

Carl Banks wrote:
> 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.

You might consider flattening your graph to map it onto a heap (see the heapq
module). One way to do that might be to assign a different power of two to
each node and calculate the priority of each node as the sum of its parent's
numbers. That way, a child will always have a higher value (== lower priority)
than its parents, so the heap will return it after its parents. If you also
want a unique priority instead of the same one for all children of the same
set of parents, adding the number of the child itself will give you a
(possibly arbitrary) unique priority.

This (or a similar approach) may or may not solve your problem, depending on
how you determine the dependencies.

Stefan