Меню
Что нового?

Хранение и работа с графом

jenia

Новичок
Хранение и работа с графом

Возникла проблема с хранением и работой с графом.
Структура такая: таблица данных (spr), таблица вершин (spr_razd), таблица связей (spr_svz). Не могу никак решить по какому алгоритму таблицу вершин составить: пробовал по NESTED SETS - не понравилось то, что при вытягивании пути для вершины приходится делать аж три запроса; пробовал Adjacency List - не нравится то, что нужно рекурсию делать при вытягивании пути.
Уровень вложенности небольшой - до 5-6 уровней.
Требования: вывод пути к вершине, вывод непосредственных детей, вывод всех детей.
Подскажите пожалуйста, какой алгоритм хранения выбрать.
 

Popoff

popoff.donetsk.ua
jenia
Так граф или всё-таки дерево?

Во вложенных множествах для получения пути от корня к любой вершине достаточно одного запроса.
 

jenia

Новичок
Граф. Но в таблице вершин, как я понимаю, нужно хранить не только информацию о вершине, но и связи между вершинами. А в таблице с данными нужно хранить связи вершин с данными. Или я неправильно понимаю?

-~{}~ 18.07.06 03:09:

Если хранить в таблице связей все связи - и связи между вершинами, и связи с данными, то я вообще не понимаю, как можно делать выборку допустим для пути к вершине.
 

Popoff

popoff.donetsk.ua
Вложенные множества используются исключительно для хранения деревьев и для хранения графов в общем случае не годятся. Списки смежностей Вы можете использовать как для хранения графов в общем случае, так и для хранения деревьев в частности.

Таблица вершин - это и есть таблица данных. Собственно, вершина - это данное.

А связи хранятся в таблице связей.
 

jenia

Новичок
Чего-то я не понимаю. В одной таблице хранятся данные (основные данные, а не вершины), а в двух других - граф. Одна из этих двух - таблица связей, а вторая - таблица вершин. Правильно?
 

Popoff

popoff.donetsk.ua
jenia
что хранится в таблице вершин? какие в этой таблице столбцы? что такое "вершина"? это число?
 

jenia

Новичок
Таблица вершин в моём случае - это разделы справочника (id раздела, его название, id родителя ).
Таблица данных - это данные справочника (название и описание товара).
Таблица связей - связь между предыдущими двумя таблицами (поле с id раздела и поле с id описания товара).
 

jenia

Новичок
Один и тот же товар может находится в двух-трёх группах. Это можно сделать без графа?

-~{}~ 18.07.06 15:24:

Может я что-то не так спросил? Или никто не разбирается в этой тематике?
Спросил я не просто так, сначала статей десять прочитал по хранению графов в БД, но так и не разобрался.
 

jenia

Новичок
Я так и реализую. В таблице связей должны находится все связи или только связи товар-группа?
 

jenia

Новичок
А группы как должны быть связаны друг с другом? Наверное таблица групп должна быть организована по какому-нибудь алгоритму? Например NESTED SETS или Adjacency List или ещё какой-нибудь. Вот я и прошу, чтобы мне посоветовали алгоритм для организации таблицы групп в данном графе.
Требования: вывод пути к вершине, вывод непосредственных детей, вывод всех детей. Вложенность - не более 6 (в основном 2-3).

-~{}~ 18.07.06 16:50:

Я работал и с Nested Sets и Adjacency List, но не при построении графа, а при построении дерева. Проблема в том, что при работе с графом я не могу найти путь к вершине меньше чем тремя запросами. Я считаю, что это многовато.
 

Popoff

popoff.donetsk.ua
jenia
Если в графе есть одна вершина с нулевой полустепенью захода, все остальные вершины - с единичной полустепенью захода, и в этом графе нет циклов, то это - частный вид графа, который называется словом "дерево".

То, что Вы называете словом "граф", является не графом в общем случае, а его частным видом - деревом.

Если Вы не знаете, что такое полустепень захода и что является циклом в графе, то не говорите слово "граф" до того, как изучите этот вопрос.
 

jenia

Новичок
Автор оригинала: Popoff
jenia
Если в графе есть одна вершина с нулевой полустепенью захода, все остальные вершины - с единичной полустепенью захода, и в этом графе нет циклов, то это - частный вид графа, который называется словом "дерево".

То, что Вы называете словом "граф", является не графом в общем случае, а его частным видом - деревом.

Если Вы не знаете, что такое полустепень захода и что является циклом в графе, то не говорите слово "граф" до того, как изучите этот вопрос.
Нажмите для раскрытия...
Я конечно не силён в теории графов. Но вы хотите сказать, что структура в которой у вершины есть несколько родителей, не является графом? А является деревом?

-~{}~ 18.07.06 18:12:

Popoff
А вообще называйте как хотите. У меня есть задача, которую я стараюсь решить, но не получается. Поэтому обратился на форум. Если можете, то подскажите по существу.

-~{}~ 21.07.06 04:23:

Я не решился только с одним вопросом: наиболее часто мне будет приходится вытягивать путь от корня и поддерево. Я склоняюсь, что данные в таблице узлов надо хранить по алгоритму NESTED SETS. Но реализовал как NESTED SETS так и Adjacency List. Какую реализацию выбрать?
 
Войдите или зарегистрируйтесь для ответа.
Сверху