pgr_maxFlow¶
pgr_maxFlow
— Calcula el flujo máximo en un gráfico dirigido desde los orígenes a los destinos mediante el algoritmo Push Relabel.

Adentro: Boost Graph¶
Disponibilidad
Versión 3.0.0
Función oficial
Versión 2.4.0
Nueva función Propuesta
Soporte
Descripción¶
Las características principales son:
El grafo es dirigido.
Calcula el flujo máximo desde source(s) a target(s).
Cuando el flujo máximo es 0, entonces no hay flujo y se devuelve 0.
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.
Use el algoritmo pgr_pushRelabel .
Tiempo de ejecución: \(O( V ^ 3)\)
Firmas¶
Resumen
pgr_maxFlow(Edges SQL, source, target)
pgr_maxFlow(Edges SQL, sources, target)
pgr_maxFlow(Edges SQL, source, targets)
pgr_maxFlow(Edges SQL, sources, targets)
RETURNS BIGINT
Uno a Uno¶
pgr_maxFlow(Edges SQL, source, target)
RETURNS BIGINT
- Ejemplo
Del vértice \(6\) al vértice \(11\)
SELECT * FROM pgr_maxFlow(
'SELECT id,
source,
target,
capacity,
reverse_capacity
FROM edge_table'
, 6, 11
);
pgr_maxflow
-------------
230
(1 row)
Uno a Muchos¶
pgr_maxFlow(Edges SQL, source, targets)
RETURNS BIGINT
- Ejemplo
Del vértice \(6\) a los vértices \(\{11, 1, 13\}\)
SELECT * FROM pgr_maxFlow(
'SELECT id,
source,
target,
capacity,
reverse_capacity
FROM edge_table'
, 6, ARRAY[11, 1, 13]
);
pgr_maxflow
-------------
340
(1 row)
Muchos a Uno¶
pgr_maxFlow(Edges SQL, sources, target)
RETURNS BIGINT
- Ejemplo
De los vértices vertices \(\{6, 8, 12\}\) al vértice \(11\)
SELECT * FROM pgr_maxFlow(
'SELECT id,
source,
target,
capacity,
reverse_capacity
FROM edge_table'
, ARRAY[6, 8, 12], 11
);
pgr_maxflow
-------------
230
(1 row)
Muchos a Muchos¶
pgr_maxFlow(Edges SQL, sources, targets)
RETURNS BIGINT
- Ejemplo
De los vértices \(\{6, 8, 12\}\) a los vértices \(\{1, 3, 11\}\)
SELECT * FROM pgr_maxFlow(
'SELECT id,
source,
target,
capacity,
reverse_capacity
FROM edge_table'
, ARRAY[6, 8, 12], ARRAY[1, 3, 11]
);
pgr_maxflow
-------------
360
(1 row)
Parámetros¶
Columna |
Tipo |
Valores predeterminados |
Descripción |
---|---|---|---|
Edges SQL |
|
La consulta SQL de aristas como se describe en Inner Query. |
|
origen |
|
Identificador del vértice inicial del flujo. |
|
orígenes |
|
Conjunto de identificadores de los vértices iniciales del flujo. |
|
objetivo |
|
Identificador del vértice final del flujo. |
|
destinos |
|
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 |
|
Identificador de la arista. |
|
origen |
|
Identificador del primer punto final en el vértice de la arista. |
|
objetivo |
|
Identificador del segundo punto final en el vértice de la arista. |
|
capacidad |
|
Peso de la arista (source, target)
|
|
reverse_capacity (capacidad inversa) |
|
-1 |
Peso de la arista (target, source),
|
Donde:
- ANY-INTEGER
SMALLINT, INTEGER, BIGINT
Columnas de Devoluciones¶
Tipo |
Descripción |
---|---|
|
Flujo máximo posible desde el/los orígen(es) hacia el/los destino(s) |