"Carl Banks" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] | 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 -- http://mail.python.org/mailman/listinfo/python-list
