Velocity Reviews > dependency algorithm

# dependency algorithm

Tom Jones
Guest
Posts: n/a

 11-14-2007
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

Thanks.

Mike C. Fletcher
Guest
Posts: n/a

 11-14-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

Robert Kern
Guest
Posts: n/a

 11-14-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.

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
an underlying truth."
-- Umberto Eco

Diez B. Roggisch
Guest
Posts: n/a

 11-14-2007
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