pgr_edgeDisjointPaths¶
pgr_edgeDisjointPaths — Calcula las rutas de aristas desarticuladas entre dos grupos de vértices.
Adentro: Boost Graph¶
Disponibilidad
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
Soporte
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.
Una a muchas, muchas a una, muchas a muchas, versiones que también son soportadas.
Utiliza pgr_boykovKolmogorov para calcular las rutas.
Firmas¶
Resumen
pgr_edgeDisjointPaths(Edges SQL, start_vid, end_vid)
pgr_edgeDisjointPaths(Edges SQL, start_vid, end_vid [, directed])
pgr_edgeDisjointPaths(Edges SQL, start_vid, end_vids [, directed])
pgr_edgeDisjointPaths(Edges SQL, start_vids, end_vid [, directed])
pgr_edgeDisjointPaths(Edges SQL, start_vids, end_vids [, directed])
RETURNS SET OF (seq, path_id, path_seq, [start_vid,] [end_vid,] node, edge, cost, agg_cost)
OR EMPTY SET
Uso de valores predeterminados
pgr_edgeDisjointPaths(Edges SQL, start_vid, end_vid)
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET
- Ejemplo
Del vértice \(3\) al vértice \(5\) en un grafo dirigido
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
3, 5
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 3 | 2 | 1 | 0
2 | 1 | 2 | 2 | 4 | 1 | 1
3 | 1 | 3 | 5 | -1 | 0 | 2
4 | 2 | 1 | 3 | 5 | 1 | 0
5 | 2 | 2 | 6 | 8 | 1 | 1
6 | 2 | 3 | 5 | -1 | 0 | 2
(6 rows)
Uno a Uno¶
pgr_edgeDisjointPaths(Edges SQL, start_vid, end_vid, directed)
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET
- Ejemplo
Del vértice \(3\) al vértice \(5\) en un grafo no dirigido
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
3, 5,
directed := false
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 3 | 2 | 1 | 0
2 | 1 | 2 | 2 | 4 | 1 | 1
3 | 1 | 3 | 5 | -1 | 0 | 2
4 | 2 | 1 | 3 | 3 | -1 | 0
5 | 2 | 2 | 4 | 16 | 1 | -1
6 | 2 | 3 | 9 | 9 | 1 | 0
7 | 2 | 4 | 6 | 8 | 1 | 1
8 | 2 | 5 | 5 | -1 | 0 | 2
9 | 3 | 1 | 3 | 5 | 1 | 0
10 | 3 | 2 | 6 | 11 | 1 | 1
11 | 3 | 3 | 11 | 12 | -1 | 2
12 | 3 | 4 | 10 | 10 | 1 | 1
13 | 3 | 5 | 5 | -1 | 0 | 2
(13 rows)
Uno a Muchos¶
pgr_edgeDisjointPaths(Edges SQL, start_vid, end_vids, directed)
RETURNS SET OF (seq, path_id, path_seq, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
- Ejemplo
Del vértice \(3\) a los vértices \(\{4, 5, 10\}\) en un grafo dirigido graph
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
3, ARRAY[4, 5, 10]
);
seq | path_id | path_seq | end_vid | node | edge | cost | agg_cost
-----+---------+----------+---------+------+------+------+----------
1 | 1 | 1 | 4 | 3 | 5 | 1 | 0
2 | 1 | 2 | 4 | 6 | 9 | 1 | 1
3 | 1 | 3 | 4 | 9 | 16 | 1 | 2
4 | 1 | 4 | 4 | 4 | -1 | 0 | 3
5 | 2 | 1 | 5 | 3 | 2 | 1 | 0
6 | 2 | 2 | 5 | 2 | 4 | 1 | 1
7 | 2 | 3 | 5 | 5 | -1 | 0 | 2
8 | 3 | 1 | 5 | 3 | 5 | 1 | 0
9 | 3 | 2 | 5 | 6 | 8 | 1 | 1
10 | 3 | 3 | 5 | 5 | -1 | 0 | 2
11 | 4 | 1 | 10 | 3 | 2 | 1 | 0
12 | 4 | 2 | 10 | 2 | 4 | 1 | 1
13 | 4 | 3 | 10 | 5 | 10 | 1 | 2
14 | 4 | 4 | 10 | 10 | -1 | 0 | 3
(14 rows)
Muchos a Uno¶
pgr_edgeDisjointPaths(Edges SQL, start_vids, end_vid, directed)
RETURNS SET OF (seq, path_id, path_seq, start_vid, node, edge, cost, agg_cost)
OR EMPTY SET
- Ejemplo
De los vértices \(\{3, 6\}\) al vértice \(5\) en un grafo dirigido
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[3, 6], 5
);
seq | path_id | path_seq | start_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+------+------+------+----------
1 | 1 | 1 | 0 | 3 | 2 | 1 | 0
2 | 1 | 2 | 0 | 2 | 4 | 1 | 1
3 | 1 | 3 | 0 | 5 | -1 | 0 | 2
4 | 2 | 1 | 1 | 3 | 5 | 1 | 0
5 | 2 | 2 | 1 | 6 | 8 | 1 | 1
6 | 2 | 3 | 1 | 5 | -1 | 0 | 2
7 | 3 | 1 | 2 | 6 | 8 | 1 | 0
8 | 3 | 2 | 2 | 5 | -1 | 0 | 1
9 | 4 | 1 | 3 | 6 | 9 | 1 | 0
10 | 4 | 2 | 3 | 9 | 16 | 1 | 1
11 | 4 | 3 | 3 | 4 | 3 | 1 | 2
12 | 4 | 4 | 3 | 3 | 2 | 1 | 3
13 | 4 | 5 | 3 | 2 | 4 | 1 | 4
14 | 4 | 6 | 3 | 5 | -1 | 0 | 5
(14 rows)
Muchos a Muchos¶
pgr_edgeDisjointPaths(Edges SQL, start_vids, end_vids, directed)
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
- Ejemplo
De los vértices \(\{3, 6\}\) a los vértices \(\{4, 5, 10\}\) en un grafo dirigido
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[3, 6], ARRAY[4, 5, 10]
);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 0 | 4 | 3 | 5 | 1 | 0
2 | 1 | 2 | 0 | 4 | 6 | 9 | 1 | 1
3 | 1 | 3 | 0 | 4 | 9 | 16 | 1 | 2
4 | 1 | 4 | 0 | 4 | 4 | -1 | 0 | 3
5 | 2 | 1 | 1 | 5 | 3 | 2 | 1 | 0
6 | 2 | 2 | 1 | 5 | 2 | 4 | 1 | 1
7 | 2 | 3 | 1 | 5 | 5 | -1 | 0 | 2
8 | 3 | 1 | 2 | 5 | 3 | 5 | 1 | 0
9 | 3 | 2 | 2 | 5 | 6 | 8 | 1 | 1
10 | 3 | 3 | 2 | 5 | 5 | -1 | 0 | 2
11 | 4 | 1 | 3 | 10 | 3 | 2 | 1 | 0
12 | 4 | 2 | 3 | 10 | 2 | 4 | 1 | 1
13 | 4 | 3 | 3 | 10 | 5 | 10 | 1 | 2
14 | 4 | 4 | 3 | 10 | 10 | -1 | 0 | 3
15 | 5 | 1 | 4 | 4 | 6 | 9 | 1 | 0
16 | 5 | 2 | 4 | 4 | 9 | 16 | 1 | 1
17 | 5 | 3 | 4 | 4 | 4 | -1 | 0 | 2
18 | 6 | 1 | 5 | 5 | 6 | 8 | 1 | 0
19 | 6 | 2 | 5 | 5 | 5 | -1 | 0 | 1
20 | 7 | 1 | 6 | 5 | 6 | 9 | 1 | 0
21 | 7 | 2 | 6 | 5 | 9 | 16 | 1 | 1
22 | 7 | 3 | 6 | 5 | 4 | 3 | 1 | 2
23 | 7 | 4 | 6 | 5 | 3 | 2 | 1 | 3
24 | 7 | 5 | 6 | 5 | 2 | 4 | 1 | 4
25 | 7 | 6 | 6 | 5 | 5 | -1 | 0 | 5
26 | 8 | 1 | 7 | 10 | 6 | 8 | 1 | 0
27 | 8 | 2 | 7 | 10 | 5 | 10 | 1 | 1
28 | 8 | 3 | 7 | 10 | 10 | -1 | 0 | 2
(28 rows)
Parámetros¶
Parámetro |
Tipo |
Valores predeterminados |
Descripción |
|---|---|---|---|
edges_sql |
|
Consulta SQL interna como se describe a continuación. |
|
start_vid |
|
Identificador del vértice inicial de la ruta. |
|
start_vids |
|
Arreglo de identificadores de vértices iniciales. |
|
end_vid |
|
Identificador del vértice final de la ruta. |
|
end_vids |
|
Arreglo de identificadores de vértices finales. |
|
dirigido |
|
|
|
Consulta interna¶
Columna |
Tipo |
Valores predeterminados |
Descripción |
|---|---|---|---|
id |
|
Identificador de la arista. |
|
origen |
|
Identificador del primer punto final en el vértice de la arista. |
|
objetivo |
|
Identificador del segundo punto final en el vértice de la arista. |
|
costo |
|
Peso de la arista (source, target)
|
|
reverse_cost |
|
-1 |
Peso de la arista (target, source),
|
Donde:
- ANY-INTEGER
SMALLINT, INTEGER, BIGINT
- ANY-NUMERICAL
SMALLINT, INTEGER, BIGINT, REAL, FLOAT
Columnas de Devoluciones¶
Devuelve el conjunto de (seq, path_id, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
Columna |
Tipo |
Descripción |
|---|---|---|
seq |
|
Valor secuencial a partir de 1. |
path_id |
|
Identificador de ruta. Tiene el valor 1 para el primero de una ruta. Se utiliza cuando hay varias rutas para la misma combinación de |
path_seq |
|
Posición relativa en la ruta. Tiene el valor 1 para el principio de una ruta. |
start_vid |
|
Identificador del vértice inicial. Se devuelve cuando hay varias vetrices iniciales en la consulta. |
end_vid |
|
Identificador del vértice final. Se devuelve cuando hay varios vértices finales en la consulta. |
nodo |
|
Identificador del nodo en la ruta de |
arista |
|
Identificador del borde utilizado para ir del |
costo |
|
Costo de desplazamiento desde |
agg_cost |
|
Coste agregado de |