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

  • Versión 3.0.0

    • Función oficial

  • Versión 2.4.0

    • Nueva función Propuesta

Descripción

Las principales características 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(SQL de aristas, salida , destino)
pgr_maxFlow(SQL de aristas, salida , destinos)
pgr_maxFlow(SQL de aristas, salidas , destino)
pgr_maxFlow(SQL de aristas, salidas , destinos)
pgr_maxFlow(SQL de aristas, SQL de combinaciones)
RETURNS BIGINT

Uno a Uno

pgr_maxFlow(SQL de aristas, salida , destino)
RETURNS BIGINT
Ejemplo:

Del vértice \(11\) al vértice \(12\)

SELECT * FROM pgr_maxFlow(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  11, 12);
 pgr_maxflow
-------------
         230
(1 row)

Uno a Muchos

pgr_maxFlow(SQL de aristas, salida , destinos)
RETURNS BIGINT
Ejemplo:

Desde el vértice \(11\) a los vértices \(\{5, 10, 12\}\)

SELECT * FROM pgr_maxFlow(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  11, ARRAY[5, 10, 12]);
 pgr_maxflow
-------------
         340
(1 row)

Muchos a Uno

pgr_maxFlow(SQL de aristas, salidas , destino)
RETURNS BIGINT
Ejemplo:

De los vértices vertices \(\{11, 3, 17\}\) al vértice \(12\)

SELECT * FROM pgr_maxFlow(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  ARRAY[11, 3, 17], 12);
 pgr_maxflow
-------------
         230
(1 row)

Muchos a Muchos

pgr_maxFlow(SQL de aristas, salidas , destinos)
RETURNS BIGINT
Ejemplo:

De los vértices \(\{11, 3, 17\}\) a los vértices \(\{5, 10, 12\}\)

SELECT * FROM pgr_maxFlow(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  ARRAY[11, 3, 17], ARRAY[5, 10, 12]);
 pgr_maxflow
-------------
         360
(1 row)

Combinaciones

pgr_maxFlow(SQL de aristas, SQL de combinaciones)
RETURNS BIGINT
Ejemplo:

Usando una tabla de combinaciones, equivalente a calcular el resultado de los vértices \(\{5, 6\}\) a los vértices \(\{10, 15, 14\}\).

La tabla de combinaciones:

SELECT source, target FROM combinations
WHERE target NOT IN (5, 6);
 source | target
--------+--------
      5 |     10
      6 |     15
      6 |     14
(3 rows)

La consulta:

SELECT * FROM pgr_maxFlow(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  'SELECT * FROM combinations WHERE target NOT IN (5, 6)');
 pgr_maxflow
-------------
          80
(1 row)

Parámetros

Columna

Tipo

Descripción

SQL de aristas

TEXT

SQL de aristas como se describe a continuación

SQL de combinaciones

TEXT

SQL de combinaciones como se describe a abajo

salida

BIGINT

Identificador del vértice inicial de la ruta.

salidas

ARRAY[BIGINT]

Arreglo de identificadores de vértices iniciales.

destino

BIGINT

Identificador del vértice final de la ruta.

destinos

ARRAY[BIGINT]

Arreglo de identificadores de vértices finales.

Consultas Internas

SQL aristas

Columna

Tipo

x Defecto

Descripción

id

ENTEROS

Identificador de la arista.

source

ENTEROS

Identificador del primer vértice de la arista.

target

ENTEROS

Identificador del segundo vértice de la arista.

capacity

ENTEROS

Peso de la arista (source, target)

reverse_capacity

ENTEROS

-1

Peso de la arista (target, source)

  • Cuando negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

SQL Combinaciones

Parámetro

Tipo

Descripción

source

ENTEROS

Identificador del vértice de salida.

target

ENTEROS

Identificador del vértice de llegada.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

Columnas de Resultados

Tipo

Descripción

BIGINT

Flujo máximo posible desde el/los orígen(es) hacia el/los destino(s)

Ejemplos Adicionales

Ejemplo:

Manualmente asignar combinaciones de vértices.

SELECT * FROM pgr_maxFlow(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  'SELECT * FROM (VALUES (5, 10), (6, 15), (6, 14)) AS t(source, target)');
 pgr_maxflow
-------------
          80
(1 row)

Ver también

Índices y tablas