Dependency Queue

Discussion in 'Python' started by Carl Banks, Apr 7, 2008.

  1. Carl Banks

    Carl Banks Guest

    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
    Carl Banks, Apr 7, 2008
    #1
    1. Advertising

  2. 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
    Stefan Behnel, Apr 7, 2008
    #2
    1. Advertising

  3. Carl Banks

    Terry Reedy Guest

    "Carl Banks" <> wrote in message
    news:...
    | 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
    Terry Reedy, Apr 7, 2008
    #3
  4. Carl Banks

    Carl Banks Guest

    On Apr 7, 1:13 pm, "Terry Reedy" <> wrote:
    > "Carl Banks" <> wrote in message
    >
    > news:...
    > | 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
    Carl Banks, Apr 7, 2008
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Paul L. Du Bois

    Queue.Queue-like class without the busy-wait

    Paul L. Du Bois, Mar 24, 2005, in forum: Python
    Replies:
    29
    Views:
    1,032
    Antoon Pardon
    Apr 4, 2005
  2. Russell Warren

    Is Queue.Queue.queue.clear() thread-safe?

    Russell Warren, Jun 22, 2006, in forum: Python
    Replies:
    4
    Views:
    654
    Russell Warren
    Jun 27, 2006
  3. Kceiw
    Replies:
    3
    Views:
    973
    Jim Langston
    Mar 14, 2006
  4. Gabriel Rossetti
    Replies:
    3
    Views:
    489
    Jerry Hill
    Apr 25, 2008
  5. Kris
    Replies:
    0
    Views:
    427
Loading...

Share This Page