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.
Disponibilidad
- Versión 3.0.0
- Versión 2.4.0
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 |
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 Devoluciones
Tipo |
Descripción |
BIGINT |
Flujo máximo posible desde el/los orígen(es) hacia el/los destino(s) |
Ver también
Índices y tablas