Jak sortować według zależności?

Question

Mam klasę, która ma listę "zależności" wskazujące na inne klasy tego samego typu podstawowego.

class Foo(Base): 
    dependencies = [] 

class Bar(Base): 
    dependencies = [Foo] 

class Baz(Base): 
    dependencies = [Bar] 

Chciałbym posortować wystąpienia, które te klasy generują na podstawie ich zależności. W moim przykładzie spodziewałbym się, że najpierw pojawią się instancje Foo, potem Bar, a potem Baz.

Jaki jest najlepszy sposób na sortowanie?

Answer 1

To się nazywa topologiczne.

def sort_deps(objs): 
    queue = [objs with no dependencies] 
    while queue: 
     obj = queue.pop() 
     yield obj 
     for obj in objs: 
      if dependencies are now satisfied: 
       queue.append(obj) 
    if not all dependencies are satisfied: 
     error 
    return result 

Answer 2

W zeszłym tygodniu miałem podobne pytanie - chciałbym wiedzieć o Stack Overflow! Trochę polowałem, dopóki nie zdałem sobie sprawy, że mam wykresy, ponieważ moje zależności nie mogą być rekurencyjne lub okrągłe. Następnie znalazłem kilka odniesień dla algorytmów do ich sortowania. Użyłem pierwszego przejścia przez głębokość, aby dostać się do węzłów liści i najpierw dodać je do posortowanej listy.

Oto strona, że ​​znalazłem przydatne:

Directed Acyclic Graphs