Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > СУБД, общие вопросы > Хранение графа в базе данных

Автор: Illuminaty 19.3.2005, 20:56

Вопрос в следующем. Задан граф. Заданы веса ребер. Как сохранить его в БД? Необходима такая реализация, чтобы удобно было с ней работать. Т.е. осуществление выборок для нахождения пути от одной вершины к другой Кто нибудь делал похожее? И у кого какие идеи? Подчеркиваю: необходима реализация в виде структуры таблиц

Автор: LSD 20.3.2005, 00:59

Самый очевидный способ: две таблицы одна список вершин, вторая список ребер с весами ребро имеет два foreign key на таблицу вершин и поле вес. Найти все пути, фиксированной длинны, из заданного ребра можно будет одним запросом.

Автор: Illuminaty 20.3.2005, 10:54

LSD Спасибо за ответ, но возникает резонный вопрос: а сколько запросов потребуется для реализации нахождения пути из вершины А в вершину Б, учитывая, что вершин достаточно много (больше 1000)? Над предложенной реализацией я думал уже , но в силу заданного вопроса она показалась мне недостаточной. Понятно, что плясать надо от нее - слов нет...

Автор: LSD 21.3.2005, 20:19

Внимание аттракцион! Сейчас с помощью ловкости рук мы получим все не циклические пути из точки B! Код /* Создаем таблицы */ drop table GRAPH_NODES cascade constraints; create table GRAPH_NODES (   NAME VARCHAR2(20) not null ); alter table GRAPH_NODES add constraint GRAPH_PK primary key (NAME); drop table GRAPH_EDGES cascade constraints; create table GRAPH_EDGES (   NODE1 VARCHAR2(20) not null,   NODE2 VARCHAR2(20) not null ); alter table GRAPH_EDGES add constraint GRAPH_EDGES_NODE1_FK foreign key (NODE1) references GRAPH_NODES (NAME); alter table GRAPH_EDGES add constraint GRAPH_EDGES_NODE2_FK foreign key (NODE2) references GRAPH_NODES (NAME); alter table GRAPH_EDGES add constraint GRAPH_EDGES_CIRCLE check (node1 <> node2); /* Заполняем таблицы значениями */ insert into GRAPH_NODES (NAME) values ('A'); insert into GRAPH_NODES (NAME) values ('B'); insert into GRAPH_NODES (NAME) values ('C'); insert into GRAPH_NODES (NAME) values ('D'); insert into GRAPH_NODES (NAME) values ('E'); insert into GRAPH_NODES (NAME) values ('F'); insert into GRAPH_EDGES (NODE1 , NODE2) values ('A' , 'B'); insert into GRAPH_EDGES (NODE1 , NODE2) values ('B' , 'A'); insert into GRAPH_EDGES (NODE1 , NODE2) values ('A' , 'C'); insert into GRAPH_EDGES (NODE1 , NODE2) values ('C' , 'A'); insert into GRAPH_EDGES (NODE1 , NODE2) values ('B' , 'C'); insert into GRAPH_EDGES (NODE1 , NODE2) values ('C' , 'B'); insert into GRAPH_EDGES (NODE1 , NODE2) values ('C' , 'D'); insert into GRAPH_EDGES (NODE1 , NODE2) values ('D' , 'C'); insert into GRAPH_EDGES (NODE1 , NODE2) values ('C' , 'E'); insert into GRAPH_EDGES (NODE1 , NODE2) values ('E' , 'C'); insert into GRAPH_EDGES (NODE1 , NODE2) values ('D' , 'E'); insert into GRAPH_EDGES (NODE1 , NODE2) values ('E' , 'D'); insert into GRAPH_EDGES (NODE1 , NODE2) values ('D' , 'F'); insert into GRAPH_EDGES (NODE1 , NODE2) values ('F' , 'D'); insert into GRAPH_EDGES (NODE1 , NODE2) values ('E' , 'F'); insert into GRAPH_EDGES (NODE1 , NODE2) values ('F' , 'E'); commit; А теперь следим за руками: Код SQL> select distinct sys_connect_by_path(node1,'/') path   2    from graph_edges   3    start with node1 = 'B'   4    connect by nocycle prior node1 = node2; PATH -------------------------------------------------------------------------------- /B /B/A /B/A/C /B/A/C/D /B/A/C/D/E /B/A/C/D/E/F /B/A/C/D/F /B/A/C/D/F/E /B/A/C/E /B/A/C/E/D /B/A/C/E/D/F /B/A/C/E/F /B/A/C/E/F/D /B/C /B/C/A /B/C/D /B/C/D/E /B/C/D/E/F /B/C/D/F /B/C/D/F/E /B/C/E /B/C/E/D /B/C/E/D/F /B/C/E/F /B/C/E/F/D 25 строк выбрано. Правда я здесь использовал специфичные фишки Oracle и если база будет не Oracle, то не прокатит. Это я к тому, что неплохо бы знать что за база.

Автор: Illuminaty 21.3.2005, 23:36

Да уж.... С Oracle не сталкивался, поэтому есть загадочные элементы Причем много... А база, скорее всего MySQL Думал, что можно все решить хорошей реализацией, не зависящей от платформы

Автор: LSD 21.3.2005, 23:41

Цитата(Illuminaty @ 21.3.2005, 23:36) А база, скорее всего MySQL Упс А я с MySQL не знаком, а как у него с join-нами?

Автор: Illuminaty 21.3.2005, 23:55

LSD Да, вроде бы, нормально

Автор: LSD 24.3.2005, 22:35

