¿Algún algoritmo de limpieza para clasificar objetos según las dependencias definidas?

Question

dado una lista de clases que heredan de esta base:

class Plugin(object): 
    run_after_plugins =() 
    run_before_plugins =() 

... y las siguientes reglas:

• Los complementos pueden proporcionar una lista de plugins que deben ejecutarse después.
• Los complementos pueden proporcionar una lista de complementos que deben ejecutarse antes.
• La lista de complementos puede contener o no todos los complementos que se han especificado para ordenar restricciones.

¿Alguien puede proporcionar un buen algoritmo de limpieza para ordenar una lista de complementos? Será necesario para detectar dependencias circulares, así ....

def order_plugins(plugins): 
     pass 

que he llegado con algunas versiones, pero nada particuarlly ordenada: Estoy seguro de que algunos de ustedes Art of Computer Programming tipos disfrutarán el reto :)

[nota: pregunta dada en Python, pero es evidente que no es sólo una cuestión de Python: pseudocódigo en cualquier idioma haría]

Answer 1

Esto se llama topological sorting.

La aplicación canónica de clasificación topológica (topológico orden) es en programar una secuencia de trabajos o tareas; clasificación topológica algoritmos se estudiaron por primera vez en el principios de 1960 en el contexto de la técnica PERT para la programación en el proyecto gestión (Jarnagin 1960). Los trabajos están representados por los vértices, y hay es una arista de x a y si el trabajo x debe ser completado antes del trabajo y puede ser iniciado (por ejemplo, cuando se lava ropa, la lavadora debe acabado antes de poner la ropa a seca). Luego, un tipo topológico da un orden en el que realizar los trabajos.

Answer 2

Esto se llama topological sorting.

Hacer esto implica varios pasos:

En primer lugar construir un gráfico de todos los plugins seleccionadas como vértices y sus dependencias como bordes. Ejecutar antes/después de los deps se reducen al mismo tipo de bordes.

Próxima compilación de un casco transitiv: Mire todos los complementos y agregue todas las dependencias faltantes. Repita esto hasta que el conjunto no cambie más.

Último paso: elija un vértice sin bordes entrantes y realice una búsqueda DFS (o BFS). Estos algoritmos se pueden enriquecer con la detección de ciclos.

Answer 3

Si define el __lt__ y los métodos asociados en el Plugin en función de si deben ejecutarse antes o después, entonces podría ser posible encontrar un orden correcto con sorted(). Sin embargo, los ciclos aún serían un problema.

Answer 4

Si quiere dar buenos diagnósticos para el caso de que haya ciclos, eche un vistazo a http://en.wikipedia.org/wiki/Strongly_connected_component. Creo que si utiliza una versión de un componente Fuertemente conectado como el descrito en http://www.cs.sunysb.edu/~skiena/373/notes/lecture16/lecture16.html, puede hacer que imprima los componentes fuertemente conectados en orden topológico.

Answer 5

Here es un código de Python que realiza la clasificación topológica.