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.0.0
    • Función oficial
  • Versión 2.4.0
    • Nueva función Propuesta

Soporte

  • Versiones soportadas: actual(3.0)
  • Versiones no soportadas: 2.6 2.5 2.4

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)