SQL - postgres - shortest path in graph - recursion

Question

I have a table which contains the edges from node x to node y in a graph.

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

I would like to create a (materialized) view which denotes the shortest number of nodes/hops a path contains to reach from x to node 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

How should I model my tables and views to facilitate this? I guess I need some kind of recursion, but I believe that is pretty difficult to accomplish in SQL. I would like to avoid that, for example, the clients need to fire 10 queries if the path happens to contain 10 nodes/hops.

Answer 1

This works for me, but it's kinda ugly:

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

Also, I am not sure how good it will perform against larger datasets. As suggested by Mark Mann, you may want to use a graph library instead, e.g. pygraph.

EDIT: here's a sample with 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

Excluding the graph building time, this takes 0.3ms while the SQL version takes 0.5ms.

Answer 2

Expanding on Mark's answer, there are some very reasonable approaches to explore a graph in SQL as well. In fact, they'll be faster than the dedicated libraries in perl or python, in that DB indexes will spare you the need to explore the graph.

The most efficient of index (if the graph is not constantly changing) is a nested-tree variation called the GRIPP index. (The linked paper mentions other approaches.)

If your graph is constantly changing, you might want to adapt the nested intervals approach to graphs, in a similar manner that GRIPP extends nested sets, or to simply use floats instead of integers (don't forget to normalize them by casting to numeric and back to float if you do).

Answer 3

Rather than computing these values on the fly, why not create a real table with all interesting pairs along with the shortest path value. Then whenever data is inserted, deleted or updated in your data table, you can recalculate all of the shortest path information. (Perl's Graph module is particularly well-suited to this task, and Perl's DBI interface makes the code straightforward.)

By using an external process, you can also limit the number of recalculations. Using PostgreSQL triggers would cause recalculations to occur on every insert, update and delete, but if you knew you were going to be adding twenty pairs of points, you could wait until your inserts were completed before doing the calculations.