Алгоритм генерации программной диаграммы стека
Я ищу идеи для алгоритма, который генерирует диаграмму, похожую на следующую, с учетом набора ациклических зависимостей (я использую это изображение, чтобы показать, что зависимости могут быть сложными)
http://www.interactivetvweb.org/images/tutorials/mhp/mhp_software_stack.gif
3 ответа
Не всегда будет возможно сделать такую диаграмму. (Ациклическое) отношение зависимости:
А зависит от X, Y, Z
B зависит от X, Y, Z
C зависит от X, Y, Z
описывает полный двудольный граф на шести вершинах, который является неплоским. Следствием этого для типа диаграммы, которую вы показываете, является то, что, по крайней мере, одна из областей на вашем графике должна быть либо разделена на две отдельные части, и / или, по крайней мере, одна из областей не должна напрямую соединяться с зависимой.
Эту проблему можно избежать с помощью визуализации на основе графа (например, graphvis), где ребра могут пересекаться друг с другом.
Схема эвристического алгоритма для создания нужных вам диаграмм выглядит следующим образом:
- Разобрать дерево зависимостей, чтобы вычислить "уровень" для каждого элемента. В приведенном выше примере X, Y и Z будут отображаться три раза на этом графике на уровне 1 как дочерние элементы каждого из A, B и C (на уровне 0).
- Нарисуйте дерево очевидным образом, с элементами на каждом "уровне" на одном и том же горизонтальном уровне, а их предки / дети ниже / выше их соответственно. Есть выбор относительно того, в каком порядке предметы размещены на каждом уровне.
- Вычислите некоторую метрику того, насколько хороша диаграмма, исходя из того, сколько раз отдельный элемент разбивается на несколько областей на графике. Если порядок элементов хороший, а две или более области, представляющие один и тот же элемент, соприкасаются друг с другом, их можно объединить.
- Используйте эту метрику, чтобы оптимизировать перестановки элементов на одном уровне, используя комбинаторный алгоритм оптимизации, такой как алгоритм Метрополис.
Это не даст лучший график каждый раз (если такая концепция даже четко определена...), но должно делать разумную работу для таких задач, как ваш пример.
Хотя это и не алгоритм (именно об этом вы и просили), вы, возможно, захотите проверить NDepend, который выполняет анализ, аналогичный тому, который вы ищете:
(У меня нет связи с NDepend)