ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Firebird, InterBase [игнор отключен] [закрыт для гостей] / Поиск циклических ссылок в графе
9 сообщений из 9, страница 1 из 1
Поиск циклических ссылок в графе
    #38552965
Kirill Razuvaev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kirill Razuvaev
Участник
Здравствуйте!
Есть граф с множеством вершин, единого корня нет. Связи графа описаны таблицей вида:
Код: sql
1.
2.
3.
create table Links(
OBJ1_ID integer,
OBJ2_ID integer);

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

FB 2.5.2
...
Рейтинг: 0 / 0
07.02.2014, 11:18:52
| Ответить | Цитировать | Написать  
Поиск циклических ссылок в графе
    #38552982
Фотография Симонов Денис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Симонов Денис
Участник
Kirill Razuvaev,

это довольно сложный вопрос. Если добавление делать в процедуре, то после INSERT можно сделать рекурсивный запрос (WITH RECURSIVE) и если глубина рекурсии превышает некую максимально допустимую считать, что у тебя есть цикл и генерировать исключение, откатывая транзакцию. Глубина рекурсии для рекурсивного запроса ограничена значением 1023. Но в многопользовательской среде никаких гарантий это не даст.
...
Рейтинг: 0 / 0
07.02.2014, 11:30:21
| Ответить | Цитировать | Написать  
Поиск циклических ссылок в графе
    #38553026
Kirill Razuvaev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kirill Razuvaev
Участник
Симонов Денисэто довольно сложный вопрос. Если добавление делать в процедуре, то после INSERT можно сделать рекурсивный запрос (WITH RECURSIVE) и если глубина рекурсии превышает некую максимально допустимую считать, что у тебя есть цикл и генерировать исключение, откатывая транзакцию. Глубина рекурсии для рекурсивного запроса ограничена значением 1023. Но в многопользовательской среде никаких гарантий это не даст.Поисковые системы уже дали понять, что легких путей нет, но в моем случае наиболее вероятны циклы на глубине от 2 до 10, а длина цепочки редко превышает 15. Вопрос в том, как грамотно поиск организовать. Пока не понимаю даже, как к нему подойти.
...
Рейтинг: 0 / 0
07.02.2014, 11:52:35
| Ответить | Цитировать | Написать  
Поиск циклических ссылок в графе
    #38553132
Гхостик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гхостик
Гость
with recursive?
...
Рейтинг: 0 / 0
07.02.2014, 12:37:46
| Ответить | Цитировать | Написать  
Поиск циклических ссылок в графе
    #38553133
Фотография Симонов Денис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Симонов Денис
Участник
Kirill Razuvaev,

для начала в саму таблицу ссылок надо добавить собственный ПК. Так проще будет.

Код: sql
1.
2.
3.
4.
create table Links(
ID integer primary key,
OBJ1_ID integer,
OBJ2_ID integer);



Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
with recursive t(id, obj1_id, obj2_id, depth, flag) as (
  select 
     id,
     obj1_id,
     obj2_id,
     0,
     0
  from links
  where id = :id
  union all
  select
    links.id,
    links.obj1_id,
    links.obj2_id,
    t.depth + 1,
    iif(links.id = :id, 1, 0)
  from t
  join links on t.obj2_id = links.obj2_id
  where depth<:max_depth or links.id = :id
)
select max(flag)
from t
into :flag



Если flag = 1 есть цикл. Правда если за max_depth шагов не найдёт, значит цикл не определит
...
Рейтинг: 0 / 0
07.02.2014, 12:37:52
| Ответить | Цитировать | Написать  
Поиск циклических ссылок в графе
    #38553366
Kirill Razuvaev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kirill Razuvaev
Участник
Симонов Денисдля начала в саму таблицу ссылок надо добавить собственный ПК. Так проще будет.
Спасибо, посмотрю!
...
Рейтинг: 0 / 0
07.02.2014, 14:00:58
| Ответить | Цитировать | Написать  
Поиск циклических ссылок в графе
    #38553382
Фотография Симонов Денис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Симонов Денис
Участник
Симонов Денис,

ой. Вот это конечно надо поправить
Код: sql
1.
where depth<:max_depth or links.id = :id


на
Код: sql
1.
where depth<:max_depth or t.flag = 1
...
Рейтинг: 0 / 0
07.02.2014, 14:06:08
| Ответить | Цитировать | Написать  
Поиск циклических ссылок в графе
    #38553534
Kirill Razuvaev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kirill Razuvaev
Участник
Симонов Денисдля начала в саму таблицу ссылок надо добавить собственный ПК. Так проще будет.А если вместо ПК обойтись RDB$DB_KEY?
...
Рейтинг: 0 / 0
07.02.2014, 14:58:57
| Ответить | Цитировать | Написать  
Поиск циклических ссылок в графе
    #38553545
Фотография Симонов Денис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Симонов Денис
Участник
Kirill RazuvaevА если вместо ПК обойтись RDB$DB_KEY?
не уверен что это будет правильно работать. Тогда уж лучше по составному ключу OBJ1_ID, OBJ2_ID. Ведь между двумя вершинами ставиться всегда только одна связь (по крайней мере в заданном направлении)?
...
Рейтинг: 0 / 0
07.02.2014, 15:03:56
| Ответить | Цитировать | Написать  
9 сообщений из 9, страница 1 из 1
Форумы / Firebird, InterBase [игнор отключен] [закрыт для гостей] / Поиск циклических ссылок в графе
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=40&msg=38553132&tid=1563908]:
 0ms
get settings:
 8ms
get forum list:
 8ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 166ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 49ms
get tp. blocked users:
 1ms
others: 204ms
total:  450ms
созд. / загр.: 450ms
x
x
Закрыть


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