pgr_maxFlow

pgr_maxFlow — Calcula el flujo máximo en un gráfico dirigido desde los orígene(s) a los destino(s) 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)
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

Valores predeterminados

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