Схемы планарного графика

Question

Какие существуют методы минимизации перекрытия краев при построении графика? (Предпочтительно относится к GraphViz). Также существует ли какое-либо существующее программное обеспечение, которое может размещать график в плоском виде?

Текущий макет - http://www.evecakes.com/doodles/master.gif

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

Answer 1

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

На странице ниже кратко описываются алгоритмы graphviz и предлагаются некоторые способы их использования для выгоды. Он также имеет ссылки на PDF-файлы, которые должны содержать больше информации об алгоритмах:

http://rss.acs.unt.edu/Rdoc/library/Rgraphviz/html/GraphvizLayouts.html

Надеюсь, это поможет.

Answer 2

В следующей библиотеке Java с открытым исходным кодом есть пара алгоритмов, которые могут помочь в построении плоских графов. http://open.trickl.com/trickl-graph/index.html

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

ChrobakPayneLayout (на основе реализации Boost C ++ Аарона Виндзора) http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/straight_line_drawing.html

FoldFreeLayout (основано на распределенной локализации без привязки в сенсорных сетях * Ниссанка Б. Приянта, Хари Балакришнан, Эрик Демейн и Сет Теллер)

То, что вы можете сделать, это использовать что-то вроде этого в качестве первой «попытки», которая гарантирует отсутствие совпадений, хотя может и не выглядеть великолепно. Затем вы можете применить силовой алгоритм для более справедливого разнесения узлов.

К сожалению, библиотека только что была выпущена, поэтому не хватает документации. Однако это может быть полезно, если предоставить какой-то реальный код, а не просто теорию.