ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Неориентированный граф
17 сообщений из 17, страница 1 из 1
Неориентированный граф
    #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, 13:25
| Ответить | Цитировать | Написать  
Неориентированный граф
    #32462356
гуест
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
гуест
Участник
Непонял а какие проблемы возникают с выбором всех дуг, выходящих из заданного нода. А для кратчайшего пути - еще одно поле в Links ВЕС_ДУГИ
...
Рейтинг: 0 / 0
30.03.2004, 14:59
| Ответить | Цитировать | Написать  
Неориентированный граф
    #32462528
Rymenar
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Rymenar
Гость
С двумя дугами никаких. Но куча проблем со вставкой/обновлением. Плюс на дуги ссылаются другие таблицы. Т.е. физически объект "дуга" один, а в графе представлен двумя записями в таблице, и на какую из них ссылаться? Поэтому и интересует, как можно сделать то же самое, но задав дугу один раз? И стоит ли вообще пытаться сделать так, или оставить вариант с двумя дугами?
...
Рейтинг: 0 / 0
30.03.2004, 16:13
| Ответить | Цитировать | Написать  
Неориентированный граф
    #32462581
Геша
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Геша
Гость
Если дуга одна , то и записей о ней должна быть одна .. иначе запутаешься ..
...
Рейтинг: 0 / 0
30.03.2004, 16:33
| Ответить | Цитировать | Написать  
Неориентированный граф
    #32462691
gardenman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
gardenman
Участник
А если описать дугу двумя таблицами?
в первой идентификатор дуги, а во второй- узлы в нее входящие?
...
Рейтинг: 0 / 0
30.03.2004, 17:22
| Ответить | Цитировать | Написать  
Неориентированный граф
    #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:39
| Ответить | Цитировать | Написать  
Неориентированный граф
    #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, 10:43
| Ответить | Цитировать | Написать  
Неориентированный граф
    #32463561
gardenman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
gardenman
Участник
>Тогда автор совсем запутается откуда дуга исходит и куда входит, не будет четкой ориентации

Сказано же ясно - НЕ ориентированный граф
...
Рейтинг: 0 / 0
31.03.2004, 11:56
| Ответить | Цитировать | Написать  
Неориентированный граф
    #32463580
gardenman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
gardenman
Участник
Три таблицы должно быть
1) Узлы
2) Дуги
3) Связь м/у узлами (т.к. узлы равнозначны)
...
Рейтинг: 0 / 0
31.03.2004, 12:04
| Ответить | Цитировать | Написать  
Неориентированный граф
    #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:37
| Ответить | Цитировать | Написать  
Неориентированный граф
    #32464239
gardenman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
gardenman
Участник
мои поздравления...)
Можно вопрос, что за задача, в которой это понадобилось?...
...
Рейтинг: 0 / 0
31.03.2004, 15:52
| Ответить | Цитировать | Написать  
Неориентированный граф
    #32464374
Rymenar
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Rymenar
Гость
БД телефонной сети. Объекты, связанные кабелями
...
Рейтинг: 0 / 0
31.03.2004, 16:37
| Ответить | Цитировать | Написать  
Неориентированный граф
    #32464790
c127
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
c127
Гость
Идем к истокам: неориентированный граф есть симметричное бинарное отношение на множестве вершин. Вот и создай представление, дополняющее отношение (таблицу дуг) до симметричного. Решит все проблемы.
...
Рейтинг: 0 / 0
01.04.2004, 00:51
| Ответить | Цитировать | Написать  
Неориентированный граф
    #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
01.04.2004, 11:37
| Ответить | Цитировать | Написать  
Неориентированный граф
    #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, 00:26
| Ответить | Цитировать | Написать  
Неориентированный граф
    #32466598
Rymenar
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Rymenar
Гость
Oracle
Скоростью запроса пока не занимался, просто набросал вот этот вариант как основу.
Ориентированных ребер не будет, так что этот вопрос снимается.
А повторяющиеся строчки не мешают, можно потом дополнительно их отсеять
...
Рейтинг: 0 / 0
02.04.2004, 10:38
| Ответить | Цитировать | Написать  
Неориентированный граф
    #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
06.04.2004, 09:14
| Ответить | Цитировать | Написать  
17 сообщений из 17, страница 1 из 1
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Неориентированный граф
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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