Bağımlılıklara göre nasıl sıralanır?

Question

Aynı temel türdeki diğer sınıfları işaret eden bir "bağımlılıklar" listesi olan bir sınıfa sahibim.

class Foo(Base): 
    dependencies = [] 

class Bar(Base): 
    dependencies = [Foo] 

class Baz(Base): 
    dependencies = [Bar] 

Bu sınıfların bağımlılıklarına göre oluşturduğu örnekleri sıralamak istiyorum. Örneğimde, önce Foo'nun, daha sonra Bar'ın, sonra Baz'ın gelmesini beklerdim.

bu sıralamak için en iyi yolu nedir?

Answer 1

bir topolojik sıralama denir.

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

Sadece geçen haftaya benzer bir sorum vardı - isterse Stack Overflow hakkında bilgi sahibi olmayı isterdim! (Benim bağımlılıkları özyinelemeli veya dairesel olamazdı çünkü Yönetmen Mercury Grafik) Ben DAG olduğunu fark edene kadar ben biraz etrafında avlanan. Sonra onları sıralamak için algoritmalar için birkaç referans buldum. Yaprak düğümlerine ulaşmak ve bunları önce sıralanmış listeye eklemek için derinlik-ilk geçişi kullandım.

Directed Acyclic Graphs