dependency algorithm

[Diez B. Roggisch]

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