Hi - <br><br>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.
<br><br>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 :)
<br><br>edges = [ (0,1), (1,2), (2,3) ]<br>n = 4<br><br>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<br><br>def linearise( adj ):<br>
    order = []<br>    for i in xrange( len( adj ) ):<br>        visit( i, adj, order )<br>    return order<br>    <br>def visit( i, adj, order ):<br>    if adj[i][1] == True:<br>        return<br><br>    adj[i][1] = True<br>
<br>    for child in adj[i][0]:<br>        visit( child, adj, order )<br><br>    order.append( i )<br><br>HTH,<br><br>Henry<br>    <br>    <br><br><div><span class="gmail_quote">On 14/11/2007, <b class="gmail_sendername">
Tom Jones</b> <<a href="mailto:thomasjones@hotmail.com">thomasjones@hotmail.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hi,<br><br>Consider tuples of the above numbers in the form:<br>   (a,b)<br><br>Suppose this relation means:<br>   a depends on b<br><br>Given a list of tuples, I would like an algorithm to return the proper<br>ordering of the elements...and if the ordering has a loop (which in this
<br>case, prevents a proper ordering), then it should return None.<br><br>For example,<br><br><br>   [(1,2),(2,3),(3,4)]<br>should give:<br>   [4,3,2,1]<br><br><br>   [(3,2),(1,3),(2,4)]<br>should give:<br>   [4,2,3,1]<br>
<br><br>   [(1,4),(4,3),(2,3)]<br>should give:<br>   [3,2,4,1]  or [3,4,2,1]  (which one doesn't matter)<br><br><br>   [(1,2), (2,3), (3,2)]<br>should give<br>   None, since it cannot be resolved<br><br><br>I'm sure this is a standard problem (mro, resolving inheritance?), but
<br>this is a simplified case since each element can directly depend on only<br>one other element (thus, multiple inheritance is not allowed)...but many<br>elements can depend on the same element (no limit on the number of
<br>classes which subclass another class).  A quick hack is simple enough to<br>code, but I am wondering if there are 'standard' ways of performing this<br>task in this limited scope.<br><br>Thanks.<br>--<br><a href="http://mail.python.org/mailman/listinfo/python-list">
http://mail.python.org/mailman/listinfo/python-list</a><br></blockquote></div><br>