SQL - postgres - кратчайший путь в графе - рекурсия

Question

У меня есть таблица, которая содержит ребра от узла x до узла y в графе.

n1 | n2
-------
a  | a
a  | b
a  | c
b  | b
b  | d
b  | c
d  | e

Я хотел бы создать (материализованное) представление, которое обозначает наименьшее количество узлов / прыжков, которое содержит путь для достижения от x до узла y :

n1 | n2 | c
-----------
a  | a  | 0
a  | b  | 1
a  | c  | 1
a  | d  | 2
a  | e  | 3
b  | b  | 0
b  | d  | 1
b  | c  | 1
b  | e  | 2
d  | e  | 1

Как мне смоделировать мои таблицы и представления, чтобы облегчить это? Я предполагаю, что мне нужна какая-то рекурсия, но я считаю, что это довольно сложно сделать в SQL. Я хотел бы избежать того, что, например, клиенты должны запустить 10 запросов, если путь содержит 10 узлов / прыжков.

Answer 1

Это работает для меня, но довольно уродливо:

WITH RECURSIVE paths (n1, n2, distance) AS (
    SELECT
        nodes.n1,
        nodes.n2,
        1
    FROM
        nodes
    WHERE
        nodes.n1 <> nodes.n2

    UNION ALL

    SELECT
        paths.n1,
        nodes.n2,
        paths.distance + 1
    FROM
        paths
        JOIN nodes
        ON
            paths.n2 = nodes.n1
    WHERE
        nodes.n1 <> nodes.n2
)
SELECT
   paths.n1,
   paths.n2,
   min(distance)
FROM
    paths
GROUP BY
    1, 2

UNION

SELECT
    nodes.n1,
    nodes.n2,
    0
FROM
    nodes
WHERE
    nodes.n1 = nodes.n2

Кроме того, я не уверен, насколько хорошо он будет работать с большими наборами данных. Как предлагает Марк Манн, вы можете вместо этого использовать библиотеку графов, например, pygraph.

РЕДАКТИРОВАТЬ: вот образец с pygraph

from pygraph.algorithms.minmax import shortest_path
from pygraph.classes.digraph import digraph


g = digraph()

g.add_node('a')
g.add_node('b')
g.add_node('c')
g.add_node('d')
g.add_node('e')

g.add_edge(('a', 'a'))
g.add_edge(('a', 'b'))
g.add_edge(('a', 'c'))
g.add_edge(('b', 'b'))
g.add_edge(('b', 'd'))
g.add_edge(('b', 'c'))
g.add_edge(('d', 'e'))

for source in g.nodes():
    tree, distances = shortest_path(g, source)
    for target, distance in distances.iteritems():
        if distance == 0 and not g.has_edge((source, target)):
            continue
        print source, target, distance

Без учета времени построения графика это занимает 0,3 мс, а для версии SQL - 0,5 мс.

Answer 2

Расширяя ответ Марка, есть несколько очень разумных подходов для изучения графа в SQL.На самом деле они будут быстрее, чем выделенные библиотеки в perl или python, поскольку индексы БД избавят вас от необходимости исследовать график.

Самый эффективный из индексов (если график не меняется постоянно)) - это вариант вложенного дерева, называемый индекс GRIPP .(В связанном документе упоминаются другие подходы.)

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

Answer 3

Вместо того, чтобы вычислять эти значения на лету, почему бы не создать реальную таблицу со всеми интересными парами и кратчайшим значением пути.Затем, когда данные вставляются, удаляются или обновляются в вашей таблице данных, вы можете пересчитать всю информацию о кратчайшем пути.(Модуль Perl Graph особенно хорошо подходит для этой задачи, а интерфейс Perl DBI делает код простым.)

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