Алгоритмы компановки (расстановки, layout) графов

← →
pasha_golub © (2008-03-05 14:56) [0]

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

Есть такой редактор yEd: http://www.yworks.com/en/products_yed_about.html

Если у вас установлена Java Web Start, то просто нажмите на той страничке кнопку Launch, если нет скачайте отсюда
дистрибутив уже с JRE http://www.yworks.com/en/products_download.php?file=yEd3_0_0_8_with_JRE_setup.exe

Запускаете, потом выбираете Sample project. Когда граф загрузится поиграйте с любыми пунктами в меню Layout (или
нажмите Alt-Shift-H, а потом кнопку OK)

Ткните носом на информацию по этой теме. Можно на англицком. Спасибо

← →
boriskb © (2008-03-05 15:53) [1]

Какая забавная игрушка.
Куда бы ее приладить?

← →
MBo © (2008-03-05 16:16) [2]

http://alenacpp.blogspot.com/2006/02/blog-post_10.html
а вообще это целая наука - конференции по укладке графов проводятся, книги выходят, например:
Nishizeki Rahman Planar Graph Drawing

← →
pasha_golub © (2008-03-05 16:52) [3]

> MBo © (05.03.08 16:16) [2]

> а вообще это целая наука

Я понимаю. Был немножко причастен к этой теме. Мне бы с чего начать. Не думаю, что надо будет решать задачу планарной укладки графа в чистом виде. Лишь часть ее для лучшей визуализации. А остальное пусть пользователь по своему усмотрению.

> boriskb © (05.03.08 15:53) [1]
>
> Какая забавная игрушка.

Эт, точно. Однако не знаю, Visio умеет такое или нет?

← →
MBo © (2008-03-05 16:55) [4]

Упомянутая книжка в эл. виде у меня есть (16M), могу выложить, если нужна.

← →
pasha_golub © (2008-03-05 17:12) [5]

> MBo © (05.03.08 16:55) [4]
>
> Упомянутая книжка в эл. виде у меня есть (16M), могу выложить,
> если нужна.

Было бы очень здорово. За ссылки тоже спасибо. Познавательно.

← →
boriskb © (2008-03-05 17:14) [6]

> Visio умеет такое или нет?

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

← →
MBo © (2008-03-05 17:23) [7]

http://slil.ru/25548731

← →
Jeer © (2008-03-05 17:37) [8]

Шикарная цацка yEd !

← →
pasha_golub © (2008-03-05 17:46) [9]

> boriskb © (05.03.08 17:14) [6]

> Насколько я помню (давно не сталкивался), там примитивов
> гораздо больше. Помогучей она.

Абсолютно. По ссылке, приведенной Борисом, так проблема и поставлена: есть диаграмма в Визио, осуществить автоматическую укладку.

> MBo © (05.03.08 17:23) [7]
>
> http://slil.ru/25548731
>

Спасибо.

> Jeer © (05.03.08 17:37) [8]
>
> Шикарная цацка yEd !
>

Сам офигел. Загорелся тут же. Чего давно не случалось по работе.

В статьях, что я прочитал рекомендуется книга Graph Drawing Algorithms for the Visualization of Graphs. Если кому надо, ее можно найти в Ослике:
это Graph Drawing Algorithms for the Visualization of Graphs.
ed2k://|file|Graph%20Drawing%20%20Algorithms%20For%20The%20Visualization%20Of%20Graphs%20Ioannis%20G%20Tollis%201998%20Prentice%20Hall%20397S.djvu|36261219|B9AFB433FF92867237B13088FF7F3F83|/

Сам только качать начал, поэтому не знаю ничего о качестве. Источников мало.

В качестве введения в теорию визуализации неплохо выглядит: http://www.cs.brown.edu/%7Ert/papers/gd-tutorial/gd-constraints.pdf (сейчас читаю)

> pasha_golub © (05.03.08 17:46) [9]

Как-то, давно уж, возникала задача отрисовки.
Времени было мало на чтение теорий и я реализовал это следующим образом.
Граф - планарный в виже дерева корнем вверх.
Дело происходит в однородном гравиполе и изначально все в одной материальной точке.
Каждый элемент обладает массой, а также взаимодействует с другими элементами силами отталкивания.
Связные линии обладают упругостью на растяжение.
В результате возникает самоорганизующаяся структура в виде обращенного дерева.

> Jeer © (05.03.08 18:16) [10]

Изящно, наверное. Но у меня мышление не физическое да и по условию граф не планарный, а направленный произвольного вида.

Есть еще такая книга (сразу её не заметил)
series editor: Chang
author: Sugiyama
Graph Drawing and Applications
for software and knowledge engineers
djvu 7 мег
http://slil.ru/25550808

кстати, напомню об одном из самых известных пакетов
http://www.graphviz.org/

Алгоритмы компановки (расстановки, layout) графов Найти похожие ветки