pgr_edgeDisjointPaths¶
pgr_edgeDisjointPaths — Calcula las rutas de aristas desarticuladas entre dos grupos de vértices.
Adentro: Boost Graph¶
Disponibilidad
Versión 3.2.0
Nueva función propuesta:
pgr_edgeDisjointPaths(Combinaciones)
Versión 3.0.0
Función oficial
Versión 2.5.0
Función propuesta
Versión 2.3.0
Nueva función Experimental
Descripción¶
Calcula las rutas de aristas desarticuladas entre dos grupos de vértices. Utiliza algoritmos de flujo máximo subyacentes para calcular las rutas.
- Los principales características son:
Calcula las rutas de aristas desarticuladas entre dos grupos de vértices cualquiera.
Devuelve un conjunto vacío EMPTY SET cuando el origen y el destino son los mismos o no se puede llegar.
El gráfico puede dirigido o no.
Utiliza pgr_boykovKolmogorov para calcular las rutas.
Firmas¶
Resumen
directed])directed])directed])directed])(seq, path_id, path_seq, [start_vid,] [end_vid,] node, edge, cost, agg_cost)Uno a Uno¶
directed])(seq, path_id, path_seq, node, edge, cost, agg_cost)- Ejemplo:
Del vértice \(11\) al vértice \(12\)
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
11, 12);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 11 | 8 | 1 | 1
2 | 1 | 2 | 7 | 10 | 1 | 2
3 | 1 | 3 | 8 | 12 | 1 | 3
4 | 1 | 4 | 12 | -1 | 0 | 4
5 | 2 | 1 | 11 | 11 | 1 | 4
6 | 2 | 2 | 12 | -1 | 0 | 5
(6 rows)
Uno a Muchos¶
directed])(seq, path_id, path_seq, end_vid, node, edge, cost, agg_cost)- Ejemplo:
Desde el vértice \(11\) a los vértices \(\{5, 10, 12\}\)
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
11, ARRAY[5, 10, 12]);
seq | path_id | path_seq | end_vid | node | edge | cost | agg_cost
-----+---------+----------+---------+------+------+------+----------
1 | 1 | 1 | 5 | 11 | 8 | 1 | 1
2 | 1 | 2 | 5 | 7 | 4 | 1 | 2
3 | 1 | 3 | 5 | 6 | 1 | 1 | 3
4 | 1 | 4 | 5 | 5 | -1 | 0 | 4
5 | 2 | 1 | 10 | 11 | 9 | 1 | 4
6 | 2 | 2 | 10 | 16 | 16 | 1 | 5
7 | 2 | 3 | 10 | 15 | 3 | 1 | 6
8 | 2 | 4 | 10 | 10 | -1 | 0 | 7
9 | 3 | 1 | 12 | 11 | 8 | 1 | 7
10 | 3 | 2 | 12 | 7 | 10 | 1 | 8
11 | 3 | 3 | 12 | 8 | 12 | 1 | 9
12 | 3 | 4 | 12 | 12 | -1 | 0 | 10
13 | 4 | 1 | 12 | 11 | 11 | 1 | 10
14 | 4 | 2 | 12 | 12 | -1 | 0 | 11
(14 rows)
Muchos a Uno¶
directed])(seq, path_id, path_seq, start_vid, node, edge, cost, agg_cost)- Ejemplo:
De los vértices vertices \(\{11, 3, 17\}\) al vértice \(12\)
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
ARRAY[11, 3, 17], 12);
seq | path_id | path_seq | start_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+------+------+------+----------
1 | 1 | 1 | 3 | 3 | 7 | 1 | 1
2 | 1 | 2 | 3 | 7 | 8 | 1 | 2
3 | 1 | 3 | 3 | 11 | 11 | 1 | 3
4 | 1 | 4 | 3 | 12 | -1 | 0 | 4
5 | 2 | 1 | 11 | 11 | 8 | 1 | 4
6 | 2 | 2 | 11 | 7 | 10 | 1 | 5
7 | 2 | 3 | 11 | 8 | 12 | 1 | 6
8 | 2 | 4 | 11 | 12 | -1 | 0 | 7
9 | 3 | 1 | 11 | 11 | 11 | 1 | 7
10 | 3 | 2 | 11 | 12 | -1 | 0 | 8
11 | 4 | 1 | 17 | 17 | 15 | 1 | 8
12 | 4 | 2 | 17 | 16 | 9 | 1 | 9
13 | 4 | 3 | 17 | 11 | 11 | 1 | 10
14 | 4 | 4 | 17 | 12 | -1 | 0 | 11
(14 rows)
Muchos a Muchos¶
directed])(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- Ejemplo:
De los vértices \(\{11, 3, 17\}\) a los vértices \(\{5, 10, 12\}\)
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
ARRAY[11, 3, 17], ARRAY[5, 10, 12]);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 3 | 5 | 3 | 7 | 1 | 1
2 | 1 | 2 | 3 | 5 | 7 | 4 | 1 | 2
3 | 1 | 3 | 3 | 5 | 6 | 1 | 1 | 3
4 | 1 | 4 | 3 | 5 | 5 | -1 | 0 | 4
5 | 2 | 1 | 3 | 10 | 3 | 7 | 1 | 4
6 | 2 | 2 | 3 | 10 | 7 | 8 | 1 | 5
7 | 2 | 3 | 3 | 10 | 11 | 9 | 1 | 6
8 | 2 | 4 | 3 | 10 | 16 | 16 | 1 | 7
9 | 2 | 5 | 3 | 10 | 15 | 3 | 1 | 8
10 | 2 | 6 | 3 | 10 | 10 | -1 | 0 | 9
11 | 3 | 1 | 3 | 12 | 3 | 7 | 1 | 9
12 | 3 | 2 | 3 | 12 | 7 | 8 | 1 | 10
13 | 3 | 3 | 3 | 12 | 11 | 11 | 1 | 11
14 | 3 | 4 | 3 | 12 | 12 | -1 | 0 | 12
15 | 4 | 1 | 11 | 5 | 11 | 8 | 1 | 12
16 | 4 | 2 | 11 | 5 | 7 | 4 | 1 | 13
17 | 4 | 3 | 11 | 5 | 6 | 1 | 1 | 14
18 | 4 | 4 | 11 | 5 | 5 | -1 | 0 | 15
19 | 5 | 1 | 11 | 10 | 11 | 9 | 1 | 15
20 | 5 | 2 | 11 | 10 | 16 | 16 | 1 | 16
21 | 5 | 3 | 11 | 10 | 15 | 3 | 1 | 17
22 | 5 | 4 | 11 | 10 | 10 | -1 | 0 | 18
23 | 6 | 1 | 11 | 12 | 11 | 8 | 1 | 18
24 | 6 | 2 | 11 | 12 | 7 | 10 | 1 | 19
25 | 6 | 3 | 11 | 12 | 8 | 12 | 1 | 20
26 | 6 | 4 | 11 | 12 | 12 | -1 | 0 | 21
27 | 7 | 1 | 11 | 12 | 11 | 11 | 1 | 21
28 | 7 | 2 | 11 | 12 | 12 | -1 | 0 | 22
29 | 8 | 1 | 17 | 5 | 17 | 15 | 1 | 22
30 | 8 | 2 | 17 | 5 | 16 | 16 | 1 | 23
31 | 8 | 3 | 17 | 5 | 15 | 3 | 1 | 24
32 | 8 | 4 | 17 | 5 | 10 | 2 | 1 | 25
33 | 8 | 5 | 17 | 5 | 6 | 1 | 1 | 26
34 | 8 | 6 | 17 | 5 | 5 | -1 | 0 | 27
35 | 9 | 1 | 17 | 10 | 17 | 15 | 1 | 27
36 | 9 | 2 | 17 | 10 | 16 | 16 | 1 | 28
37 | 9 | 3 | 17 | 10 | 15 | 3 | 1 | 29
38 | 9 | 4 | 17 | 10 | 10 | -1 | 0 | 30
39 | 10 | 1 | 17 | 12 | 17 | 15 | 1 | 30
40 | 10 | 2 | 17 | 12 | 16 | 9 | 1 | 31
41 | 10 | 3 | 17 | 12 | 11 | 11 | 1 | 32
42 | 10 | 4 | 17 | 12 | 12 | -1 | 0 | 33
(42 rows)
Combinaciones¶
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- Ejemplo:
Usando una tabla de combinaciones, equivalente a calcular el resultado de los vértices \(\{5, 6\}\) a los vértices \(\{10, 15, 14\}\) en un grafo no dirigido.
La tabla de combinaciones:
SELECT source, target FROM combinations
WHERE target NOT IN (5, 6);
source | target
--------+--------
5 | 10
6 | 15
6 | 14
(3 rows)
La consulta:
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
'SELECT * FROM combinations WHERE target NOT IN (5, 6)',
directed => false);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 5 | 10 | 5 | 1 | 1 | 1
2 | 1 | 2 | 5 | 10 | 6 | 2 | -1 | 2
3 | 1 | 3 | 5 | 10 | 10 | -1 | 0 | 1
4 | 2 | 1 | 6 | 15 | 6 | 4 | 1 | 1
5 | 2 | 2 | 6 | 15 | 7 | 8 | 1 | 2
6 | 2 | 3 | 6 | 15 | 11 | 9 | 1 | 3
7 | 2 | 4 | 6 | 15 | 16 | 16 | 1 | 4
8 | 2 | 5 | 6 | 15 | 15 | -1 | 0 | 5
9 | 3 | 1 | 6 | 15 | 6 | 2 | -1 | 5
10 | 3 | 2 | 6 | 15 | 10 | 3 | -1 | 4
11 | 3 | 3 | 6 | 15 | 15 | -1 | 0 | 3
(11 rows)
Parámetros¶
Columna |
Tipo |
Descripción |
|---|---|---|
|
SQL de aristas como se describe a continuación |
|
|
SQL de combinaciones como se describe a abajo |
|
salida |
|
Identificador del vértice inicial de la ruta. |
salidas |
|
Arreglo de identificadores de vértices iniciales. |
destino |
|
Identificador del vértice final de la ruta. |
destinos |
|
Arreglo de identificadores de vértices finales. |
Parámetros opcionales¶
Columna |
Tipo |
x Defecto |
Descripción |
|---|---|---|---|
|
|
|
|
Consultas Internas¶
SQL aristas¶
Columna |
Tipo |
x Defecto |
Descripción |
|---|---|---|---|
|
ENTEROS |
Identificador de la arista. |
|
|
ENTEROS |
Identificador del primer vértice de la arista. |
|
|
ENTEROS |
Identificador del segundo vértice de la arista. |
|
|
FLOTANTES |
Peso de la arista ( |
|
|
FLOTANTES |
-1 |
Peso de la arista (
|
Donde:
- ENTEROS:
SMALLINT,INTEGER,BIGINT- FLOTANTES:
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
SQL Combinaciones¶
Parámetro |
Tipo |
Descripción |
|---|---|---|
|
ENTEROS |
Identificador del vértice de partida. |
|
ENTEROS |
Identificador del vértice de llegada. |
Donde:
- ENTEROS:
SMALLINT,INTEGER,BIGINT
Columnas de resultados¶
Conjunto de (seq, path_id, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
Columna |
Tipo |
Descripción |
|---|---|---|
|
|
Valor secuencial a partir de 1. |
|
|
Identificador del camino.
|
|
|
Posición relativa en la ruta. Tiene el valor 1 para el inicio de una ruta. |
|
|
Identificador del vértice inicial. Se devuelve cuando hay varias vetrices iniciales en la consulta. |
|
|
Identificador del vértice final. Se devuelve cuando hay varios vértices finales en la consulta. |
|
|
Identificador del nodo en la ruta de |
|
|
Identificador de la arista utilizado para ir del |
|
|
Costo para atravesar desde |
|
|
Costo agregado desde |
Ejemplos Adicionales¶
- Ejemplo:
Asignando manualmente las combinaciones de vértices en un grafo no dirigido.
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
'SELECT * FROM (VALUES (5, 10), (6, 15), (6, 14)) AS t(source, target)',
directed => false);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 5 | 10 | 5 | 1 | 1 | 1
2 | 1 | 2 | 5 | 10 | 6 | 2 | -1 | 2
3 | 1 | 3 | 5 | 10 | 10 | -1 | 0 | 1
4 | 2 | 1 | 6 | 15 | 6 | 4 | 1 | 1
5 | 2 | 2 | 6 | 15 | 7 | 8 | 1 | 2
6 | 2 | 3 | 6 | 15 | 11 | 9 | 1 | 3
7 | 2 | 4 | 6 | 15 | 16 | 16 | 1 | 4
8 | 2 | 5 | 6 | 15 | 15 | -1 | 0 | 5
9 | 3 | 1 | 6 | 15 | 6 | 2 | -1 | 5
10 | 3 | 2 | 6 | 15 | 10 | 3 | -1 | 4
11 | 3 | 3 | 6 | 15 | 15 | -1 | 0 | 3
(11 rows)
Ver también¶
Índices y tablas