Algoritmo di ordinamento per Fornisce / Depende su oggetti

1

Ho un set di tipo rewriters , ognuno modifica un determinato tipo di C # in un modo diverso. Gli esempi sono:

  1. Aggiungi l'attributo XYZ a ciascuna proprietà della classe
  2. Aggiungi una proprietà ID
  3. Aggiungi due proprietà e un metodo corrispondente

Come puoi vedere ci sono delle dipendenze implicite: 1 dovrebbe sicuramente essere eseguito dopo 2 e 3, altrimenti non tutte le proprietà avranno l'attributo XYZ alla fine.

Abbiamo reso esplicite queste dipendenze implicite utilizzando gli attributi sui tipi rewriters:

[Performs(typeof(IAttributeOnPropertiesCreation))]
[DependsOn(typeof(IPropertyCreation))]
public class SomeRewriter
{
  // this one resembles example 1
}

[Performs(typeof(IPropertyCreation))]
// no DependsOn
public class SomeOtherRewriter
{
  // resembles example 2
}

Ho bisogno di un algoritmo per ordinare una serie di tali riscrittori di tipo per dipendenza (se possibile, cioè se non ci sono dipendenze circolari).

Esiste un algoritmo di riferimento noto per questa attività? Forse anche un nome noto che posso usare per cercare vari algoritmi?

Nota a margine: conosco il set completo di possibili tipi Performs / DependsOn. Tuttavia, potrebbero esserci dichiarazioni DependsOn () per le quali nessuna, una singola o anche più riscrittori ha un'istruzione Performs () corrispondente. A loro volta ci sono anche dichiarazioni Performs () dalle quali nessuno dipende.

    
posta D.R. 18.02.2016 - 14:15
fonte

1 risposta

1

la cosa migliore che potresti usare per questo è probabilmente un algoritmo toposort (topolocial sort). Fondamentalmente puoi scrivere codice simile come visto in così post

Nota che questo algoritmo rileverà facilmente anche le dipendenze cicliche.

Ulteriori informazioni: Se sai qualcosa sui grafici diretti, è fondamentalmente una ricerca in profondità su un grafico così diretto. Tale algoritmo può anche essere utilizzato per rilevare parti indipendenti di un grafico, che può essere utile per la parallelizzazione automatica di task / programmi e simili.

Raccomando di leggere di più sui grafici, in quanto possono essere davvero utili per la programmazione e l'ottimizzazione delle strutture dati. Vedi: Wikipedia

    
risposta data 18.02.2016 - 15:41
fonte

Leggi altre domande sui tag