Поиск всех путей от точки до точки?

Question

[rmk]

Здравствуйте!


Есть следующая задача: найти все возможные пути от точки до точки на сетевом графе. Связей в графе ~200M, лежат в MySQL Percona.


Пытаюсь решить задачу с помощью MariaDB & OQGRAPH, но он либо показывает все узлы, в которые можно пойти из начальной точки (глубина = 1) latch=0 and origid=<x>, либо кратчайшуй путь между точками (latch=1|2 and origid=<x> and destid=<y>), либо все возможные пути из точки (latch=1 and origid=<x>).


Запрос на все возможные пути из точки (latch=1 and origid=<x>), в приципе, устраивал бы, если бы можно было ограничить пути путешествия по графу по точкам и глубине (с помощью linkid not in(x...) and weight=<z>, где <z> — всегда одинаковый для всех узлов), но у меня складывается ощущение, что при таком запросе происходит полный перебор графа, а фильтр применяется только на вывод результата.


Во-первых, хотел бы спросить у имеющих опыт работы с mariadb & oqgraph, применяется ли where (weight=<x> and linkid=<y>) во время прохода по графу, или просто фильтрует все данные после полного обхода?


Во-вторых, посоветуйте, пожалуйста, какие могут быть алтернативы данному решению? Нужна граф-ориентированная СУБД с алгоритмом поиска всех путей между точками.

Comments

[rmk]

Я забыл привести граничные условия организации графа, в связи с этим уточняю вопрос.

У нас есть 2 вида точек: А и В, где Qa/Qb = 1/10, A<-->B. Таким образом точки A связаны друг с другом через ограниченное количество точек B.

Пример графа:
As <--> B1 <--> Ad
B2 <-->

Пример запроса к графу:
Найти все возможные B, которые ведут от As до Ad.

На текущий момент это все успешно работает на MySQL Percona под XtraDB примерно так:
1) Получаем все B, которые имеет As.
2) Получаем все A, которые имеет соответствующие B кроме As.

На мой взгляд тут трудно найти более оптимальный алгоритм. Я ищу инструмент, который может это сделать быстрее, проще и прозрачнее.

Answer 1

[turboNOMAD]

Ваша задача на практике неразрешима — ни средствами СУБД, ни даже написанием программы, реализующей алгоритм.

Объясню почему. Давайте для простоты решим, что мы ищем только пути, не посещающие одну вершину более 1 раза — так называемые «простые» пути. Если не налагать это ограничение, то количество путей будет несравнимо больше, а при наличии в графе циклов — бесконечным.

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

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

Замечу, что при наложении на структуру графа некоторых строгих ограничений (например, не более 2 ребер, выходящих из каждой вершины) время работы поиска в глубину становится приемлемым — полиномиальная асимптотика вместо экспоненты. Но на практике такими графами дело, конечно же, не ограничивается.

Comments

[rmk]

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