Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Связывание объектов структуры.


Автор: ArsNov 5.9.2007, 20:17
У меня появилась такая задача:
Мне нужно в графическом виде отобразить структуру.
Есть n объектов:

Например четыре:
O--->O--->O--->O

Все эти объекты каким-то образом связаны(стрелочки).
Условия.
Из одного объекта может быть сколько угодно много выходов которые ведут в другие объекты(например из первого "О" выходит пять линий. одна входит во вторую "o" , одна в третью, и две в саму себя, одна в четвертую). 

Есть ли какие-то примеры, алгоритмы? Можно ли это сделать через матрицы(таблицы. Задачу решаю для html) красиво, чтобы не было пересечений линий.?  любые варианты ...плиз  Сорри, если криво объяснил smile 

И еще вопрос! Есть ли какие-нибудь более простые способы отображения таких структур, чтобы пользователю, который на это дело смотрит было легко понять связи)?

Автор: _Y_ 5.9.2007, 21:04
Это Вам, видимо, нужно строить нейронные сети. Поищите по ним - наверняка найдете. в Java кажется были даже готовые пакеты для этих целей - во всяком случае я натыкался на них в сети. Правда не проверял хорошие пакеты или нет. Да и готовых программ много для таких целей.

Автор: JackYF 5.9.2007, 22:41
Цитата(ArsNov @  5.9.2007,  20:17 Найти цитируемый пост)
И еще вопрос! Есть ли какие-нибудь более простые способы отображения таких структур, чтобы пользователю, который на это дело смотрит было легко понять связи)? 

Цитата(_Y_ @  5.9.2007,  21:04 Найти цитируемый пост)
Это Вам, видимо, нужно строить нейронные сети.

насколько мне известно, нет.

Эта задача имеет классическое название "отображение планарного графа на плоскости без пересечений" и решается, ЕМНИП, полиномиальным алгоритмом.

Погуглите. Наверняка найдете.

Автор: Mayk 5.9.2007, 22:48
Если совсем будет туго, то можно посмотреть сырцы http://freshmeat.net/projects/graphviz'a. Он умеет отображать графы. 

Автор: ArsNov 6.9.2007, 15:00
Цитата(JackYF @ 5.9.2007,  22:41)
Цитата(ArsNov @  5.9.2007,  20:17 Найти цитируемый пост)
И еще вопрос! Есть ли какие-нибудь более простые способы отображения таких структур, чтобы пользователю, который на это дело смотрит было легко понять связи)? 

Цитата(_Y_ @  5.9.2007,  21:04 Найти цитируемый пост)
Это Вам, видимо, нужно строить нейронные сети.

насколько мне известно, нет.

Эта задача имеет классическое название "отображение планарного графа на плоскости без пересечений" и решается, ЕМНИП, полиномиальным алгоритмом.

Погуглите. Наверняка найдете.

_Y_ Спасибо за ссылки на инфо, буду искать. А пока возник вопрос: всегда ли при заданных мной условиях граф планарный(т.е. не пересекающийся)? И есть ли способ определения планарности?

Автор: JackYF 6.9.2007, 17:04
Цитата(ArsNov @  6.9.2007,  15:00 Найти цитируемый пост)
А пока возник вопрос: всегда ли при заданных мной условиях граф планарный

нет, не всегда.

Цитата(ArsNov @  6.9.2007,  15:00 Найти цитируемый пост)
И есть ли способ определения планарности? 

есть, должен быть где-то там же, где и алгоритм отображения.

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

Автор: skyboy 6.9.2007, 17:50
куча ссылок была на http://alenacpp.blogspot.com. 
Вот http://alenacpp.blogspot.com/2006/03/blog-post_23.html на тему отрисовки графов.

Автор: ArsNov 6.9.2007, 21:18
Цитата(skyboy @ 6.9.2007,  17:50)
куча ссылок была на http://alenacpp.blogspot.com. 
Вот http://alenacpp.blogspot.com/2006/03/blog-post_23.html на тему отрисовки графов.

Спасибо, накачаю книжек, буду умным  smile 

Автор: skyboy 7.9.2007, 09:10
ArsNov, если внимательно просмотришь пост, то найдешь и ссылку на другой пост, где описываются уже готовые библиотеки  smile

Добавлено через 26 секунд
Цитата(skyboy @  7.9.2007,  08:10 Найти цитируемый пост)
если внимательно просмотришь пост

я имел в виду пост на alenacpp.blogspot.com

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)