Как преобразовать направленный ациклический график (DAG) в дерево

Ответ 1

Там теоретический ответ графика и программист отвечают на это. Я предполагаю, что вы сами можете обработать часть программистов. Для теоретического ответа на график:

• DAG - это набор модулей, где никогда не бывает, что A нуждается в B, и в то же время B (или одному из модулей B потребностей) требуется A, в модулях говорят: нет круговой зависимости. Я видел круговые зависимости (поиск на форумах Gentoo для примеров), поэтому вы даже не можете быть на 100% уверены, что у вас есть DAG, но пусть у вас есть. Это не очень сложно сделать проверку на круговые зависимости, поэтому я бы рекомендовал вам сделать это где-то в вашем загрузчике модулей.
• В дереве чего-то, что никогда не может произойти, является то, что A зависит от B и C и что B и C зависят от D (бриллиант), но это может произойти в DAG.
• Кроме того, дерево имеет ровно один корень node, но DAG может иметь несколько "корневых" узлов (т.е. модулей, от которых ничего не зависит). Например, программа, подобная GIMP, программа GIMP будет корневым node набора модулей, но для GENTOO почти любая программа с графическим интерфейсом является "корневым" node, тогда как библиотеки и т.д. Являются зависимостями их. (И.Е. и Konqueror, и Kmail зависят от Qtlib, но ничего не зависит от Konqueror, и ничто не зависит от Kmail)

Теоретический ответ Графа на ваш вопрос, как указывали другие, заключается в том, что DAG нельзя преобразовать в дерево, а каждое дерево - DAG.

Однако, (отвечают высокоуровневые программисты), если вы хотите дерево для графических представлений, вас интересуют только зависимости конкретного модуля, а не то, что зависит от этого модуля. Позвольте мне привести пример:

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

Я не могу показать это как дерево ASCII-art по той простой причине, что это невозможно преобразовать в дерево. Однако, если вы хотите показать, от чего зависит A, вы можете показать это:

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

Как вы видите, вы получаете двойные записи в своем дереве - в данном случае "только" D, но если вы выполните "развернуть все" на дереве Gentoo, я гарантирую, что ваше дерево будет иметь как минимум 1000 раз сумму узлов, поскольку есть модули. (существует не менее 100 пакетов, зависящих от Qt, поэтому все Qt зависит от того, будет ли оно по меньшей мере 100 раз в дереве).

Если у вас есть "большое" или "сложное" дерево, лучше всего развернуть дерево динамически, а не заранее, иначе у вас может быть очень интенсивный процесс.

Недостатком дерева выше является то, что если вы нажмете на кнопку B, то D, вы увидите, что A и B зависят от D, но не то, что C зависит от D. Однако в зависимости от вашей ситуации это может быть не так важно, если вы поддерживаете список загруженных модулей, при загрузке C вы видите, что вы уже загрузили D, и неважно, что он не был загружен для C, а для B. Он загружен, что все это вопросы. Если вы динамически поддерживаете то, что напрямую зависит от определенного модуля, вы также можете справиться с другой проблемой (выгрузкой).

Однако то, что вы не можете сделать с деревом, - это то, что в вашем последнем предложении: сохранить топологический порядок, т.е. если B загружается в тот же контейнер, что и C, вы никогда не сможете загрузить C в том же контейнере, что и Что ж. Или вам, возможно, придется поместить все в один контейнер (не то, что я полностью понимаю, что вы имеете в виду с "загрузкой в ​​тот же контейнер" )

Удачи!

Ответ 2

DAG и дерево математически не одно и то же. Таким образом, любое преобразование вводит двусмысленность. Дерево по определению не имеет циклов, периода.

Ответ 3

То, что вы ищете, чтобы найти заказ на загрузку ваших модулей, это Топологическая сортировка вашей DAG. Если ребра переходят от модуля к модулю, это зависит от (что, я думаю, наиболее вероятно), вам придется загружать модули в обратном порядке топологической сортировки, потому что появится модуль - прежде всего модули от которого это зависит.

Если вы представляете DAG так, что ребра переходят от зависимых модулей к модулям, которые зависят от них (вы можете получить это, изменив все ребра на приведенном выше графике), вы можете просто загрузить модули в порядке топологической сортировки.

Ответ 4

Это зависит от того, как вы представляете свою группу DAG. Например, это может быть матрица смежности (A [i, j] = 1, если существует ребро от node я до node j, else 0) или как система указателей или как массив узлов и массив ребер....

Кроме того, неясно, какое преобразование вы пытаетесь применить. Связанная DAG - это дерево, поэтому, боюсь, вам нужно немного уточнить свой вопрос.

Ответ 5

Вы можете сделать это, только если все поддеревья имеют один корень node.