Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Неориентированный граф / 17 сообщений из 17, страница 1 из 1
30.03.2004, 13:25
    #32462153
Rymenar
Rymenar
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Неориентированный граф
Задача классическая: есть несколько узлов и связи между ними. Связи неориентированные (т.е двунаправленные). Каждая связь, помимо собственно узлов, описывается еще и некоторыми параметрами на каждом узле.
Содаю две таблицы:
Nodes (node_id, node_name)
Links (link_id, node_start_id, node_start_params, node_end_id, node_end_params)
Проблема как раз с двунаправленностью дуг. Т.е. запись в таблице Nodes типа (..., 1, ..., 2, ...) описывает дугу от узла 1 к узлу 2. При этом должно подразумеваться, что эта же дуга является дугой от узла 2 к узлу 1.
Вроде бы проще всего показалось автоматически добавлять обратную дугу (от 2 к 1) как еще одну запись в таблице. Тут вылезло сразу куча проблем: автоматическое дублироваие триггером сделать не получилось (ограничения на mutating table), и аналогично с обновлением - синхронизация свойств этих дуг и т.д., поэтому все Insert/Updatу через ХП. Можно и дальше в этом направлении двигаться, но очень уж громоздко выходит.
Можно ли как нибудь обойтись средствами SQL без создания обратной связи, для, например, получения всех дуг, выходящих из конкретного узла? И хватит ли такой структуры (без явно заданных обратных дуг) для решения дальнейших задач (планируется, в частности, поиск кратчайшего пути)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.03.2004, 14:59
    #32462356
гуест
гуест
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Неориентированный граф
Непонял а какие проблемы возникают с выбором всех дуг, выходящих из заданного нода. А для кратчайшего пути - еще одно поле в Links ВЕС_ДУГИ
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.03.2004, 16:13
    #32462528
Rymenar
Rymenar
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Неориентированный граф
С двумя дугами никаких. Но куча проблем со вставкой/обновлением. Плюс на дуги ссылаются другие таблицы. Т.е. физически объект "дуга" один, а в графе представлен двумя записями в таблице, и на какую из них ссылаться? Поэтому и интересует, как можно сделать то же самое, но задав дугу один раз? И стоит ли вообще пытаться сделать так, или оставить вариант с двумя дугами?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.03.2004, 16:33
    #32462581
Геша
Геша
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Неориентированный граф
Если дуга одна , то и записей о ней должна быть одна .. иначе запутаешься ..
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.03.2004, 17:22
    #32462691
gardenman
gardenman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Неориентированный граф
А если описать дугу двумя таблицами?
в первой идентификатор дуги, а во второй- узлы в нее входящие?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.03.2004, 10:39
    #32463342
bas
bas
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Неориентированный граф
А если описать дугу двумя таблицами?
в первой идентификатор дуги, а во второй- узлы в нее входящие?

Тогда автор совсем запутается откуда дуга исходит и куда входит, не будет четкой ориентации.

А если сделать так:
Nodes (node_id, node_name)
Links (link_id, node_id_1, node_id_2, )
LinksDetail(ld_id, link_id, node_start_params, node_end_params, trend), детали связи, если связь идет от узла1 к узлу2, то trend = 1, если наоборот trend = -1

и запрос:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
select decode(ld.trend,  1 , n1.node_name, - 1 , n2.node_name), 
       decode(ld.trend,  1 , n2.node_name, - 1 , n1.node_name),
       decode(ld.trend,  1 , n1.node_id, - 1 , n2.node_id), 
       decode(ld.trend,  1 , n2.node_id, - 1 , n1.node_id),
       ld.ld_id link_id, ld.node_start_params, ld.node_end_params
from node n1,  node n2, links l, linksdetail ld
where n1.node_id = l.node_id_1
  and n2.node_id = l.node_id_2
  and l.link_id =  ld.link_id
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.03.2004, 10:43
    #32463353
bas
bas
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Неориентированный граф
Забыл, что запрос для Oracle. Так работает Decode:



DECODE Expressions
A DECODE expression uses the special DECODE syntax:
Syntax:=
DECODE (expr, search, result{,search,result...} {,default})

To evaluate this expression, Oracle compares expr to each search value one by one. If expr is equal to a search, Oracle returns the corresponding result. If no match is found, Oracle returns default, or, if default is omitted, returns null. If expr and search contain character data, Oracle compares them using nonpadded comparison semantics.

