SQL - postgres - camino más corto en el gráfico - recursión

Question

I tiene una tabla que contiene los bordes de nodo x al nodo y en un gráfico.

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

Me gustaría crear un (materializada) vista que denota el menor número de nodos/saltos que un camino contiene acceso desde x al nodo 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 

¿Cómo debe ¿Modelar mis tablas y vistas para facilitar esto? Supongo que necesito algún tipo de recursión, pero creo que es bastante difícil de lograr en SQL. Me gustaría evitar eso, por ejemplo, los clientes deben disparar 10 consultas si la ruta contiene 10 nodos/saltos.

Answer 1

En lugar de calcular estos valores sobre la marcha, ¿por qué no crear una tabla real con todos los pares interesantes junto con el valor de ruta más corta? Luego, cuando se insertan, eliminan o actualizan datos en su tabla de datos, puede volver a calcular toda la información de ruta más corta. (El módulo Graph de Perl es especialmente adecuado para esta tarea, y la interfaz DBI de Perl simplifica el código.)

Al usar un proceso externo, también puede limitar el número de recálculos. El uso de desencadenantes de PostgreSQL provocará que se realicen nuevos cálculos en cada inserción, actualización y eliminación, pero si supiera que va a agregar veinte pares de puntos, podría esperar hasta completar los insertos antes de hacer los cálculos.

Answer 2

Esto funciona para mí, pero es un poco fea:

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 

Además, no estoy seguro de lo bien que se llevará a cabo en contra de grandes conjuntos de datos. Según lo sugerido por Mark Mann, es posible que desee utilizar una biblioteca de gráficos en su lugar, p. pygraph.

EDIT: he aquí una muestra con 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 

Excluyendo el tiempo de construcción gráfica, esto se lleva a 0.3ms mientras que la versión de SQL tarda 0,5 ms.

Answer 3

Expandiendo la respuesta de Mark, hay algunos enfoques muy razonables para explorar un gráfico en SQL también. De hecho, serán más rápidos que las bibliotecas dedicadas en Perl o Python, ya que los índices DB le ahorrarán la necesidad de explorar el gráfico.

El índice más eficiente (si el gráfico no cambia constantemente) es una variación de árbol anidado llamado GRIPP index. (El documento vinculado menciona otros enfoques)

Si su gráfico cambia constantemente, es posible que desee adaptar el enfoque nested intervals a los gráficos, de manera similar que GRIPP amplía conjuntos anidados, o simplemente usar flotantes en lugar de enteros (no te olvides de normalizarlos al convertir a numérico y de regreso a flotar si lo haces).