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

Boost Graph Inside

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 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, start vid, end vid)
pgr_maxFlow(Edges SQL, start vid, end vids)
pgr_maxFlow(Edges SQL, start vids, end vid)
pgr_maxFlow(Edges SQL, start vids, end vids)
pgr_maxFlow(Edges SQL, Combinations SQL)
RETURNS BIGINT

Uno a Uno

pgr_maxFlow(Edges SQL, start vid, end vid)
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, start vid, end vids)
RETURNS BIGINT
Ejemplo

From vertex \(6\) to vertices \(\{1, 3, 11\}\)

SELECT * FROM pgr_maxFlow(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edge_table',
  6, ARRAY[1, 3, 11]);
 pgr_maxflow
-------------
         340
(1 row)

Muchos a Uno

pgr_maxFlow(Edges SQL, start vids, end vid)
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, start vids, end vids)
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

Using a combinations table, equivalent to calculating result from vertices \(\{1, 2\}\) to vertices \(\{3, 4, 17\}\).

The combinations table:

SELECT source, target FROM combinations_table
WHERE target NOT IN (1, 2);
 source | target
--------+--------
      1 |      3
      2 |      4
      2 |     17
(3 rows)

The query:

SELECT * FROM pgr_maxFlow(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edge_table',
  'SELECT * FROM combinations_table
   WHERE target NOT IN (1, 2)');
 pgr_maxflow
-------------
          80
(1 row)

Parámetros

Columna

Tipo

Descripción

Edges SQL

TEXT

Edges SQL as described below

Combinations SQL

TEXT

Combinations SQL as described below

start vid

BIGINT

Identifier of the starting vertex of the path.

start vids

ARRAY[BIGINT]

Array of identifiers of starting vertices.

end vid

BIGINT

Identifier of the ending vertex of the path.

end vids

ARRAY[BIGINT]

Array of identifiers of ending vertices.

Consultas internas

SQL de aristas

Columna

Tipo

x Defecto

Descripción

id

ANY-INTEGER

Identificador de la arista.

source

ANY-INTEGER

Identificador del primer vértice extremo de la arista.

target

ANY-INTEGER

Identificador del segundo vértice extremo de la arista.

capacity

ANY-INTEGER

Weight of the edge (source, target)

reverse_capacity

ANY-INTEGER

-1

Weight of the edge (target, source)

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Combinaciones SQL

Parameter

Tipo

Descripción

source

ANY-INTEGER

Identifier of the departure vertex.

target

ANY-INTEGER

Identifier of the arrival vertex.

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)

Additional Examples

Ejemplo

Manually assigned vertex combinations.

SELECT * FROM pgr_pushRelabel(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edge_table',
  'SELECT * FROM (VALUES (1, 3), (2, 4), (2, 17)) AS t(source, target)');
 seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
   1 |    4 |         2 |       5 |   80 |                20
   2 |    8 |         5 |       6 |   80 |                20
   3 |    9 |         6 |       9 |   80 |                50
   4 |   16 |         9 |       4 |   80 |                 0
(4 rows)

Ver también

Índices y tablas