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