urutkan/grafik urutan traversal dari daftar objek yang bergantung satu sama lain [duplikat]

Saya memiliki kelas seperti Foo di bawah ini yang memiliki atribut "depends_on" yang merupakan array dari Foo instance lainnya. Saya ingin dapat mengambil daftar Foo dan mengurutkannya sedemikian rupa sehingga foo yang bergantung pada foo lain lebih besar dari itu. Misalnya, jika foo b bergantung pada foo a, arraynya harus berada di urutan [a,b]. Saya pikir akan lebih baik untuk memberikan setiap foo bidang order dan mengurutkan bidang itu daripada menggunakan __lt__.

class Foo(object):
    def __init__(self, name, depends_on=[]):
        self.order = 0
        self.name = name
        self.depends_on = depends_on

a = Foo('a')
b = Foo('b', [a])
c = Foo('c', [b])
d = Foo('d')
e = Foo('e')
f = Foo('f', [e])
g = Foo('g', [f, b])

foos = [a,b,c,d,e,f,g]

Saya telah membuat fungsi rekursif yang mirip dengan ini dan tampaknya berfungsi, tapi menurut saya ada cara yang lebih baik.

Pada lintasan pertama, saya membandingkan setiap objek dalam array satu sama lain. Jika objek x bergantung pada objek y, saya menambah bidang order objek x sebanyak satu.

Pada lintasan kedua, saya hanya membandingkan foos dengan order lebih besar atau sama dengan 1; yaitu, foo yang bergantung pada setidaknya satu foo lainnya. Sekali lagi, saya menambah bidang order dari subset foos ini jika keduanya bergantung satu sama lain.

Saya melanjutkan pola ini sampai tidak ada lagi perbandingan yang bisa dilakukan.

def recursive_order(order=0):
    compared = 0
    for fooa in [foo for foo in foos if foo.order >= order]:
        for foob in [foo for foo in foos if foo.order >= order]:
            compared += 1
            if fooa in foob.depends_on:
                foob.order += 1
    if compared == 0:
        return
    recursive_order(order + 1)

recursive_order()
foos.sort(key=lambda foo: foo.order)
print [(foo.name, foo.order) for foo in foos]

[('a', 0), ('d', 0), ('e', 0), ('b', 1), ('f', 1), ('c', 2), ('g', 2)]

Saya ingin daftar foo yang memperhitungkan "urutan ketergantungan". Misalnya, foo a dan foo b tidak memiliki ketergantungan dan karenanya setara. Foo b bergantung pada Foo a, jadi foo a ‹ foo b ([a,b]. Foo c bergantung pada Foo b, jadi [a,b,c].

Edit

Terima kasih kepada Martijn Pieters untuk link ke pengurutan topologi. Inilah implementasi saya:

def topological_sort(foos):
    provided = set()
    while foos:
        remaining_foos = []
        emitted = False

        for foo in foos:
            if set(foo.depends_on).issubset(provided):
                yield foo
                provided.add(foo)
                emitted = True
            else:
                remaining_foos.append(foo)

        if not emitted:
            raise raise ValueError("cyclic dependency detected")

        foos = remaining_foos

print [foo.name for foo in topological_sort(foos)]

['e', 'd', 'a', 'f', 'b', 'g', 'c']