Cálculo de dependencias de plugins

Question

Tengo la necesidad de crear un sistema de complementos que tenga soporte de dependencia y no estoy seguro de la mejor forma de dar cuenta de las dependencias. Todos los complementos se subclasificarán desde una clase base, cada uno con su propio método execute(). En cada clase de complemento, había planeado crear un atributo dependencies como una lista de todos los demás complementos de los que depende.

Al cargar los complementos, los importaría a todos y los incluiría en una lista y los ordenaría según las dependencias. Una vez que todos estén en el orden correcto (de modo que cualquier cosa con una dependencia esté en la lista después de sus dependencias), recorro la lista ejecutando cada método execute().

Donde estoy cada vez más borroso es la lógica detrás de la clasificación. Puedo comenzar a ponerlos en orden alfabético hasta que encuentre uno que tenga una dependencia. Si sus dependencias aún no están en la lista, póngalo en una lista de tmp. al final de la primera ronda de importaciones, comience al final de la lista temporal (una lista con nada más que complementos que tienen dependencias) y revise la 'lista de ejecución' nuevamente. si encuentro sus dependencias en la 'lista de ejecución', asegúrese de que tenga un número de índice mayor que su dependencia más alta. Si sus dependencias no están en la lista, manténgala presionada y pase al siguiente complemento en la lista temporal. Una vez que llegue al final de la lista de tmp, comience de nuevo en la parte superior y vuelva a intentarlo. Una vez que se hayan ordenado todos los complementos o que la lista tmp no cambie de tamaño después de recorrerlo, comience a ejecutar complementos.

Lo que quedaría en la lista temporal son los complementos que no tienen dependencias encontradas o tienen una dependencia circular. (2 complementos en la lista tmp que dependen uno del otro)

Si todavía está leyendo Y pudo seguir mi lógica; ¿Es este un plan sensato? ¿Hay alguna forma más simple? Si quisiera implementar números de secuencia para el orden de ejecución, ¿existe una forma "fácil" de tener secuencia y dependencias? (con dependencias que superan la secuencia si hubiera un conflicto) ¿O debería un complemento usar una secuencia O dependencias? (Ejecutar los plugins con los primeros números de secuencia, que los que tienen dependencias?)

TL; DR

¿Cómo escribir la lógica para calcular las dependencias en un sistema de plugins?

---

Editar:

Alright- creo que implemente el tipo topológico de la página de Wikipedia; siguiendo su ejemplo lógico para el DFS. Parece que funciona, pero nunca he hecho algo como esto antes.

http://en.wikipedia.org/wiki/Topological_sorting#Examples

data = { 
    '10' : ['11', '3'], 
    '3' : [], 
    '5' : [], 
    '7' : [], 
    '11' : ['7', '5'], 
    '9' : ['8', '11'], 
    '2' : ['11'], 
    '8' : ['7', '3'] 
} 

L = [] 
visited = [] 

def nodeps(data): 
    S = [] 
    for each in data.keys(): 
     if not len(data[each]): 
      S.append(each) 
    return S 

def dependson(node): 
    r = [] 
    for each in data.keys(): 
     for n in data[each]: 
      if n == node: 
       r.append(each) 
    return r 

def visit(node): 
    if not node in visited: 
     visited.append(node) 
     for m in dependson(node): 
      visit(m) 
     L.append(node) 

for node in nodeps(data): 
    visit(node) 

print L[::-1] 

Answer 1

El algoritmo que ha descrito parece que funcionaría pero le resultaría difícil detectar las dependencias circulares.

Lo que estás buscando es un Topological sort de tus dependencias. Si crea un gráfico de sus dependencias donde un borde de A a B significa que A depende de B, puede hacer un Depth-first search para determinar el orden correcto. Querrá hacer un variation of a regular DFS que pueda detectar ciclos para que pueda imprimir un error en ese caso.

Si utiliza una lista ordenada en cada vértice para almacenar conexiones en el gráfico, puede agregar dependencias usando sus números de secuencia. Una ventaja de usar un DFS es que la lista ordenada resultante debe respetar su orden de secuencia cuando no está en conflicto con el orden de dependencia. (Creo que tengo que probar esto.)

Answer 2

Un topological sort pondrá todo en el orden correcto.