• Versiones soportadas: Última (3.3) 3.2 3.1 3.0

• Versiones no soportadas: 2.6 2.5 2.4 2.3

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	TEXT	Edges SQL as described below
Combinations SQL	TEXT	Combinations SQL as described below
start vid	BIGINT	Identifier of the starting vertex of the path.
start vids	ARRAY[BIGINT]	Array of identifiers of starting vertices.
end vid	BIGINT	Identifier of the ending vertex of the path.
end vids	ARRAY[BIGINT]	Array of identifiers of ending vertices.

Consultas internas

SQL de aristas

Columna	Tipo	x Defecto	Descripción
id	ANY-INTEGER		Identificador de la arista.
source	ANY-INTEGER		Identificador del primer vértice extremo de la arista.
target	ANY-INTEGER		Identificador del segundo vértice extremo de la arista.
capacity	ANY-INTEGER		Weight of the edge (source, target)
reverse_capacity	ANY-INTEGER	-1	Weight of the edge (target, source) When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Combinaciones SQL

Parameter	Tipo	Descripción
source	ANY-INTEGER	Identifier of the departure vertex.
target	ANY-INTEGER	Identifier of the arrival vertex.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

Return Columns

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 vértice extremo de la arista.
end_vid	BIGINT	Identificador del segundo vértice extremo 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).

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

• Flow - Familia de funciones.

  • pgr_edmondsKarp

  • pgr_pushRelabel

• https://www.boost.org/libs/graph/doc/boykov_kolmogorov_max_flow.html

Índices y tablas

• Índice

• Página de Búsqueda