¿Cómo ordenar según las dependencias?

Question

Tengo una clase que tiene una lista de "dependencias" que apunta a otras clases del mismo tipo de base.

class Foo(Base): 
    dependencies = [] 

class Bar(Base): 
    dependencies = [Foo] 

class Baz(Base): 
    dependencies = [Bar] 

Me gustaría ordenar las instancias que estas clases generan en función de sus dependencias. En mi ejemplo, esperaría que Foo fuera primero, luego Bar, luego Baz.

¿Cuál es la mejor manera de ordenar esto?

Answer 1

Se llama tipo topológico.

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

Tuve una pregunta similar la semana pasada. ¡Ojalá supiera sobre Stack Overflow! Cacé un poco hasta que me di cuenta de que tenía un DAG (Directed Acyclic Graph, ya que mis dependencias no podían ser recursivas ni circulares). Luego encontré algunas referencias de algoritmos para ordenarlos. Usé un recorrido transversal en profundidad para llegar a los nodos de hoja y agregarlos primero a la lista ordenada.

Aquí hay una página que he encontrado útil:

Directed Acyclic Graphs