VPF::Хранение графа в базе данных - Форум программистов

Illuminaty

Дата 19.3.2005, 20:56 (ссылка)

(нет голосов)

Загрузка ...

/*Антон Захаров*/

Профиль
Группа: Комодератор
Сообщений: 1238
Регистрация: 19.3.2005
Где: Россия, Казань

Репутация: нет
Всего: 56

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

LSD

Дата 20.3.2005, 00:59 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 24
Всего: 538

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

--------------------

Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it.

Illuminaty

Дата 20.3.2005, 10:54 (ссылка)

(нет голосов)

Загрузка ...

/*Антон Захаров*/

Профиль
Группа: Комодератор
Сообщений: 1238
Регистрация: 19.3.2005
Где: Россия, Казань

Репутация: нет
Всего: 56

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

Над предложенной реализацией я думал уже smile

, но в силу заданного вопроса она показалась мне недостаточной. Понятно, что плясать надо от нее - слов нет...

LSD

Дата 21.3.2005, 20:19 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 24
Всего: 538

Внимание аттракцион!
Сейчас с помощью ловкости рук мы получим все не циклические пути из точки B! smile

Код

/* Создаем таблицы */
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 (ссылка)

(нет голосов)

Загрузка ...

/*Антон Захаров*/

Профиль
Группа: Комодератор
Сообщений: 1238
Регистрация: 19.3.2005
Где: Россия, Казань

Репутация: нет
Всего: 56

Да уж....
С Oracle не сталкивался, поэтому есть загадочные элементы smile

Причем много...
А база, скорее всего MySQL

Думал, что можно все решить хорошей реализацией, не зависящей от платформы

Это сообщение отредактировал(а) Illuminaty - 21.3.2005, 23:40

LSD

Дата 21.3.2005, 23:41 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 24
Всего: 538

Цитата(Illuminaty @ 21.3.2005, 23:36)

А база, скорее всего MySQL

Упс

А я с MySQL не знаком, а как у него с join-нами?

--------------------

Illuminaty

Дата 21.3.2005, 23:55 (ссылка)

(нет голосов)

Загрузка ...

/*Антон Захаров*/

Профиль
Группа: Комодератор
Сообщений: 1238
Регистрация: 19.3.2005
Где: Россия, Казань

Репутация: нет
Всего: 56

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

LSD

Дата 24.3.2005, 22:35 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 24
Всего: 538

ИМХО все должно быть ОК. Т.к. именно так граф представляется в математике (множество вершин и множество ребер) и соответсвенно все алгоритмы поиска пути в графе расчитанны именно на такое представление.
Вот например как можно реализовать алгоритм Дейкстры, это уже для 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 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 48
Регистрация: 17.11.2004

Репутация: нет
Всего: нет

Всё ниже сказанное сугубое ИМХО.

Я тоже занимался приколами с графами. И долго думал, как же их хранить. Предложенный метод имеет один противный момент. Для 1000 вершин мы должны сделать 1 000 000 записей. Может для оракла это и быстро. Может для MS SQL 2000 это быстро. Для локальных баз - это погибель. Так что есть вариант. В базе хранить только "габариты" графа. А саму матрицу скидывать на хард.

Для наглядности:
У меня машина P4 2,4GHz, 768Mb RAM
Запись того самого миллиона рёбер потребовала ~20 минут. БД юзал Парадокс, аксесс, InterBase. Если не страшны такие скорости - то я позорно замолкаю(типа со своим уставом в чужой монастырь...) smile

LSD

Дата 30.3.2005, 22:04 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 24
Всего: 538

Цитата(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)

Так что есть вариант. В базе хранить только "габариты" графа. А саму матрицу скидывать на хард.

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

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| СУБД, общие вопросы \| Следующая тема »