dependency algorithm

Discussion in 'Python' started by Tom Jones, Nov 14, 2007.

  1. Tom Jones

    Tom Jones Guest

    Hi,

    Consider tuples of the above numbers in the form:
    (a,b)

    Suppose this relation means:
    a depends on b

    Given a list of tuples, I would like an algorithm to return the proper
    ordering of the elements...and if the ordering has a loop (which in this
    case, prevents a proper ordering), then it should return None.

    For example,


    [(1,2),(2,3),(3,4)]
    should give:
    [4,3,2,1]


    [(3,2),(1,3),(2,4)]
    should give:
    [4,2,3,1]


    [(1,4),(4,3),(2,3)]
    should give:
    [3,2,4,1] or [3,4,2,1] (which one doesn't matter)


    [(1,2), (2,3), (3,2)]
    should give
    None, since it cannot be resolved


    I'm sure this is a standard problem (mro, resolving inheritance?), but
    this is a simplified case since each element can directly depend on only
    one other element (thus, multiple inheritance is not allowed)...but many
    elements can depend on the same element (no limit on the number of
    classes which subclass another class). A quick hack is simple enough to
    code, but I am wondering if there are 'standard' ways of performing this
    task in this limited scope.

    Thanks.
    Tom Jones, Nov 14, 2007
    #1
    1. Advertising

  2. Tom Jones wrote:
    > Hi,
    >
    > Consider tuples of the above numbers in the form:
    > (a,b)
    >
    > Suppose this relation means:
    > a depends on b
    >
    > Given a list of tuples, I would like an algorithm to return the proper
    > ordering of the elements...and if the ordering has a loop (which in this
    > case, prevents a proper ordering), then it should return None.
    >

    You want what's called a topological sort, see:

    http://blog.vrplumber.com/scripts/toposort.py

    for a pair of old algorithms from Tim Peters and I. I believe we raise
    errors on loops, but that's pretty trivial to change.

    Have fun,
    Mike

    --
    ________________________________________________
    Mike C. Fletcher
    Designer, VR Plumber, Coder
    http://www.vrplumber.com
    http://blog.vrplumber.com
    Mike C. Fletcher, Nov 14, 2007
    #2
    1. Advertising

  3. Tom Jones

    Robert Kern Guest

    Tom Jones wrote:
    > Hi,
    >
    > Consider tuples of the above numbers in the form:
    > (a,b)
    >
    > Suppose this relation means:
    > a depends on b
    >
    > Given a list of tuples, I would like an algorithm to return the proper
    > ordering of the elements...and if the ordering has a loop (which in this
    > case, prevents a proper ordering), then it should return None.


    Google for "topological sort python". There are several implementations out there.

    --
    Robert Kern

    "I have come to believe that the whole world is an enigma, a harmless enigma
    that is made terrible by our own mad attempt to interpret it as though it had
    an underlying truth."
    -- Umberto Eco
    Robert Kern, Nov 14, 2007
    #3
  4. Tom Jones schrieb:
    > Hi,
    >
    > Consider tuples of the above numbers in the form:
    > (a,b)
    >
    > Suppose this relation means:
    > a depends on b
    >
    > Given a list of tuples, I would like an algorithm to return the proper
    > ordering of the elements...and if the ordering has a loop (which in this
    > case, prevents a proper ordering), then it should return None.
    >
    > For example,
    >
    >
    > [(1,2),(2,3),(3,4)]
    > should give:
    > [4,3,2,1]
    >
    >
    > [(3,2),(1,3),(2,4)]
    > should give:
    > [4,2,3,1]
    >
    >
    > [(1,4),(4,3),(2,3)]
    > should give:
    > [3,2,4,1] or [3,4,2,1] (which one doesn't matter)
    >
    >
    > [(1,2), (2,3), (3,2)]
    > should give
    > None, since it cannot be resolved
    >
    >
    > I'm sure this is a standard problem (mro, resolving inheritance?), but
    > this is a simplified case since each element can directly depend on only
    > one other element (thus, multiple inheritance is not allowed)...but many
    > elements can depend on the same element (no limit on the number of
    > classes which subclass another class). A quick hack is simple enough to
    > code, but I am wondering if there are 'standard' ways of performing this
    > task in this limited scope.


    http://en.wikipedia.org/wiki/Topological_sorting

    Diez
    Diez B. Roggisch, Nov 14, 2007
    #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. Replies:
    17
    Views:
    10,976
    Tim Hubberstey
    Apr 6, 2005
  2. danpres2k
    Replies:
    0
    Views:
    1,456
    danpres2k
    Aug 13, 2003
  3. martin
    Replies:
    1
    Views:
    554
    Steve C. Orr [MVP, MCSD]
    Oct 18, 2003
  4. Ahmed Moustafa
    Replies:
    0
    Views:
    764
    Ahmed Moustafa
    Nov 15, 2003
  5. Bapaiah Katepalli
    Replies:
    1
    Views:
    1,481
    Mike Treseler
    Jun 23, 2006
Loading...

Share This Page