dependency algorithm

Mike C. Fletcher mcfletch at vrplumber.com
Wed Nov 14 17:52:47 EST 2007


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




More information about the Python-list mailing list