pgr_edmondsKarp

pgr_edmondsKarp — Calcula el flujo en las aristas del grafo que maximiza el flujo de los orígenes a los destinos mediante el algoritmo de Push Relabel.

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad

  • 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

Soporte

  • Versiones sustentadas: actual(3.0)
  • Versiones no sustentadas:** 2.6 2.5 2.4 2.3

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ígenes, y un súper destino con aristas para todos los destinos.
  • 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: \(O( V * E ^ 2)\)

Firmas

Resumen

pgr_edmondsKarp(Edges SQL, source,  target)
pgr_edmondsKarp(Edges SQL, sources, target)
pgr_edmondsKarp(Edges SQL, source,  targets)
pgr_edmondsKarp(Edges SQL, sources, targets)
RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)
OR EMPTY SET

Uno a Uno

pgr_edmondsKarp(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_edmondsKarp(
    '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_edmondsKarp(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_edmondsKarp(
    '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_edmondsKarp(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_edmondsKarp(
    '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_edmondsKarp(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_edmondsKarp(
    '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)

Parámetros

Columna Tipo Valores predeterminados Descripción
Edges SQL TEXT   La consulta SQL de aristas como se describe en Inner Query.
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.

Consulta interna

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 (capacidad inversa) 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

Columnas de Resultados

Columna Tipo Descripción
seq INT Valor secuencial a partir de 1.
edge 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).