Risolvi le dipendenze usando i vincoli before-after

2

Quello che vorrei fare è il seguente.
(Non sono sicuro se questa domanda dovrebbe andare a StackOverflow, o qui)

Considera una struttura dati come questa:

interface IAction {
    IAction[] afterActions()
    IAction[] beforeActions()
    void execute()
}

Quello che mi piacerebbe fare è execute() a IAction collection, nel modo in cui

  1. Tutte le beforeActions() vengono eseguite prima che il fornitore della beforeActions() invochi il risultato.
  2. Tutti afterActions() vengono eseguiti dopo che il fornitore del afterActions() chiama risultato.
  3. Essere in grado di rilevare "dipendenze cicliche", quindi se si deve eseguire prima e dopo un'altra, o dopo di sé, o dopo un'altra azione, quella su qualsiasi percorso deve essere eseguita prima, ecc.

In altri mondi vorrei "ordinare" queste azioni in un ordine eseguibile.

Mi piacerebbe avere solo una spiegazione su come dovrei (potrei) fare questo, non mi aspetto che qualcuno possa implementare qualcosa per me (nota che non ho intenzionalmente specificato una lingua).

Se conosci qualche algoritmo generico per questo scopo, che ritieni sia adatto al problema, non esitare a condividere con una spiegazione minima, su come lo traducesti in questo problema

Modifica

Dopo aver riflettuto molto sul problema, ho capito che per quanto riguarda la dipendenza, afterActions() è assolutamente inutile (un'azione non dovrebbe sapere cosa viene eseguito dopo, dovrebbe solo descrivere ciò che deve essere completato prima , per eseguire correttamente). Sapendo questo ho finito per fare qualcosa di simile a ciò che @Rafael Eyng ha suggerito:

Ho creato un Iterator , che ha avvolto la raccolta originale e ha avuto un next() , che ha sempre restituito l'azione successiva (risolta). L'iteratore non era stateless, aveva un riferimento alla collezione con tutte le azioni e aveva una (crescente) Set di azioni, che sono state risolte. Per ottenere ciò, ogni volta che è stato chiamato next() ho fatto quanto segue:

  1. Esegui l'iter su tutte le azioni
  2. Se uno non ha dipendenze o tutte sono incluse nell'elenco già risolto, può essere restituito come dopo.
  3. Se ha delle dipendenze, fallo in modo ricorsivo per tutti i prerequisiti.
  4. Stavo anche raccogliendo le azioni già visitate, dalla radice della chiamata ricorsiva, in modo che i cicli potessero essere rilevati
posta Balázs Édes 27.01.2015 - 15:40
fonte

2 risposte

1

Prima di tutto, dovresti avere una raccolta (chiamiamola) ready di IAction le cui dipendenze erano già soddisfatte. Questa raccolta inizia vuota, ovviamente. Quindi dovresti scorrere le istanze di IAction e verificare se tutte le sue dipendenze sono state soddisfatte. Lo fai iterando su tutte le dipendenze e controllando se tutte sono presenti nella raccolta ready . Se tutte le dipendenze di alcune istanze di IAction sono presenti nella raccolta ready , puoi inserire questa istanza di IAction anche nella raccolta ready . A questo punto, non controlli più le dipendenze di IAction rimuovendole dalle raccolte irrisolte di IAction o segnalandole come pronte per l'esecuzione.

Naturalmente ciò presuppone che ci saranno alcune IAction che non hanno alcuna dipendenza (che saranno le prime ad essere inserite nella collezione ready ), o più in generale, non ci sono dipendenze cicliche. Ma penso che potrebbe darti una buona prima implementazione su cui lavorare.

    
risposta data 29.01.2015 - 02:21
fonte
0

Per la domanda 3, è necessario eseguire iterazioni ricorsive sul grafico delle istanze di IAction interamente. L'iterazione ricorsiva è un'operazione di base. Se non sai come farlo, leggi sull'incrocio dell'albero recursivo. È possibile rilevare le dipendenze cicliche in almeno due modi:

  • Utilizzare una classe anziché un'interfaccia e utilizzare un campo booleano nella classe per indicare che l'istanza è già stata visitata. Se durante l'iterazione, visiti due volte la stessa istanza, hai rilevato un ciclo.
  • Utilizza una raccolta di istanze IAction e aggiungi ciascuna istanza alla raccolta quando la visiti. Puoi rilevare i cicli notando che un'istanza è già presente nella raccolta, prima di aggiungerla.
risposta data 28.01.2015 - 19:29
fonte

Leggi altre domande sui tag