rrrrrrrr
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.03.2004, 11:56
    #32463561
gardenman
gardenman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Неориентированный граф
>Тогда автор совсем запутается откуда дуга исходит и куда входит, не будет четкой ориентации

Сказано же ясно - НЕ ориентированный граф
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.03.2004, 12:04
    #32463580
gardenman
gardenman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Неориентированный граф
Три таблицы должно быть
1) Узлы
2) Дуги
3) Связь м/у узлами (т.к. узлы равнозначны)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.03.2004, 15:37
    #32464184
Rymenar
Rymenar
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Неориентированный граф
Сделал в итоге так:
Nodes (node_id, node_name)
Links (link_id, link_params)
NodesLinks(nl_id, link_id, node_id, node_link_params)
link_params - параметры для дуги в целом. node_link_params - перекочевавшие сюда параметры связи для каждого из узлов. Для каждой связи по две записи в NodesLinks (для каждого из узлов). заодно получилась возможность делать уходящие в "никуда" дуги (что тоже оказалось нужным.
Правда запрос для выборки из всего этого счастья получился просто жутким, но это уже другая проблема
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.03.2004, 15:52
    #32464239
gardenman
gardenman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Неориентированный граф
мои поздравления...)
Можно вопрос, что за задача, в которой это понадобилось?...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.03.2004, 16:37
    #32464374
Rymenar
Rymenar
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Неориентированный граф
БД телефонной сети. Объекты, связанные кабелями
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.04.2004, 00:51
    #32464790
c127
c127
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Неориентированный граф
Идем к истокам: неориентированный граф есть симметричное бинарное отношение на множестве вершин. Вот и создай представление, дополняющее отношение (таблицу дуг) до симметричного. Решит все проблемы.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.04.2004, 11:37
    #32465156
Rymenar
Rymenar
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Неориентированный граф
Похоже, даже проще получается
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
create view vwAllLinks as
select l.link_id, l.link_name, n1.node_name as node_start_name, l.node_start_param, n2.node_name as node_end_name, l.node_end_param
from links l, nodes n1, nodes n2
where
  l.node_start_id=n1.node_id and
  l.node_end_id=n2.node_id
union all
select l.link_id, l.link_name, n2.node_name, l.node_end_param, n1.node_name, l.node_start_param
from link l, node n1, node n2
where
  l.node_start_id=n1.node_id and
  l.node_end_id=n2.node_id

Вроде так, да?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.04.2004, 00:26
    #32466297
c127
c127
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Неориентированный граф
2 Rymenar

Похоже на правду. Я бы в начале построил правильное симметричное отношение Links (возможно виртуальное), а потом соединял бы его с nodes, но это дело вкуса, к тому же в смысле скорости выполнения может зависеть от конкретной задачи и SQL сервера. Нужно смотреть планы запросов. Какой SQL сервер? Похоже что MSSQL сервер. Еще нужно решить:

*) Хочешь ли ты убирать ориентированные ребра, т.е. если в таблицу вдруг попало ориентированное ребро (это когда в таблице Links для пары (x,y) присутствует пара (y,x), но с другими параметрами), то показывать ли его в представлении, или проигнорировать, заменив на неориентрированное по общему правилу. В последнем случае можно в представление добавить в что-то вроде (опять же зависит от постановки) "where node_start_id<node_end_id" или соответсвующее ограничение в таблицу.
*) Мешают ли тебе в представлении повторяющиеся строчки.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.04.2004, 10:38
    #32466598
Rymenar
Rymenar
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Неориентированный граф
Oracle
Скоростью запроса пока не занимался, просто набросал вот этот вариант как основу.
Ориентированных ребер не будет, так что этот вопрос снимается.
А повторяющиеся строчки не мешают, можно потом дополнительно их отсеять
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.04.2004, 09:14
    #32469987
Valer
Valer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Неориентированный граф
для неориентированного графа хватает и двух таблиц

Nodes (node_id, node_name)
Links (link_id, node_start_id, node_end_id, длина дуги )

на одну дугу 1 запись

просто когда нужно посмотреть все дуги из узла нужно делать UNION
where node_start_id= my_node ... union ... where node_end_id= my_node
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Неориентированный граф / 17 сообщений из 17, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]