pgr_edgeDisjointPaths¶
pgr_edgeDisjointPaths — Calcula las rutas de aristas desarticuladas entre dos grupos de vértices.
Boost Graph Inside¶
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
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]) pgr_edgeDisjointPaths(Edges SQL, Combinations SQL [, directed]) RETURNS SET OF (seq, path_id, path_seq, [start_vid,] [end_vid,] node, edge, cost, agg_cost) OR EMPTY SET
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
From vertex \(6\) to vertex \(11\)
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edge_table',
6, 11);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 6 | 8 | 1 | 0
2 | 1 | 2 | 5 | 10 | 1 | 1
3 | 1 | 3 | 10 | 12 | 1 | 2
4 | 1 | 4 | 11 | -1 | 0 | 3
5 | 2 | 1 | 6 | 11 | 1 | 0
6 | 2 | 2 | 11 | -1 | 0 | 1
(6 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
From vertex \(6\) to vertices \(\{1, 3, 11\}\)
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edge_table',
6, ARRAY[1, 3, 11]);
seq | path_id | path_seq | end_vid | node | edge | cost | agg_cost
-----+---------+----------+---------+------+------+------+----------
1 | 1 | 1 | 1 | 6 | 8 | 1 | 0
2 | 1 | 2 | 1 | 5 | 4 | 1 | 1
3 | 1 | 3 | 1 | 2 | 1 | 1 | 2
4 | 1 | 4 | 1 | 1 | -1 | 0 | 3
5 | 2 | 1 | 3 | 6 | 9 | 1 | 0
6 | 2 | 2 | 3 | 9 | 16 | 1 | 1
7 | 2 | 3 | 3 | 4 | 3 | 1 | 2
8 | 2 | 4 | 3 | 3 | -1 | 0 | 3
9 | 3 | 1 | 11 | 6 | 8 | 1 | 0
10 | 3 | 2 | 11 | 5 | 10 | 1 | 1
11 | 3 | 3 | 11 | 10 | 12 | 1 | 2
12 | 3 | 4 | 11 | 11 | -1 | 0 | 3
13 | 4 | 1 | 11 | 6 | 11 | 1 | 0
14 | 4 | 2 | 11 | 11 | -1 | 0 | 1
(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
From vertices \(\{6, 8, 12\}\) to vertex \(11\)
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edge_table',
ARRAY[6, 8, 12], 11);
seq | path_id | path_seq | start_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+------+------+------+----------
1 | 1 | 1 | 6 | 6 | 8 | 1 | 0
2 | 1 | 2 | 6 | 5 | 10 | 1 | 1
3 | 1 | 3 | 6 | 10 | 12 | 1 | 2
4 | 1 | 4 | 6 | 11 | -1 | 0 | 3
5 | 2 | 1 | 6 | 6 | 11 | 1 | 0
6 | 2 | 2 | 6 | 11 | -1 | 0 | 1
7 | 3 | 1 | 8 | 8 | 7 | 1 | 0
8 | 3 | 2 | 8 | 5 | 8 | 1 | 1
9 | 3 | 3 | 8 | 6 | 11 | 1 | 2
10 | 3 | 4 | 8 | 11 | -1 | 0 | 3
11 | 4 | 1 | 12 | 12 | 15 | 1 | 0
12 | 4 | 2 | 12 | 9 | 9 | 1 | 1
13 | 4 | 3 | 12 | 6 | 11 | 1 | 2
14 | 4 | 4 | 12 | 11 | -1 | 0 | 3
(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
From vertices \(\{6, 8, 12\}\) to vertices \(\{1, 3, 11\}\)
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edge_table',
ARRAY[6, 8, 12], ARRAY[1, 3, 11]);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 6 | 1 | 6 | 8 | 1 | 0
2 | 1 | 2 | 6 | 1 | 5 | 4 | 1 | 1
3 | 1 | 3 | 6 | 1 | 2 | 1 | 1 | 2
4 | 1 | 4 | 6 | 1 | 1 | -1 | 0 | 3
5 | 2 | 1 | 6 | 3 | 6 | 9 | 1 | 0
6 | 2 | 2 | 6 | 3 | 9 | 16 | 1 | 1
7 | 2 | 3 | 6 | 3 | 4 | 3 | 1 | 2
8 | 2 | 4 | 6 | 3 | 3 | -1 | 0 | 3
9 | 3 | 1 | 6 | 11 | 6 | 8 | 1 | 0
10 | 3 | 2 | 6 | 11 | 5 | 10 | 1 | 1
11 | 3 | 3 | 6 | 11 | 10 | 12 | 1 | 2
12 | 3 | 4 | 6 | 11 | 11 | -1 | 0 | 3
13 | 4 | 1 | 6 | 11 | 6 | 11 | 1 | 0
14 | 4 | 2 | 6 | 11 | 11 | -1 | 0 | 1
15 | 5 | 1 | 8 | 1 | 8 | 7 | 1 | 0
16 | 5 | 2 | 8 | 1 | 5 | 4 | 1 | 1
17 | 5 | 3 | 8 | 1 | 2 | 1 | 1 | 2
18 | 5 | 4 | 8 | 1 | 1 | -1 | 0 | 3
19 | 6 | 1 | 8 | 3 | 8 | 7 | 1 | 0
20 | 6 | 2 | 8 | 3 | 5 | 8 | 1 | 1
21 | 6 | 3 | 8 | 3 | 6 | 9 | 1 | 2
22 | 6 | 4 | 8 | 3 | 9 | 16 | 1 | 3
23 | 6 | 5 | 8 | 3 | 4 | 3 | 1 | 4
24 | 6 | 6 | 8 | 3 | 3 | -1 | 0 | 5
25 | 7 | 1 | 8 | 11 | 8 | 7 | 1 | 0
26 | 7 | 2 | 8 | 11 | 5 | 8 | 1 | 1
27 | 7 | 3 | 8 | 11 | 6 | 11 | 1 | 2
28 | 7 | 4 | 8 | 11 | 11 | -1 | 0 | 3
29 | 8 | 1 | 12 | 1 | 12 | 15 | 1 | 0
30 | 8 | 2 | 12 | 1 | 9 | 9 | 1 | 1
31 | 8 | 3 | 12 | 1 | 6 | 8 | 1 | 2
32 | 8 | 4 | 12 | 1 | 5 | 4 | 1 | 3
33 | 8 | 5 | 12 | 1 | 2 | 1 | 1 | 4
34 | 8 | 6 | 12 | 1 | 1 | -1 | 0 | 5
35 | 9 | 1 | 12 | 3 | 12 | 15 | 1 | 0
36 | 9 | 2 | 12 | 3 | 9 | 16 | 1 | 1
37 | 9 | 3 | 12 | 3 | 4 | 3 | 1 | 2
38 | 9 | 4 | 12 | 3 | 3 | -1 | 0 | 3
39 | 10 | 1 | 12 | 11 | 12 | 15 | 1 | 0
40 | 10 | 2 | 12 | 11 | 9 | 9 | 1 | 1
41 | 10 | 3 | 12 | 11 | 6 | 11 | 1 | 2
42 | 10 | 4 | 12 | 11 | 11 | -1 | 0 | 3
(42 rows)
Combinaciones¶
pgr_edgeDisjointPaths(Edges SQL, Combinations SQL [, directed]) RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost) OR EMPTY SET
- Ejemplo
Using a combinations table, equivalent to calculating result from vertices \(\{1, 2\}\) to vertices \(\{3, 4, 17\}\) on an undirected graph.
The combinations table:
SELECT source, target FROM combinations_table
WHERE target NOT IN (1, 2);
source | target
--------+--------
1 | 3
2 | 4
2 | 17
(3 rows)
The query:
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edge_table',
'SELECT * FROM combinations_table
WHERE target NOT IN (1, 2)',
directed => false);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 1 | 3 | 1 | 1 | 1 | 0
2 | 1 | 2 | 1 | 3 | 2 | 2 | -1 | 1
3 | 1 | 3 | 1 | 3 | 3 | -1 | 0 | 0
4 | 2 | 1 | 2 | 4 | 2 | 2 | -1 | 0
5 | 2 | 2 | 2 | 4 | 3 | 3 | -1 | -1
6 | 2 | 3 | 2 | 4 | 4 | -1 | 0 | -2
7 | 3 | 1 | 2 | 4 | 2 | 4 | 1 | 0
8 | 3 | 2 | 2 | 4 | 5 | 8 | 1 | 1
9 | 3 | 3 | 2 | 4 | 6 | 9 | 1 | 2
10 | 3 | 4 | 2 | 4 | 9 | 16 | 1 | 3
11 | 3 | 5 | 2 | 4 | 4 | -1 | 0 | 4
(11 rows)
Parámetros¶
Columna |
Tipo |
Descripción |
|---|---|---|
|
Edges SQL as described below |
|
|
Combinations SQL as described below |
|
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. |
Optional parameters¶
Columna |
Tipo |
default |
Descripción |
|---|---|---|---|
|
|
|
|
Consultas internas¶
Edges SQL¶
Columna |
Tipo |
x Defecto |
Descripción |
|---|---|---|---|
|
ANY-INTEGER |
Identificador de la arista. |
|
|
ANY-INTEGER |
Identificador del primer vértice extremo de la arista. |
|
|
ANY-INTEGER |
Identificador del segundo vértice extremo de la arista. |
|
|
ANY-NUMERICAL |
Weight of the edge ( |
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Donde:
- ANY-INTEGER
SMALLINT,INTEGER,BIGINT- ANY-NUMERICAL
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
Combinaciones SQL¶
Parámetro |
Tipo |
Descripción |
|---|---|---|
|
ANY-INTEGER |
Identifier of the departure vertex. |
|
ANY-INTEGER |
Identifier of the arrival vertex. |
Donde:
- ANY-INTEGER
SMALLINT,INTEGER,BIGINT
Columnas de Devoluciones¶
Set of (seq, path_id, path_seq [, start_vid] [, end_vid], node, edge, cost,
agg_cost)
Columna |
Tipo |
Descripción |
|---|---|---|
|
|
Valor secuencial a partir de 1. |
|
|
Path identifier.
|
|
|
Posición relativa en la ruta. Tiene el valor 1 para el principio 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 |
|
|
Identifier of the edge used to go from |
|
|
Costo del desplazamiento desde |
|
|
Aggregate cost from |
Additional Examples¶
- Ejemplo
Manually assigned vertex combinations on an undirected graph.
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edge_table',
'SELECT * FROM (VALUES (1, 3), (2, 4), (2, 17)) AS t(source, target)',
directed => false);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 1 | 3 | 1 | 1 | 1 | 0
2 | 1 | 2 | 1 | 3 | 2 | 2 | -1 | 1
3 | 1 | 3 | 1 | 3 | 3 | -1 | 0 | 0
4 | 2 | 1 | 2 | 4 | 2 | 2 | -1 | 0
5 | 2 | 2 | 2 | 4 | 3 | 3 | -1 | -1
6 | 2 | 3 | 2 | 4 | 4 | -1 | 0 | -2
7 | 3 | 1 | 2 | 4 | 2 | 4 | 1 | 0
8 | 3 | 2 | 2 | 4 | 5 | 8 | 1 | 1
9 | 3 | 3 | 2 | 4 | 6 | 9 | 1 | 2
10 | 3 | 4 | 2 | 4 | 9 | 16 | 1 | 3
11 | 3 | 5 | 2 | 4 | 4 | -1 | 0 | 4
(11 rows)
Ver también¶
Índices y tablas