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

 

[Stefan Behnel]

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

 

[Terry Reedy]

| 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

 

[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.

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