Jak przekonwertować kierowany Wykres acykliczny (DAG) na drzewo

Jest odpowiedź teoretyczna grafu i odpowiedź programisty na to. Zakładam, że poradzisz sobie sam z programistami. Dla grafu odpowiedź teoretyczna:

DAG jest zbiorem modułów, w których nigdy nie zdarza się, że A potrzebuje B, a jednocześnie B (lub jeden z modułów B potrzebuje) potrzebuje a, w modules-speak: no circular dependency. Widziałem, że zdarzają się okrągłe zależności (poszukaj przykładów na forach Gentoo), więc nie możesz być nawet w 100% pewien, że masz DAG, ale niech Załóżmy, że tak. Nie jest to bardzo trudne do sprawdzenia na kołowych zależności, więc polecam zrobić to gdzieś w swoim module loader.
• w drzewie, coś, co nigdy nie może się zdarzyć, to to, że A zależy od B I C i że zarówno B, jak i C zależą od D (diamentu), ale to może się zdarzyć w DAG.
• ponadto drzewo ma dokładnie jeden węzeł korzeniowy, ale DAG może mieć wiele węzłów "korzeniowych" (tzn. modułów, od których nic nie zależy). GIMP, GIMP program będzie root 'em. na przykład program taki jak GIMP, będzie root' em. na przykład program GIMP będzie root ' em. węzeł zestawu modułów, ale dla GENTOO prawie każdy program z GUI jest węzłem" root", podczas gdy biblioteki itp są ich zależnościami. (Tj. zarówno Konqueror, jak i Kmail zależą od Qtlib, ale nic nie zależy od Konquerora i nic nie zależy od Kmaila)

Teoretyczna odpowiedź na twoje pytanie, jak zauważyli inni, jest taka, że DAG nie może być zamieniony na drzewo, podczas gdy każde drzewo jest DAG.

Jednakże (Programiści wysokiego poziomu odpowiadają) jeśli chcesz, aby drzewo dla reprezentacje graficzne, interesują Cię tylko zależności konkretnego modułu, a nie to, co zależy od tego modułu. Podam przykład:

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

Nie mogę pokazać tego jako drzewa ASCII-art, z tego prostego powodu, że nie można tego przekształcić w drzewo. Jeśli jednak chcesz pokazać, od czego zależy A, możesz pokazać to:

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

Jak widzisz, dostajesz podwójne wpisy w swoim drzewie - w tym przypadku "tylko" D, ale jeśli zrobisz "Rozwiń wszystko" na drzewie Gentoo, gwarantuję Ci że twoje drzewo będzie miało co najmniej 1000 razy więcej węzłów niż istnieją Moduły. (istnieje co najmniej 100 pakietów, które zależą od Qt, więc wszystko od czego zależy Qt będzie obecne co najmniej 100 razy w drzewie).

Jeśli masz" duże "lub" złożone " drzewo, może być najlepiej rozwinąć drzewo dynamicznie, nie z góry, w przeciwnym razie możesz mieć bardzo intensywny proces pamięci.

Wadą powyższego drzewa jest to, że jeśli klikniesz otwórz B, to D, zobaczysz, że A i B zależy od D, ale nie to, że również C zależy od D. Jednak, w zależności od twojej sytuacji, może to wcale nie być ważne - jeśli utrzymasz listę załadowanych modułów, po załadowaniu C zobaczysz, że już załadowałeś D, i nie ma znaczenia, że nie był załadowany dla C, ale dla B. jest załadowany, to wszystko, co się liczy. Jeśli dynamicznie utrzymujesz to, co bezpośrednio zależy od określonego modułu, możesz również poradzić sobie z przeciwnym problemem (rozładowaniem).

Jednak to, czego nie można zrobić z drzewem, to co jest w twoim ostatnim zdaniu: zachowaj porządek topologiczny, tzn. jeśli B zostanie załadowany do tego samego kontenera co C, nigdy nie załadujesz C do tego samego kontenera. Nie rozumiem, co masz na myśli mówiąc "ładowanie do tego samego pojemnika"("loading into the same container")