`pgr_edmondsKarp`¶

pgr_edmondsKarp — Calcula el flujo en las aristas del grafo que maximizan el flujo de las fuentes a los destinos usando el algoritmo de Edmonds Karp.

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

Disponibilidad

Versión 3.2.0
- Nueva función propuesta
  - pgr_edmondsKarp (Combinaciones)
Versión 3.0.0
- Función oficial
Versión 2.5.0
- Renombrado desde pgr_maxFlowEdmondsKarp
- 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: \(O( V * E ^ 2)\)

Firmas¶

Resumen

pgr_edmondsKarp(SQL de aristas, salida, destino)
pgr_edmondsKarp(SQL de aristas, salida, destinos)
pgr_edmondsKarp(SQL de aristas, salidas, destino)
pgr_edmondsKarp(SQL de aristas, salidas, destinos)
pgr_edmondsKarp(SQL de aristas, SQL de combinaciones)

RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)

OR EMPTY SET

Uno a Uno¶

pgr_edmondsKarp(SQL de aristas, salida, destino)

RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)

OR EMPTY SET

Ejemplo:: Del vértice \(11\) al vértice \(12\)

SELECT * FROM pgr_edmondsKarp(
  '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¶

pgr_edmondsKarp(SQL de aristas, salida, destinos)

RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)

OR EMPTY SET

Ejemplo:: Desde el vértice \(11\) a los vértices \(\{5, 10, 12\}\)

SELECT * FROM pgr_edmondsKarp(
  '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¶

pgr_edmondsKarp(SQL de aristas, salidas, destino)

RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)

OR EMPTY SET

Ejemplo:: De los vértices vertices \(\{11, 3, 17\}\) al vértice \(12\)

SELECT * FROM pgr_edmondsKarp(
  '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¶

pgr_edmondsKarp(SQL de aristas, salidas, destinos)

RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)

OR EMPTY SET

Ejemplo:: De los vértices \(\{11, 3, 17\}\) a los vértices \(\{5, 10, 12\}\)

SELECT * FROM pgr_edmondsKarp(
  '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¶

pgr_edmondsKarp(SQL de aristas, SQL de combinaciones)

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 \(\{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_edmondsKarp(
  '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	`TEXT`	SQL de aristas como se describe a continuación
SQL de combinaciones	`TEXT`	SQL de combinaciones como se describe a abajo
salida	`BIGINT`	Identificador del vértice inicial de la ruta.
salidas	`ARRAY[BIGINT]`	Arreglo de identificadores de vértices iniciales.
destino	`BIGINT`	Identificador del vértice final de la ruta.
destinos	`ARRAY[BIGINT]`	Arreglo de identificadores de vértices finales.

Consultas Internas¶

SQL aristas¶

Columna	Tipo	x Defecto	Descripción
`id`	ENTEROS		Identificador de la arista.
`source`	ENTEROS		Identificador del primer vértice de la arista.
`target`	ENTEROS		Identificador del segundo vértice de la arista.
`capacity`	ENTEROS		Peso de la arista (`source`, `target`)
`reverse_capacity`	ENTEROS	-1	Peso de la arista (`target`, `source`) Cuando negativo: la arista (`target`, `source`) no existe, por lo tanto no es parte del grafo.

Donde:

ENTEROS:: SMALLINT, INTEGER, BIGINT
FLOTANTES:: SMALLINT, INTEGER, BIGINT, REAL, FLOAT

SQL Combinaciones¶

Parámetro	Tipo	Descripción
`source`	ENTEROS	Identificador del vértice de salida.
`target`	ENTEROS	Identificador del vértice de llegada.

Donde:

ENTEROS:: SMALLINT, INTEGER, BIGINT

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 vértice de la arista.
`end_vid`	`BIGINT`	Identificador del segundo vértice de la arista.
flujo	`BIGINT`	Flujo a través del arista en la dirección (`start_vid`, `end_vid`).
residual_capacity	`BIGINT`	Capacidad residual del arista en la dirección (`start_vid`, `end_vid`).

Ejemplos Adicionales¶

Ejemplo:: Manualmente asignar combinaciones de vértices.

SELECT * FROM pgr_edmondsKarp(
  '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