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.

Boost Graph Inside¶
Availability
Versión 3.2.0
New proposed signature
pgr_boykovKolmogorov
(Combinations)
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 características principales 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 los orígen(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 agregación del flujo saliente de los orígenes
Mediante la agregación del flujo entrante a los destinos
Tiempo de ejecución: Polinomio
Firmas¶
Resumen
pgr_boykovKolmogorov(Edges SQL, start vid, end vid) pgr_boykovKolmogorov(Edges SQL, start vid, end vids) pgr_boykovKolmogorov(Edges SQL, start vids, end vid) pgr_boykovKolmogorov(Edges SQL, start vids, end vids) pgr_boykovKolmogorov(Edges SQL, Combinations SQL) RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity) OR EMPTY SET
Uno a Uno¶
pgr_boykovKolmogorov(Edges SQL, start vid, end vid) RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity) OR EMPTY SET
- Ejemplo
Del vértice \(6\) al vértice \(11\)
SELECT * FROM pgr_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edge_table',
6, 11);
seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
1 | 10 | 5 | 10 | 100 | 30
2 | 8 | 6 | 5 | 100 | 30
3 | 11 | 6 | 11 | 130 | 0
4 | 12 | 10 | 11 | 100 | 0
(4 rows)
Uno a Muchos¶
pgr_boykovKolmogorov(Edges SQL, start vid, end vids) RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity) OR EMPTY SET
- Ejemplo
Del vértice \(6\) a los vértices \(\{1, 3, 11\}\)
SELECT * FROM pgr_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edge_table',
6, ARRAY[1, 3, 11]);
seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
1 | 1 | 2 | 1 | 50 | 80
2 | 3 | 4 | 3 | 80 | 50
3 | 4 | 5 | 2 | 50 | 0
4 | 10 | 5 | 10 | 80 | 50
5 | 8 | 6 | 5 | 130 | 0
6 | 9 | 6 | 9 | 80 | 50
7 | 11 | 6 | 11 | 130 | 0
8 | 16 | 9 | 4 | 80 | 0
9 | 12 | 10 | 11 | 80 | 20
(9 rows)
Muchos a Uno¶
pgr_boykovKolmogorov(Edges SQL, start vids, end vid) RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity) OR EMPTY SET
- Ejemplo
De los vértices vertices \(\{6, 8, 12\}\) al vértice \(11\)
SELECT * FROM pgr_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edge_table',
ARRAY[6, 8, 12], 11);
seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
1 | 10 | 5 | 10 | 100 | 30
2 | 8 | 6 | 5 | 100 | 30
3 | 11 | 6 | 11 | 130 | 0
4 | 12 | 10 | 11 | 100 | 0
(4 rows)
Muchos a Muchos¶
pgr_boykovKolmogorov(Edges SQL, start vids, end vids) RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity) OR EMPTY SET
- Ejemplo
De los vértices \(\{6, 8, 12\}\) a los vértices \(\{1, 3, 11\}\)
SELECT * FROM pgr_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edge_table',
ARRAY[6, 8, 12], ARRAY[1, 3, 11]);
seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
1 | 1 | 2 | 1 | 50 | 80
2 | 3 | 4 | 3 | 80 | 50
3 | 4 | 5 | 2 | 50 | 0
4 | 10 | 5 | 10 | 100 | 30
5 | 8 | 6 | 5 | 130 | 0
6 | 9 | 6 | 9 | 80 | 50
7 | 11 | 6 | 11 | 130 | 0
8 | 7 | 8 | 5 | 20 | 30
9 | 16 | 9 | 4 | 80 | 0
10 | 12 | 10 | 11 | 100 | 0
(10 rows)
Combinaciones¶
pgr_boykovKolmogorov(Edges SQL, Combinations SQL) RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity) OR EMPTY SET
- Ejemplo
Using a combinations table, equivalent to calculating result from vertices \(\{1, 2\}\) to vertices \(\{3, 4, 17\}\).
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_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edge_table',
'SELECT * FROM combinations_table
WHERE target NOT IN (1, 2)');
seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
1 | 4 | 2 | 5 | 80 | 20
2 | 8 | 5 | 6 | 80 | 20
3 | 9 | 6 | 9 | 80 | 50
4 | 16 | 9 | 4 | 80 | 0
(4 rows)
Parámetros¶
Columna |
Tipo |
Descripción |
---|---|---|
|
Edges SQL as described below |
|
|
Combinations SQL as described below |
|
start vid |
|
Identifier of the starting vertex of the path. |
start vids |
|
Array of identifiers of starting vertices. |
end vid |
|
Identifier of the ending vertex of the path. |
end vids |
|
Array of identifiers of ending vertices. |
Consultas internas¶
SQL de aristas¶
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-INTEGER |
Weight of the edge ( |
|
|
ANY-INTEGER |
-1 |
Weight of the edge (
|
Donde:
- ANY-INTEGER
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERICAL
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Combinaciones SQL¶
Parameter |
Tipo |
Descripción |
---|---|---|
|
ANY-INTEGER |
Identifier of the departure vertex. |
|
ANY-INTEGER |
Identifier of the arrival vertex. |
Donde:
- ANY-INTEGER
SMALLINT
,INTEGER
,BIGINT
Return Columns¶
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 extremo de la arista. |
end_vid |
|
Identificador del segundo vértice extremo de la arista. |
flujo |
|
Flujo a través del arista en la dirección ( |
residual_capacity (capacidad residual) |
|
Capacidad residual del arista en la dirección ( |
Additional Examples¶
- Ejemplo
Manually assigned vertex combinations.
SELECT * FROM pgr_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edge_table',
'SELECT * FROM (VALUES (1, 3), (2, 4), (2, 17)) AS t(source, target)');
seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
1 | 4 | 2 | 5 | 80 | 20
2 | 8 | 5 | 6 | 80 | 20
3 | 9 | 6 | 9 | 80 | 50
4 | 16 | 9 | 4 | 80 | 0
(4 rows)
Ver también¶
Índices y tablas