pgr_boykovKolmogorov
¶
pgr_boykovKolmogorov
— Calcula el flujo en las aristas del grafo que maximiza el flujo de las fuentes a los objetivos utilizando el algoritmo Boykov Kolmogorov.
Disponibilidad
Versión 3.2.0
Nueva firma propuesta
pgr_boykovKolmogorov
(Combinaciones)
Versión 3.0.0
Función oficial
Versión 2.5.0
Renombrado de
pgr_maxFlowBoykovKolmogorov
Función propuesta
Versión 2.3.0
Nueva función Experimental
Descripción¶
Las principales características son:
El grafo es dirigido.
El proceso se realiza sólo en aristas con capacidades positivas.
Cuando el flujo máximo es 0 entonces no hay flujo, se devolverá: EMPTY SET.
No hay ningún flujo cuando el orígen es el mismo que el destino.
Cualquier valor duplicado en el/los orígen(es) o en el/los destino(s) será ignorado.
Calcula la capacidad de flujo/residuo para cada arista. En la salida
Se omiten las aristas con flujo cero.
Crea una súper origen, con aristas para todos las fuentes(es), y un súper destino con aristas para todos los destino(s).
Se garantiza que el flujo máximo a través del grafo es el valor devuelto por pgr_maxFlow cuando es ejecutado con los mismos parámetros y se puede calcular:
Mediante la suma de los flujos salientes de las fuentes
Mediante la suma de los flujos llegantes a los destinos
Tiempo de ejecución: Polinomio
Firmas¶
Resumen
(seq, edge, start_vid, end_vid, flow, residual_capacity)
Uno a Uno¶
(seq, edge, start_vid, end_vid, flow, residual_capacity)
- Ejemplo:
Del vértice \(11\) al vértice \(12\)
SELECT * FROM pgr_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
11, 12);
seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
1 | 10 | 7 | 8 | 100 | 30
2 | 12 | 8 | 12 | 100 | 0
3 | 8 | 11 | 7 | 100 | 30
4 | 11 | 11 | 12 | 130 | 0
(4 rows)
Uno a Muchos¶
(seq, edge, start_vid, end_vid, flow, residual_capacity)
- Ejemplo:
Desde el vértice \(11\) a los vértices \(\{5, 10, 12\}\)
SELECT * FROM pgr_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
11, ARRAY[5, 10, 12]);
seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
1 | 1 | 6 | 5 | 50 | 80
2 | 4 | 7 | 6 | 50 | 0
3 | 10 | 7 | 8 | 80 | 50
4 | 12 | 8 | 12 | 80 | 20
5 | 8 | 11 | 7 | 130 | 0
6 | 11 | 11 | 12 | 130 | 0
7 | 9 | 11 | 16 | 80 | 50
8 | 3 | 15 | 10 | 80 | 50
9 | 16 | 16 | 15 | 80 | 0
(9 rows)
Muchos a Uno¶
(seq, edge, start_vid, end_vid, flow, residual_capacity)
- Ejemplo:
De los vértices vertices \(\{11, 3, 17\}\) al vértice \(12\)
SELECT * FROM pgr_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
ARRAY[11, 3, 17], 12);
seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
1 | 7 | 3 | 7 | 50 | 0
2 | 10 | 7 | 8 | 100 | 30
3 | 12 | 8 | 12 | 100 | 0
4 | 8 | 11 | 7 | 50 | 80
5 | 11 | 11 | 12 | 130 | 0
(5 rows)
Muchos a Muchos¶
(seq, edge, start_vid, end_vid, flow, residual_capacity)
- Ejemplo:
De los vértices \(\{11, 3, 17\}\) a los vértices \(\{5, 10, 12\}\)
SELECT * FROM pgr_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
ARRAY[11, 3, 17], ARRAY[5, 10, 12]);
seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
1 | 7 | 3 | 7 | 50 | 0
2 | 1 | 6 | 5 | 50 | 80
3 | 4 | 7 | 6 | 50 | 0
4 | 10 | 7 | 8 | 100 | 30
5 | 12 | 8 | 12 | 100 | 0
6 | 8 | 11 | 7 | 100 | 30
7 | 11 | 11 | 12 | 130 | 0
8 | 9 | 11 | 16 | 80 | 50
9 | 3 | 15 | 10 | 80 | 50
10 | 16 | 16 | 15 | 80 | 0
(10 rows)
Combinaciones¶
(seq, edge, start_vid, end_vid, flow, residual_capacity)
- Ejemplo:
Usando una tabla de combinaciones, equivalente a calcular el resultado de los vértices \(\{5, 6\}\) a los vértices \(\{10, 15, 14\}\).
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_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
'SELECT * FROM combinations WHERE target NOT IN (5, 6)');
seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
1 | 4 | 6 | 7 | 80 | 20
2 | 8 | 7 | 11 | 80 | 20
3 | 9 | 11 | 16 | 80 | 50
4 | 16 | 16 | 15 | 80 | 0
(4 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. |
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. |
|
|
ENTEROS |
Peso de la arista ( |
|
|
ENTEROS |
-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 salida. |
|
ENTEROS |
Identificador del vértice de llegada. |
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
Columnas de resultados¶
Columna |
Tipo |
Descripción |
---|---|---|
seq |
|
Valor secuencial a partir de 1. |
arista |
|
Identificador de la arista en la consulta original(edges_sql). |
start_vid |
|
Identificador del primer vértice de la arista. |
end_vid |
|
Identificador del segundo vértice de la arista. |
flujo |
|
Flujo a través del arista en la dirección ( |
residual_capacity |
|
Capacidad residual del arista en la dirección ( |
Ejemplos Adicionales¶
- Ejemplo:
Manualmente asignar combinaciones de vértices.
SELECT * FROM pgr_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
'SELECT * FROM (VALUES (5, 10), (6, 15), (6, 14)) AS t(source, target)');
seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
1 | 4 | 6 | 7 | 80 | 20
2 | 8 | 7 | 11 | 80 | 20
3 | 9 | 11 | 16 | 80 | 50
4 | 16 | 16 | 15 | 80 | 0
(4 rows)
Ver también¶
Índices y tablas