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.

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

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	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`).

Ver también¶

Índices y tablas