Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

0 views

Skip to first unread message

Nov 14, 2007, 5:24:18 PM11/14/07

to

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.

Nov 14, 2007, 5:53:08 PM11/14/07

to pytho...@python.org

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.

> 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

that is made terrible by our own mad attempt to interpret it as though it had

an underlying truth."

-- Umberto Eco

Nov 14, 2007, 5:59:42 PM11/14/07

to

Nov 14, 2007, 5:52:47 PM11/14/07

to Tom Jones, pytho...@python.org

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:> 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.

>

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

0 new messages

Search

Clear search

Close search

Google apps

Main menu