Теория: хранение графа

А для чего, если не секртет? Решал подобную задачу, но у меня был поиск пути по карте 6х6км.

Задача связана с обработкой текстов. Больше пока рассказать не могу :)

Тогда не знаю :) Я просто бил карту на ровные части и на основе этого строил индексы для быстрого доступа к списку узлов по определённым координатам.

Использовать какую-нибудь объектно-ориентированную DB?

Тебе больше всего подойдет IBM DB2, версии Express-C (бесплатна, но закрыта) и обрабатывай рекурсивными запросами. Вроде в Postgres последней версии появилась рекурсия, но не пробовал, так что ничего сказать не могу.

MUMPS и хранит данные в виде дерева. Вот версия http://cns2.uni.edu/~okane/ что написал для себя один профессор. У него лежит в http://cns2.uni.edu/~okane/source/MUMPS-MDH/

Именно эту версию не проверял, но наша контора вообще далает все на MUMPSе, c десятками подключений. (под SQL на такие нагрузки пришлось бы изрядно помучиться с оптимизацией)

Из альтернативных могу еще предложить пощупать Oracle Berkley DB (не пугайтесь, оракл ее бесплатно раздает)

Ну, и если на джаве, то Perst Embedded Database

DB2 Express-C со своими несерьёзными ограничениями - детский лепет перед постгресом.

> Вроде в Postgres последней версии появилась рекурсия, но не пробовал, так что ничего сказать не могу.

RDBMS тут, имхо, совсем лишней будет.

TimesTen

Добрый. И что страшного? Всё по-моему, ложится в реляционную структуру и все задачи решаются хорошо.
Заводим две таблицы:
таблицу "узел" и таблицу "связь". В таблице узел хранятся:
id (код узла)
value (значение)

в таблице "связь" хранится:
left_id (меньший из двух кодов связанных узлов)
right_id (больший из двух кодов связанных узлов)

в каждой таблице строится индекс по каждому полю. Миллион записей - это, в общем-то, не так страшно. Соответственно, поиск:

select id from узел where value=:value

поиск всех соседей:

select right_id,value from связь where left_id=:id
union
select left_id,value from связь where right_id=:id
order by value desc

Но только нужно учесть специфику. Если к базе не будет интенсивного доступа одновременно на чтение и запись, может быть, лучше воспользоваться чем-то типа BerkleyDB (сам не пользовался, правда)

Медланная работа реляционных СУБД - это, в основном, плата за надёжность и параллельность доступа.

den73, такие схемы хранения я и видел (когда гуглил). Но тут есть одна проблема - миллион записей в первой таблице - это не страшно. А вот во второй что будет происходить? Если по 10-15 связей на узел))) Вот тут кошмар и начнется.

dizza, не доходит до меня, как к этой задаче рекурсию применить можно? Что она мне даст? Если можно, объясни.

Skynin, java отпадает (скорости не хватит). Berkeley DB не думаю, что подойдет. К одной базе будет обращаться несколько приложений, часто одновременно, кто-то на чтение, кто-то на запись. А у этой БД, как я понял, для работы только API интерфейс, для использования в одном приложении. MUMPS попробую поизучать, может, и подойдет.

nikolayd, TimesTen тоже попробую посмотреть.

Спасибо, что откликнулись:) Буду изучать вышепредложенное, и ждать еще варианты (на всякий пожарный:)

Если нужно искать именно связи с минимальным весом, то
эту связь можно вычислять при каждом обновлении БД и хранить в самой записи узла. Тогда таблица с 15 миллионами не отменится, но запросов к ней будет меньше.

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

Что ещё придумать? Есть базы с полями-массивами. Может быть, будет быстрее записать все связи в виде массива или даже в виде перечня кодов связанных узлов через запятую. Это нужно пробовать.

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

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

> Пробовать конечно буду, в понедельник начну работу.

отпишись плиз по результатам - поднятый вопрос довольно интересен.

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

Просто я ничерта не понял по задаче - по какому признаку тебе до узлов надо достучаться и зачем. У меня было просто - найти узлы в радиусе R по заданым координатам и присунуть к ним еще один - это одно. У тебя, подозреваю, совсем другое.

Гм.. Мастер-класс, ага.

Строим матрицу смежности, пишем её в двумерный массив, массив (половинку массива, граф же неориентированный ^^) пишем в файл, файл пишем в БД.

/me увернулся от всех летящих в него предметов и убежал.

А с матрицей смежности тоже идея) Буду экспериментировать, как что-то получится, отпишу :)

Если тебе задача позволяетт работать с матрицей смежности, то вот как её хранить можно. http://netlib.org/linalg/html_templates/node91.html Можно много вариций на эту тему придумать. По личному опыту могу посоветовать выделить диагональ в отдельный массив. Можно строки в отдельные массивы положить, если к скорости продега по матрице алгоритм не сильно критичен.

> Использовать какую-нибудь объектно-ориентированную DB?

Кстати, давно интересовался. А что есть из доступного для linux?

> Кстати, давно интересовался. А что есть из доступного для linux?

http://common-lisp.net/project/elephant/

Перед тем, как изучать MUMPS, прочти это:

http://thedailywtf.com/Articles/A_Case_of_the_MUMPS.aspx

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

Спасибо. А есть что-нибудь свободное для C++? По идее коммерческих должно быть много.

А почему бы не забить на бд и не хранить граф как граф - т.е. Node { Node * links[42]; }; ? Рёбра хранить отсортированными как надо. Единственное что не очевидно - поиск узла по ключу, но тут можно ещё индекс прикрутить (готовый или самописный контейнер). В тыщу строк можно уложиться, да ещё и с синхронизацией многопоточности.