Determine los nodos en la red con PostgreSQL
Tengo una tabla donde cada entrada es un nodo y la tabla contiene las conexiones directas de cada nodo a otros nodos. Estoy buscando crear una vista con una columna para cada nodo que contenga todos los nodos de la cadena, no solo los nodos a los que está conectado el nodo.
Un ejemplo sería generar la columna Nodos en cadena a partir de las dos primeras columnas de la siguiente tabla:
CREATE TABLE example
(
node text,
connections text[],
nodes_in_chain text[]
)
INSERT INTO example VALUES
('a', ARRAY['a','b'], null),
('b', ARRAY['a','b','c','d'], null),
('c', ARRAY['b','c'], null),
('d', ARRAY['b','d'], null),
('e', ARRAY['e','f'], null),
('f', ARRAY['e','f'], null);
Node Connections Nodes in Chain
"a" "{a,b}" "{a,b,c,d}"
"b" "{a,b,c,d}" "{a,b,c,d}"
"c" "{b,c}" "{a,b,c,d}"
"d" "{b,d}" "{a,b,c,d}"
"e" "{e,f}" "{e,f}"
"f" "{e,f}" "{e,f}"
Esa es una pequeña versión simplificada del problema real. Si puedo resolver el ejemplo, la tabla completa no debería ser un problema.
Los datos de esta tabla se pueden visualizar de la siguiente forma:
He examinado varios métodos diferentes para resolver este problema. He examinado las CTE recursivas pero no he logrado que funcionen.
Cada nodo está conectado a sí mismo actualmente en la base de datos. No es un problema eliminar la conexión a sí mismo en la base de datos si es necesario.
Probablemente antecedentes innecesarios del problema :
El origen de este problema proviene de intentar identificar vehículos en el tráfico. La base de datos original contiene la ubicación y velocidad de los vehículos en cada paso de tiempo t en un área determinada. El objetivo es determinar el tiempo pasado en un semáforo. Para solucionar este problema se identificó una zona de parada para el semáforo. Se considera que cada vehículo en esta área con una velocidad por debajo de un cierto umbral está esperando el semáforo. Sin embargo, debido a la larga cola de espera, los vehículos pueden estar haciendo cola fuera de esta área. Por lo tanto, se hace una línea de tráfico ("Cadena de Nodos") con todos los vehículos que se encuentran dentro de una cierta distancia entre sí y tienen una velocidad baja por debajo. Partiendo de un vehículo dentro del área de cola identificada. El problema forma parte de la investigación científica sobre los tiempos de rodaje de las aeronaves. Por tanto, los vehículos son aeronaves y los semáforos son umbrales de pista.
Primero realicé el cálculo para identificar vehículos en un área con Python y pandas. Sin embargo, el código tardó 10 veces más en ejecutarse, lo que lo hizo prohibitivo para el proyecto. El código era muy simple sin bucles introducidos manualmente y, por lo tanto, no se podía acelerar (creo). También compararé la velocidad de ejecución del algoritmo de cola en Python versus PostgreSQL.
Respuestas
Enfoque 1:
A primera vista, parece que podría aplicar una solución básica porque, según sus datos de muestra, cada conexión individual está incluida en otra conexión.
SELECT
e1.node,
e1.connections,
COALESCE(e2.connections, e1.connections) nodes_in_chain
FROM
example e1
LEFT JOIN
example e2
ON e2.node <> e1.node
AND e1.connections <@ e2.connections;
nodo | conexiones | nodos_en_cadena
: --- | : ---------- | : -------------
a | {a, b} | {a B C D}
b | {a, b, c, d} | {a B C D}
c | {b, c} | {a B C D}
d | {b, d} | {a B C D}
e | {e, f} | {e, f}
f | {e, f} | {e, f}
Enfoque 2:
Pero, como señaló @ypercube , esta solución no funciona si hay 3 o más puntos lineales seguidos.
Ej: e -> f -> g -> h
Como referencia para resolver esta pregunta utilicé las respuestas en otra pregunta relacionada:
- Agrupación en cualquiera de las múltiples columnas en Postgres
Utiliza un método llamado cierre transitivo para resolver el problema.
Clausura transitiva
En matemáticas, el cierre transitivo de una relación binaria R en un conjunto X es la relación más pequeña en X que contiene R y es transitiva.
Por ejemplo, si X es un conjunto de aeropuertos y xRy significa "hay un vuelo directo desde el aeropuerto x al aeropuerto y" (para xey en X), entonces el cierre transitivo de R en X es la relación R + tal que x R + y significa "es posible volar de xay en uno o más vuelos". De manera informal, el cierre transitivo le brinda el conjunto de todos los lugares a los que puede llegar desde cualquier lugar de partida.
Primero déjeme cambiar sus datos de muestra agregando una conexión lineal de 4 nodos.
DELETE FROM example WHERE node = 'f';
INSERT INTO example VALUES
('f', ARRAY['e','f','g'], null),
('g', ARRAY['f','g','h'], null),
('h', ARRAY['g','h'], null);
Ahora aplicando las matemáticas:
WITH RECURSIVE al (dst, src) AS --adjacent list or list of all related nodes
(
SELECT e1.node, e2.node
FROM example e1
JOIN example e2
ON e1.node = any(e2.connections)
), tc (dst, src) AS
(
SELECT dst, src FROM al -- transitive closure
UNION
SELECT a1.dst, a2.src
FROM al as a1
JOIN tc as a2
ON a1.src = a2.dst
)
SELECT src, array_agg(DISTINCT dst ORDER BY dst) AS nodes_in_chain
FROM tc
GROUP BY src;
Danos este resultado:
src | nodes_in_chain
:-- | :-------------
a | {a,b,c,d}
b | {a,b,c,d}
c | {a,b,c,d}
d | {a,b,c,d}
e | {e,f,g,h}
f | {e,f,g,h}
g | {e,f,g,h}
h | {e,f,g,h}
db <> violín aquí
NOTA : La relación original tiene solo las conexiones inmediatas, que pueden verse como rutas de longitud 1 (2 nodos cada una). El Método 1 busca todas las rutas de longitud 2 (3 nodos) ya que aplica un método de conexión una vez. Para encontrar caminos de longitud N, debe aplicar los métodos N-1 veces. Para encontrar todas las rutas de longitudes arbitrarias (por desgracia, el cierre transitivo), necesita una solución recursiva o un bucle while. No se puede hacer con SQL simple. (es decir, una consulta sin CTE).
@ypercube