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 -- http://mail.python.org/mailman/listinfo/python-list
