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.

_images/boost-inside.jpeg — Adentro: Boost Graph¶

Disponibilidad:

Versión 3.2.0
- Nueva función 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 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, source,  target)
pgr_boykovKolmogorov(Edges SQL, sources, target)
pgr_boykovKolmogorov(Edges SQL, source,  targets)
pgr_boykovKolmogorov(Edges SQL, sources, targets)
pgr_boykovKolmogorov(Edges SQL, Combinations SQL) -- Proposed on v3.2
RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)
OR EMPTY SET

Uno a Uno¶

pgr_boykovKolmogorov(Edges SQL, source,  target)
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, source,  targets)
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, sources,  target)
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, sources,  targets)
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: Usando una tabla de combinaciones, equivalente a calcular el resultado 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',
    'SELECT * FROM ( VALUES (6, 1), (8, 3), (12, 11), (8, 1) ) AS t(source, target)'
);
 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)

Parámetros¶

Columna	Tipo	Descripción
Edges SQL	`TEXT`	Consulta de bordes como se describe en Consultas internas.
Combinaciones SQL	`TEXT`	Consultas de combinaciones como se describe en Consultas internas.
origen	`BIGINT`	Identificador del vértice inicial del flujo.
orígenes	`ARRAY[BIGINT]`	Conjunto de identificadores de los vértices iniciales del flujo.
objetivo	`BIGINT`	Identificador del vértice final del flujo.
destinos	`ARRAY[BIGINT]`	Conjunto de identificadores de los vértices finales del flujo.

Consultas internas¶

Edges SQL: Consulta SQL de un grafo dirigido de capacidades, que debe devolver un conjunto de filas con las siguientes columnas:

Columna	Tipo	Valores predeterminados	Descripción
id	`ANY-INTEGER`		Identificador de la arista.
origen	`ANY-INTEGER`		Identificador del primer punto final en el vértice de la arista.
objetivo	`ANY-INTEGER`		Identificador del segundo punto final en el vértice de la arista.
capacidad	`ANY-INTEGER`		Peso de la arista (source, target) Cuando es negativo: la arista (source, target) no existe, por lo tanto no es parte del grafo.
reverse_capacity	`ANY-INTEGER`	-1	Peso de la arista (target, source), En caso negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ANY-INTEGER: SMALLINT, INTEGER, BIGINT

Combinaciones SQL: una consulta SQL que debe devolver un conjunto de filas con las siguientes columnas:

Columna	Tipo	Valores predeterminados	Descripción
origen	`ANY-INTEGER`		Identificador del primer punto final en el vértice de la arista.
objetivo	`ANY-INTEGER`		Identificador del segundo punto final en el vértice de la arista.

Donde:

ANY-INTEGER: SMALLINT, INTEGER, BIGINT

La función agrega los orígenes y los destinos, quita los duplicados y, a continuación, calcula el resultado de los vértices de origen resultantes a los vértices de destino.

Columnas de Resultados¶

Columna	Tipo	Descripción
seq	`INT`	Valor secuencial a partir de 1.
arista	`BIGINT`	Identificador de la arista en la consulta original(edges_sql).
start_vid	`BIGINT`	Identificador del primer punto final en el vértice de la arista.
end_vid	`BIGINT`	Identificador del segundo punto final en el vértice de la arista.
flujo	`BIGINT`	Flujo a través del arista en la dirección (`start_vid`, `end_vid`).
residual_capacity (capacidad residual)	`BIGINT`	Capacidad residual del arista en la dirección (`start_vid`, `end_vid`).

Ver también¶

Índices y tablas