Сокращение пересечения ребер в графике

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

Я нашел методы, такие как попытка разместить узлы вокруг другого узла, но я хотел бы знать некоторые другие идеи. Спасибо.

1 7
algorithm intersection

1 ответ:

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

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

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

2