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