dependency order

[belred]

i'm having trouble trying to figure this out... it's part of a build
system i'm writing in python. maybe someone has a good simple way to
solve this. i'm trying to create a dependency order out of multiple
lists.

list1: B C
list2: A B
list3: A C

i want the end result to be the list: A B C
i'm very frustrated that i can't come up with anything that always
works.


thanks... any clues to solve this would be greatly appreciated.

bryan

 

[Diez B. Roggisch]

i'm having trouble trying to figure this out... it's part of a build
system i'm writing in python. maybe someone has a good simple way to
solve this. i'm trying to create a dependency order out of multiple
lists.

list1: B C
list2: A B
list3: A C

i want the end result to be the list: A B C
i'm very frustrated that i can't come up with anything that always
works.


thanks... any clues to solve this would be greatly appreciated.

Maybe the frustration is based on the IMHO wrong data-structure you use.
What does [B, C] mean?

A common approach for this is to create a dict instead, that maps an
object to the list of things it depends on (or that depend on it, it's
essentially the same)

The resulting data-structure is called a directed graph, and there are
algorithms like "partial orderings" you can google for that will help you.

An example graph would be:


dict(
"A" : ["B", "C"],
"B" : ["C"]
"C" : []
)

Then the result of a partial ordering would be

["C", "B", "A"]

which should be what you are after.

Diez

 

[belred]

i'm having trouble trying to figure this out... it's part of a build
system i'm writing in python. maybe someone has a good simple way to
solve this. i'm trying to create a dependency order out of multiple
lists.

list1: B C
list2: A B
list3: A C

i want the end result to be the list: A B C
i'm very frustrated that i can't come up with anything that always
works.

thanks... any clues to solve this would be greatly appreciated.

Maybe the frustration is based on the IMHO wrong data-structure you use.
What does [B, C] mean?

A common approach for this is to create a dict instead, that maps an
object to the list of things it depends on (or that depend on it, it's
essentially the same)

The resulting data-structure is called a directed graph, and there are
algorithms like "partial orderings" you can google for that will help you.

An example graph would be:

dict(
"A" : ["B", "C"],
"B" : ["C"]
"C" : []
)

Then the result of a partial ordering would be

["C", "B", "A"]

which should be what you are after.

Diez

i found this program in pypi, it does exactly what i was after

http://pypi.python.org/pypi/topsort/0.9

from topsort import topsort
topsort([('B', 'C'),('A', 'B'),('A', 'C')])

['A', 'B', 'C']

very cool!!! i will be able to adapt this to my program without any
problems.

 

[Gabriel Genellina]

i'm having trouble trying to figure this out... it's part of a build
system i'm writing in python. maybe someone has a good simple way to
solve this. i'm trying to create a dependency order out of multiple
lists.

list1: B C
list2: A B
list3: A C

i want the end result to be the list: A B C
i'm very frustrated that i can't come up with anything that always
works.

"Topological sort". There were two threads here last month.

http://groups.google.com/group/comp.lang.python/search?q=topological+sort&start=0&scoring=d