dependency algorithm

Henry henry.robinson at gmail.com
Thu Nov 15 01:02:45 CET 2007


Hi -

You want to linearise a dependency graph. The standard way to do this is to
do a depth first search on the graph and output the nodes in reverse order
of their finishing times (although your example looks like you want them in
the reverse order, that is starting with the node on which nothing depends
rather than the node that depends on nothing). Doing this iteratively is a
bit of a pain because you have to keep track of the 'current' node, doing it
recursively is a no-no for large graphs because the stack will have depth
O(E) in the worst case.

What follows is a simple linearisation that doesn't a) detect loops or b) do
things iteratively which puts the stack at risk. I almost find it easier to
do a separate loop check via very similar means. Excuse the un-idiomatic
nature of the code, I'm not yet a proper pythonista :)

edges = [ (0,1), (1,2), (2,3) ]
n = 4

adj_list = [ [[ e for (s,e) in edges if s == i ], False ] for i in xrange(n)
] # You seem to be 1-based, but I've ignored that here

def linearise( adj ):
    order = []
    for i in xrange( len( adj ) ):
        visit( i, adj, order )
    return order

def visit( i, adj, order ):
    if adj[i][1] == True:
        return

    adj[i][1] = True

    for child in adj[i][0]:
        visit( child, adj, order )

    order.append( i )

HTH,

Henry



On 14/11/2007, Tom Jones <thomasjones at hotmail.com> 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.
>
> 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.
> --
> http://mail.python.org/mailman/listinfo/python-list
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20071115/b211d015/attachment.html>


More information about the Python-list mailing list