Come convertire Directed Acyclic Graph (DAG) in albero

Question

Ho cercato esempi C # per trasformare un DAG in un albero.

Qualcuno ha esempi o puntatori nella giusta direzione?

Aggiornamento chiarimenti

Ho un grafico che contiene un elenco di moduli che la mia applicazione deve caricare. Ogni modulo ha un elenco di moduli da cui dipende. Ad esempio, ecco i miei moduli, A, B C, D ed E

• A non ha dipendenze
• B dipende da A, C ed E
• C dipende da A
• D dipende da A
• E dipende da C e A

Voglio risolvere le dipendenze e generare un albero simile a questo ...

- A

- + - B

----- + - C

--------- + - D

- + - E

Ordinamento topologico

Grazie per l'informazione, se eseguo un ordinamento topologico e inverto l'output, avrò il seguente ordine

• A
• B
• C
• D
• E

Voglio mantenere la struttura gerarchica in modo che i miei moduli siano caricati nel contesto corretto, ad esempio ... il modulo E dovrebbe trovarsi nello stesso contenitore di B

Grazie

Rohan

Answer 1

C'è la risposta teorica del grafico e la risposta del programmatore a questo. Presumo che tu possa gestire tu stesso la parte dei programmatori. Per la risposta teorica del grafico:

• Un DAG è un insieme di moduli in cui non accade mai che A abbia bisogno di B, e allo stesso tempo, B (o uno dei moduli B di cui ha bisogno) abbia bisogno di A, in termini di moduli: nessuna dipendenza circolare. Ho visto accadere dipendenze circolari (cerca esempi nei forum di Gentoo), quindi non puoi nemmeno essere sicuro al 100% di avere un DAG, ma supponiamo che tu lo abbia. Non è molto difficile fare un controllo sulle dipendenze circolari, quindi ti consiglio di farlo da qualche parte nel tuo caricatore di moduli.
• In un albero, qualcosa che non può mai accadere è che A dipende da B e C e che sia B che C dipendono da D (un diamante), ma ciò può accadere in un DAG.
• Inoltre, un albero ha esattamente un nodo radice, ma un DAG può avere più " root " nodi (ovvero moduli da cui nulla dipende). Ad esempio un programma come GIMP, il programma GIMP sarà il nodo principale dell'insieme di moduli, ma per GENTOO, quasi ogni programma con una GUI è un "root" nodo, mentre le librerie ecc. ne dipendono. (I.E. sia Konqueror che Kmail dipendono da Qtlib, ma nulla dipende da Konqueror e nulla dipende da Kmail)

La risposta teorica di Graph alla tua domanda, come altri hanno sottolineato, è che un DAG non può essere convertito in un albero, mentre ogni albero è un DAG.

Tuttavia, (risposta dei programmatori di alto livello) se si desidera l'albero per le rappresentazioni grafiche, si è interessati solo alle dipendenze di un modulo specifico, non a ciò che dipende da quel modulo. Lasciami fare un esempio:

A depends on B and C
B depends on D and E
C depends on D and F

Non posso mostrarlo come un albero di arte ASCII, per la semplice ragione che non può essere convertito in un albero. Tuttavia, se vuoi mostrare da cosa dipende A, puoi mostrarlo:

A
+--B
|  +--D
|  +--E
+--C
   +--D
   +--F

Come vedi, ottieni doppie voci nella tua struttura - in questo caso " solo " D ma se esegui un " espandi tutto " sull'albero Gentoo, ti garantisco che il tuo albero avrà almeno 1000 volte la quantità di nodi in quanto ci sono moduli. (ci sono almeno 100 pacchetti che dipendono da Qt, quindi tutto ciò che Qt dipende sarà presente almeno 100 volte nella struttura).

Se hai un " large " o "complesso" albero, potrebbe essere meglio espandere l'albero in modo dinamico, non in anticipo, altrimenti potresti avere un processo che richiede molta memoria.

Lo svantaggio dell'albero sopra è che se fai clic su apri B, quindi D, vedi che A e B dipendono da D, ma non che anche C dipende da D. Tuttavia, a seconda della situazione, questo potrebbe non essere importante affatto - se mantieni un elenco di moduli caricati, quando carichi C vedi che hai già caricato D, e non importa che non sia stato caricato per C, ma per B. È caricato, tutto qui questioni. Se mantieni dinamicamente ciò che dipende direttamente da un determinato modulo, puoi gestire anche il problema opposto (scarico).

Tuttavia, ciò che non puoi fare con un albero è ciò che è nella tua frase finale: preservare l'ordine topologico, cioè se B viene caricato nello stesso contenitore di C, non riuscirai mai a caricare C nello stesso contenitore di bene. Oppure potresti dover sopportare di mettere tutto in un contenitore (non che io comprenda appieno cosa intendi con "caricamento nello stesso contenitore")

Buona fortuna!

Answer 2

Un DAG e un albero non sono matematicamente la stessa cosa. Pertanto, qualsiasi conversione introduce ambiguità. Un albero per definizione non ha cicli, punto.

Answer 3

Quello che stai cercando, al fine di trovare l'ordine in cui caricare i tuoi moduli, è il Ordinamento topologico del tuo DAG. Se i bordi vanno da un modulo ai moduli da cui dipende (che ritengo sia il più probabile), dovrai caricare i moduli nell'ordine inverso rispetto all'ordinamento topologico perché un modulo apparirà -prima di tutti i moduli da cui dipende.

Se rappresenti il ??DAG in modo tale che i bordi passino dai moduli dipendenti ai moduli che dipendono da essi (puoi ottenerlo invertendo tutti i bordi nel grafico sopra), puoi semplicemente caricare i moduli nell'ordine di tipo topologico.

Answer 4

Dipende molto da come rappresenti il ??tuo DAG. Ad esempio, potrebbe essere una matrice di adiacenza (A [i, j] = 1 se esiste un bordo dal nodo i al nodo j, altrimenti 0) o come sistema di puntatori o come matrice di nodi e matrice di bordi ....

Inoltre, non è chiaro quale trasformazione stai cercando di applicare. Un DAG collegato è un albero, quindi temo che tu debba chiarire un po 'la tua domanda.

Answer 5

Puoi farlo solo se tutti i sottotitoli hanno un singolo nodo radice.