Алгоритм для создания диаграммы стека программного обеспечения

Question

Я ищу идеи для алгоритма, который генерирует диаграмму, подобную следующей, учитывая набор ациклических зависимостей (я использую это изображение, чтобы показать, что зависимости могут быть сложными)

alt text http://www.interactivetvweb.org/images/tutorials/mhp/mhp_software_stack.gif

Answer 1

Хотя не алгоритм (который является то, что вы просили) вы можете проверить NDepend, который выполняет подобный анализ и генерирует подобные диаграммы в одном вы после:

http://ndepend.com/

(У меня нет принадлежности к NDepend)

Answer 2

Невозможно сделать такую ​​диаграмму. (Ациклические) отношения зависимость:

А зависит от X, Y, Z,

В зависит от X, Y, Z,

С зависит от X, Y, Z,

описывает полный двудольный граф на шести вершинах, который равен non-planar. Следствием этого для типа диаграммы, которую вы показываете, является то, что хотя бы одна из областей вашего графика должна быть разделена на две отдельные части и/или по крайней мере одна из областей не должна напрямую соединяться с ее зависимым.

Эта проблема устранена на основе графической визуализации (например, graphvis), где края могут пересекать друг друга.

Схемы эвристического алгоритма для получения рода диаграмм вы ищете выглядят следующим образом:

1. Разбирает дерево зависимостей для расчета «уровня» для каждого элемента. В приведенном выше примере X, Y и Z будут отображаться три раза на этом графе на уровне 1, поскольку дети каждого из A, B и C (на уровне 0)
2. Нарисуйте дерево очевидным образом, с элементами на каждом «уровне» на одном и том же горизонтальном уровне и их предками/детьми ниже/выше их соответственно. Существует выбор того, какой порядок предметов размещен на каждом уровне.
3. Рассчитайте некоторые показатели того, насколько хороша диаграмма, исходя из того, сколько раз один элемент разбивается на несколько областей на графике. Если порядок товаров хорош, а две или более области, представляющие один и тот же элемент, касаются друг друга, вы можете сплавить их вместе.
4. Используйте этот показатель, чтобы оптимизировать перестановки элементов на том же уровне, используя комбинаторный алгоритм оптимизации, такой как Metropolis algorithm.

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

Answer 3

STAN4J генерирует такие диаграммы из java-кода.