dependency order

[belred at gmail.com]

On Feb 9, 11:10 am, "Diez B. Roggisch" <de... at nospam.web.de> wrote:
> bel... at gmail.com schrieb:
>
> > 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.