Как перераспределить элементы графа, чтобы максимизировать читабельность?

Question

У меня есть график, который состоит из узлов. Каждый узел может иметь несколько родителей и / или детей. Я хочу отобразить этот график и соединения между узлами.

Но я не знаю, как перераспределить узлы, чтобы максимизировать удобочитаемость. В настоящее время я сталкиваюсь со следующими проблемами:

• Соединения узлов слишком сильно пересекаются друг с другом, даже если это излишне и может быть исключено
• Визуальные соединения между узлами слишком длинные
• Некоторые соединения имеют одинаковый угол, поэтому они перекрываются и становятся одной линией
• Соединения между столбцом i и столбцом i-2 (и далее) иногда go сквозными элементами в столбце i-1

Также я могу смещать узлы только по вертикали, а не по горизонтали, потому что количество столбцов ограничено.

Чтобы упростить для себя, я попытался поместить узлы в сетчатый шаблон. И мне удалось сгруппировать их по столбцам. Но затем мне нужно как-то перебирать столбцы и сравнивать их с другими столбцами, чтобы переупорядочить вещи. И я не знаю с чего начать.

UPD: Я могу ошибаться, но я чувствую, что моя проблема с выравниванием графа как-то связана с типичной проблемой графа кратчайшего пути. За исключением того, что в моем случае есть несколько путей, которые должны быть рассчитаны одновременно, и некоторые узлы могут быть пропущены только один раз.

На изображении ниже вы можете увидеть почти идеальное перераспределение, которое я сделал, просто набросав вещи на бумаге (направление слева направо показывает связи между родителями и детьми).

Answer 1

Это графическая схема и проблема рисования. Вы можете выбрать один из следующих двух подходов:

1. Использовать уже существующие библиотеки : доступно множество библиотек макетов графиков, например GraphViz, Gephi, D3 js et c. Вы можете напрямую использовать их API или найти приложения / инструменты, созданные на их основе. Но чтобы получить лучший макет, вам нужно угадать семейство макетов. например, раскладка многослойного графа (хорошо для плотного, но многослойного графа, такого как блок-схемы). Разметка дерева (используется, когда граф на самом деле представляет собой дерево или лес. Существует много вариантов дерева), раскладка радиального дерева (опять же для дерева, но в полярной системе), направленная сила макеты (когда вы не знаете, какая визуальная структура лучше всего представляет данные, это хорошая отправная точка). Все эти макеты будут иметь много параметров настройки, таких как расстояние между узлами, расстояние между узлами и краями, общее соотношение сторон чертежа и т. Д. c. GraphViz Gephi

2. Реализация алгоритмов компоновки самостоятельно Подробное описание алгоритмов рисования графиков для разных семейств можно найти здесь Справочник по рисованию графиков

Если вы не хотите вдаваться в подробности, вот точки быстрого старта

1. Для графиков выполните топологическая сортировка и размещение узлов в слоях в соответствии с топологическим порядком. Это может дать вам очень хорошую отправную точку и поможет вам избежать ненужных пересечений. Сетка может быть хорошей идеей здесь. Но размещайте узлы в сетке в порядке топологии.
2. В качестве альтернативы найдите связующее дерево для графа, используйте компоновку дерева для рисования связующего дерева, а затем добавьте оставшиеся ребра
3. Для деревьев: используйте рекурсивные основания вверх подход для размещения поддеревьев. Для радиальных деревьев выполните прямолинейное расположение, а затем преобразуйте его в полярную систему координат
4. Для неизвестного семейства: используйте метод направленной силы. Определите силу между двумя узлами (например, усилие пружины), а затем go с помощью итераций, чтобы найти точку равновесия.

Лучшая автоматическая визуализация графика - очень интересная область, и люди пробуют многие техники ML здесь.

Answer 2

Вы можете реализовать принудительное рисование . Или вы можете использовать библиотеку графических рисунков, которая уже поддерживает принудительное рисование, например, принудительное расположение D3 .