Supported versions:

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.

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

Disponibilidad

Versión 3.2.0
- Nueva función propuesta:
  - pgr_maxFlow(Combinaciones)
Versión 3.0.0
- Función oficial
Versión 2.4.0
- Nueva función Propuesta

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)
pgr_maxFlow(Edges SQL, Combinations SQL) -- Proposed on v3.2
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)

Combinaciones¶

pgr_maxFlow(Edges SQL, Combinations SQL)
RETURNS BIGINT

Ejemplo: Usando una tabla de combinaciones, equivalente a calcular el resultado 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',
    'SELECT * FROM ( VALUES (6, 1), (8, 3), (12, 11), (8, 1) ) AS t(source, target)'
);
 pgr_maxflow
-------------
         360
(1 row)

Parámetros¶

Columna	Tipo	Descripción
Edges SQL	`TEXT`	Consulta de bordes como se describe en Consultas internas.
Combinaciones SQL	`TEXT`	Consultas de combinaciones como se describe en Consultas internas.
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.

Consultas internas¶

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

Combinaciones SQL: una consulta SQL que debe devolver un conjunto de filas con las siguientes columnas:

Columna	Tipo	Valores predeterminados	Descripción
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.

Donde:

ANY-INTEGER: SMALLINT, INTEGER, BIGINT

La función agrega los orígenes y los destinos, quita los duplicados y, a continuación, calcula el resultado de los vértices de origen resultantes a los vértices de destino.

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