SQL - postgres - shortest path in graph - recursion

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    pathsGROUP BY    1, 2UNIONSELECT    nodes.n1,    nodes.n2,    0FROM    nodesWHERE    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_pathfrom pygraph.classes.digraph import digraphg = 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.

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).

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.