C'è la risposta teorica del grafico e la risposta del programmatore a questo. Presumo che tu possa gestire da solo la parte dei programmatori. Per il grafico risposta theorethical:
- Un DAG è un insieme di moduli dove non accade mai che A ha bisogno di B, e allo stesso tempo, B (o una delle necessità moduli B) deve A, in MODULI parla: nessuna dipendenza circolare. Ho visto le dipendenze circolari accadere (cercare i forum di Gentoo per gli esempi), quindi non si può nemmeno essere sicuri al 100% di avere un DAG, ma supponiamo che tu 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 questo può accadere in un DAG.
- Inoltre, un albero ha esattamente un nodo radice, ma un DAG può avere più nodi "root" (cioè moduli che nulla dipende da). Ad esempio, un programma come GIMP, il programma GIMP sarà il nodo principale del set di moduli, ma per GENTOO quasi tutti i programmi con una GUI sono un nodo "root", mentre le librerie ecc. Ne dipendono. (IE sia Konqueror e Kmail dipendono Qtlib, ma nulla dipende da Konqueror, e niente dipende Kmail)
Il grafico theorethical risposta alla tua domanda, come altri hanno sottolineato, è che un DAG non può essere convertito ad un albero, mentre ogni albero è un DAG.
Tuttavia, (i programmatori di alto livello rispondono) se si desidera la struttura per rappresentazioni grafiche, si è interessati solo alle dipendenze di un modulo specifico, non a ciò che dipende da quel modulo. Vi faccio un esempio:
A depends on B and C
B depends on D and E
C depends on D and F
non posso mostrare questo come un albero di ASCII-art, per la semplice ragione che questo non può essere convertito in un albero. Tuttavia, se si vuole mostrare ciò che un dipende, è possibile mostrare questo:
A
+--B
| +--D
| +--E
+--C
+--D
+--F
Come si vede, si ottiene il doppio voci nel vostro albero - in questo caso "solo" D, ma se si fa un " espandi tutto "sull'albero di Gentoo, ti garantisco che il tuo albero avrà almeno 1000 volte la quantità di nodi quanti sono i moduli. (ci sono almeno 100 pacchetti che dipendono da Qt, quindi tutto ciò che dipende da Qt sarà presente almeno 100 volte nell'albero).
Se si dispone di un albero "grande" o "complesso", potrebbe essere preferibile espandere l'albero in modo dinamico, non in anticipo, altrimenti si potrebbe avere un processo che richiede molta memoria.
Lo svantaggio dell'albero sopra è che se si fa clic su B, quindi su D, si vede 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 - se si mantiene un elenco di moduli caricati, nel caricamento C si vede che hai già caricato D, e non importa che non è stato caricato per C, ma per B. È caricato, questo è tutto quello che conta. Se si mantiene in modo dinamico ciò che dipende direttamente da un determinato modulo, è possibile gestire anche il problema opposto (scaricamento).
Tuttavia, ciò che non si può fare con un albero è ciò che c'è nella frase finale: preservare l'ordine topologico, cioè se B viene caricato nello stesso contenitore di C, non si arriva mai a caricare C nello stesso contenitore anche. Oppure potresti essere costretto a mettere tutto in un unico contenitore (non che io capisca perfettamente cosa intendi con "caricamento nello stesso contenitore")
Buona fortuna!
come desiderate trattare i diamanti ... A -> B, A -> C, B & C -> D – ShuggyCoUk
Questa è una buona domanda, vedo un problema ma non so come risolverlo, cosa sarebbe tu fai? La mia esperienza con la teoria dei grafi è molto limitata. –
1) scegli il primo, 2) scegli l'ultimo 3) duplica il nodo. Qualunque sia la migliore è interamente dipendente dall'applicazione, 3 è più semplice seguito da 1 seguito da 2 ... è difficile dire quale sia l'albero in base alla domanda. le dipendenze dei diamanti sono una cagna in generale – ShuggyCoUk