В чем преимущество возможности отображать зависимости системы в виде DAG (ориентированного ациклического графа)?

Question

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

Answer 1

У DAG есть несколько свойств, которые идеально подходят для анализа зависимостей.

Во-первых, вы можете легко определить компоненты «базового уровня» вашей системы.Это узлы в группе обеспечения доступности баз данных, в которые не входят ребра.Знание относительных уровней вашей системы означает, что вы знаете влияние рефакторинга.(Все по цепочке.)

Во-вторых, если вы можете создать DAG, вы знаете, что в системе нет странных взаимозависимостей.Циклы в графе зависимостей означают, что у вас есть два компонента, которые полагаются друг на друга — это рецепт странных ошибок и ошибок сборки.В Microsoft мы использовали инструмент под названием асммета чтобы обойти эту проблему.

Answer 2

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

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

В основном, я думаю, это зависит от того, какие алгоритмы вы хотите запустить в своем представлении.Если вы не уверены, что у вас есть DAG, вы можете запустить алгоритм обнаружения цикла чтобы сказать вам, так это или нет.Если вы хотите найти кратчайшие пути, вы можете запустить Дейкстры в теме.Я думаю, что это действительно зависит от того, что вы хотите сделать, и я знаю, что вы можете сделать с общим графиком, что в основном связано с доказательством того, что это DAG.Когда у вас есть группа обеспечения доступности баз данных, большинство вещей, которые я хотел бы установить, уже установлены.Хотя это только я.

-Брайан Дж.Стинар-