Планарные макеты графика

Question

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

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

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

Answer 1

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

На приведенной ниже странице кратко описывается алгоритмы 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 (Основываясь на распределенной локализации без привязки в сенсорных сетях * Ниссанка Б. Приянта, Хари Балакришнан, Эрик Демейн и Сет Теллер)

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

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