ИМХО все должно быть ОК. Т.к. именно так граф представляется в математике (множество вершин и множество ребер) и соответсвенно все алгоритмы поиска пути в графе расчитанны именно на такое представление. Вот например как можно реализовать алгоритм http://algolist.manual.ru/maths/graphs/shortpath/dijkstra.php, это уже для Interbase (у меня нет под рукой MySQL). Код /* Создаем таблицы */ create table GRAPH_NODES (   NAME      VARCHAR(5)       not null ); alter table GRAPH_NODES add constraint GRAPH_PK primary key (NAME); create table GRAPH_EDGES (   NODE1     VARCHAR(5)       not null,   NODE2     VARCHAR(5)       not null,   WEIGHT    DECIMAL(10,0)    not null ); alter table GRAPH_EDGES add constraint GRAPH_EDGES_NODE1_FK foreign key (NODE1) references GRAPH_NODES (NAME); alter table GRAPH_EDGES add constraint GRAPH_EDGES_NODE2_FK foreign key (NODE2) references GRAPH_NODES (NAME); alter table GRAPH_EDGES add constraint GRAPH_EDGES_CIRCLE check (node1 <> node2); create table DEXTRA (   NODE      VARCHAR(5)       not null,   WEIGHT    DECIMAL(18,0)    not null ); alter table DEXTRA add constraint DEXTRA_PK primary key (NODE); alter table DEXTRA add constraint DEXTRA_NODE_FK foreign key (NODE) references GRAPH_NODES (NAME); /* Заполняем таблицы */ insert into GRAPH_NODES (NAME) values ('A'); insert into GRAPH_NODES (NAME) values ('B'); insert into GRAPH_NODES (NAME) values ('C'); insert into GRAPH_NODES (NAME) values ('D'); insert into GRAPH_NODES (NAME) values ('E'); insert into GRAPH_NODES (NAME) values ('F'); insert into GRAPH_EDGES (NODE1 , NODE2 , WEIGHT) values ('A' , 'B' , 1); insert into GRAPH_EDGES (NODE1 , NODE2 , WEIGHT) values ('A' , 'C' , 5); insert into GRAPH_EDGES (NODE1 , NODE2 , WEIGHT) values ('B' , 'C' , 2); insert into GRAPH_EDGES (NODE1 , NODE2 , WEIGHT) values ('C' , 'D' , 7); insert into GRAPH_EDGES (NODE1 , NODE2 , WEIGHT) values ('C' , 'E' , 9); insert into GRAPH_EDGES (NODE1 , NODE2 , WEIGHT) values ('D' , 'E' , 3); insert into GRAPH_EDGES (NODE1 , NODE2 , WEIGHT) values ('D' , 'F' , 5); insert into GRAPH_EDGES (NODE1 , NODE2 , WEIGHT) values ('E' , 'F' , 5); commit; /* Подготоваливаем таблицу DEXTRA */ delete from DEXTRA; insert into DEXTRA select NAME NODE, 9999999999 WEIGHT from GRAPH_NODES; commit; /* Подготоваливаем начальную точку */ update DEXTRA set WEIGHT = 0 where NODE = 'A'; /* Заполняем таблицу DEXTRA (я это делал процедурой) */ DECLARE VARIABLE RESULT INTEGER; DECLARE VARIABLE NODE_NAME VARCHAR(5); DECLARE VARIABLE NODE_WEIGHT DECIMAL(10,0); begin   RESULT = 1;   while RESULT > 0 do   begin     RESULT = 0;     for select T3.NODE2 NODE, (T3.WEIGHT + T2.WEIGHT) WEIGHT         from DEXTRA T1, DEXTRA T2, GRAPH_EDGES T3         where T1.NODE = T3.NODE2 and T2.NODE = T3.NODE1 and T1.WEIGHT > (T3.WEIGHT + T2.WEIGHT)         into :NODE_NAME , :NODE_WEIGHT do     begin       update DEXTRA set WEIGHT = :NODE_WEIGHT where NODE = :NODE_NAME;       RESULT = RESULT + 1;     end   end end Теперь чтобы найти путь из начальной точки в заданную, выбираем для заданной точки соседнюю, так что есть ребро ведущее в эту точку если таких точек несколько, выбираем ту в которой WEIGHT минимально

Автор: Feliastre 30.3.2005, 10:35

Всё ниже сказанное сугубое ИМХО. Я тоже занимался приколами с графами. И долго думал, как же их хранить. Предложенный метод имеет один противный момент. Для 1000 вершин мы должны сделать 1 000 000 записей. Может для оракла это и быстро. Может для MS SQL 2000 это быстро. Для локальных баз - это погибель. Так что есть вариант. В базе хранить только "габариты" графа. А саму матрицу скидывать на хард. Для наглядности: У меня машина P4 2,4GHz, 768Mb RAM Запись того самого миллиона рёбер потребовала ~20 минут. БД юзал Парадокс, аксесс, InterBase. Если не страшны такие скорости - то я позорно замолкаю(типа со своим уставом в чужой монастырь...)

Автор: LSD 30.3.2005, 22:04

Цитата(Feliastre @ 30.3.2005, 10:35) Для 1000 вершин мы должны сделать 1 000 000 записей. Это верно для полного ориентированного графа, для не ориентированного это число меньше в половину. Но как правило графы не полные (иначе поиск пути на них задача тривиальная). Я попробовал забить в Firefox 1.5 полный неориентированный граф, 1000 вершин 500 000 ребер. На таблицах были foreign key и constrain. Вставка вершин заняла 0.5-1 сек, вставка ребер 3.5-5 мин. Машина: AthlonXP 2000, 768Mb RAM. Цитата(Feliastre @ 30.3.2005, 10:35) Так что есть вариант. В базе хранить только "габариты" графа. А саму матрицу скидывать на хард. А как работать с таким графом, тащить полностью в память? А целостность (отсутствие дубликатов ребер, некорректных ссылок и т.п.)?

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