Un algoritmo pulito per l'ordinamento di oggetti in base a dipendenze definite?

Question

Dato un elenco di classi che ereditano da questa base:

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

... e le seguenti regole:

• plugin possono fornire una lista di plugin che devono correre dopo.
• I plug-in possono fornire un elenco di plug-in che devono essere eseguiti prima.
• L'elenco di plug-in può contenere o meno tutti i plug-in che sono stati specificati nei vincoli di ordinamento.

Qualcuno può fornire un buon algoritmo pulito per ordinare un elenco di plug-in? Sarà necessario rilevare le dipendenze circolari così ....

def order_plugins(plugins): 
     pass 

mi è venuta in mente un paio di versioni, ma nulla particuarlly pulito: sono sicuro che alcuni di voi Art of Computer Programming tipi sarà assaporare la sfida :)

[Nota: domanda dato in Python, ma è chiaro che non è solo una questione di Python: pseudocodice in qualsiasi lingua farebbe]

Answer 1

questo è chiamato topological sorting.

L'applicazione canonica di ordinamento topologico (topologico ordine) è in pianificazione di una sequenza di posti di lavoro o attività; Gli ordinamenti topologici degli algoritmi sono stati studiati per la prima volta negli anni '60 nel contesto della tecnica PERT per la pianificazione nella gestione del progetto (Jarnagin 1960). I lavori sono rappresentati da vertici, e non vi è un vantaggio da X a Y se lavoro x deve essere completata prima di lavoro Y può essere avviato (ad esempio, quando si lava i vestiti, la lavatrice deve finitura prima di mettere i vestiti a secco). Quindi, un ordinamento topologico fornisce a un ordine in cui eseguire i lavori.

Answer 2

Questo è chiamato topological sorting.

Fare questo comporta diversi passaggi:

prima costruire un grafico di tutti i plugin scelti come i vertici e le loro dipendenze come bordi. Esegui prima/dopo le deps riducono allo stesso tipo di bordi.

Avanti costruisci uno scafo di transito: guarda tutti i plugin e aggiungi tutte le dipendenze mancanti. Ripeti fino a quando l'insieme non cambia più.

Ultimo passaggio: scegliere una vertice senza bordi in entrata e fare una ricerca DFS (o BFS). Questo algoritmo può essere arricchito con il rilevamento del ciclo.

Answer 3

Se si definisce il __lt__ ei metodi associati sul plug-in in base al fatto che debbano essere eseguiti prima o dopo, è possibile trovare un ordinamento sano con sorted(). I cicli sarebbero comunque un problema.

Answer 4

Se si desidera fornire una buona diagnostica per il caso che ci siano cicli, dare un'occhiata a http://en.wikipedia.org/wiki/Strongly_connected_component. Penso che se si utilizza una versione di un componente Strongly connected come quella delineata in http://www.cs.sunysb.edu/~skiena/373/notes/lecture16/lecture16.html, è possibile ottenere che stampi i componenti fortemente connessi nell'ordine di ordinamento topologico.

Answer 5

Here è un codice Python che esegue l'ordinamento topologico.