Flow - Familia de funciones.

  • pgr_maxFlow - Only the Max flow calculation using Push and Relabel algorithm.

  • pgr_boykovKolmogorov - Algoritmos Boykov y Kolmogorov con detalles del flujo en aristas.

  • pgr_edmondsKarp - Algoritmo de Edmonds y Karp algorithm con detalles de flujo con detalles del flujo en aristas.

  • pgr_pushRelabel - Algoritmos Push y Relabel con detalles del flujo en aristas.

  • Aplicaciones

Experimental

Advertencia

Posible bloqueo del servidor

  • Estas funciones pueden crear un bloqueo del servidor

Advertencia

Funciones experimentales

  • No son oficialmente de la versión actual.

  • Es probable que oficialmente no formen parte de la siguiente versión:

    • Las funciones no podrían hacer uso de ANY-INTEGER ni ANY-NUMERICAL

    • El nombre puede cambiar.

    • La firma (declaración de funciones) podría cambiar.

    • La funcionalidad puede cambiar.

    • Las pruebas de pgTap pueden estar ausentes.

    • Posiblemente necesite codificación c/c++.

    • Puede haber carencia de documentación.

    • Hay documentación que, en dado caso, podría ser necesario reescribir.

    • Ejemplos de documentación que puede ser necesario generar automáticamente.

    • Puede ser necesaria más retroalimentación por parte de la comunidad.

    • Puede depender de una función propuesta de pgRouting

    • Podría depender de una función obsoleta de pgRouting

Información General de las Funciones de Flujo

Las características principales son:

  • El grafo es dirigido.

  • El proceso se realiza sólo en aristas con capacidades positivas.

  • Cuando el flujo máximo es 0 entonces no hay flujo, se devolverá: EMPTY SET.

    • 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.

  • Calcula la capacidad de flujo/residuo para cada arista. En la salida

    • Se omiten las aristas con flujo cero.

  • Crea una súper origen, con aristas para todos los orígenes, y un súper destino con aristas para todos los destinos.

  • Se garantiza que el flujo máximo a través del grafo es el valor devuelto por pgr_maxFlow cuando es ejecutado con los mismos parámetros y se puede calcular:

    • Mediante la agregación del flujo saliente de los orígenes

    • Mediante la agregación del flujo entrante a los destinos

pgr_maxFlow es el Flujo Máximo y se garantiza que ese máximo es el mismo en las funciones pgr_pushRelabel, pgr_edmondsKarp, pgr_boykovKolmogorov, pero el flujo real a través de cada arista puede variar.

Consultas internas

SQL de aristas

Capacity edges

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

Capacity-Cost edges

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

Capacity of the edge (source, target)

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

reverse_capacity

ANY-INTEGER

-1

Capacity of the edge (target, source)

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

cost

ANY-NUMERICAL

Weight of the edge (source, target) if it exist

reverse_cost

ANY-NUMERICAL

\(-1\)

Weight of the edge (target, source) if it exist

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Cost edges

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.

cost

ANY-NUMERICAL

Weight of the edge (source, target)

reverse_cost

ANY-NUMERICAL

-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 Resultados

Para pgr_pushRelabel, pgr_edmondsKarp, pgr_boykovKolmogorov :

Columna

Tipo

Descripción

seq

INT

Valor secuencial a partir de 1.

edge

BIGINT

Identificador de la arista en la consulta original(edges_sql).

start_vid

BIGINT

Identificador del primer vértice extremo de la arista.

end_vid

BIGINT

Identificador del segundo vértice extremo de la arista.

flujo

BIGINT

Flujo a través del arista en la dirección (start_vid, end_vid).

residual_capacity (capacidad residual)

BIGINT

Capacidad residual del arista en la dirección (start_vid, end_vid).

Para pgr_maxFlowMinCost - Experimental

Columna

Tipo

Descripción

seq

INT

Valor secuencial a partir de 1.

edge

BIGINT

Identificador de la arista en la consulta original(edges_sql).

origen

BIGINT

Identificador del primer vértice extremo de la arista.

objetivo

BIGINT

Identificador del segundo vértice extremo de la arista.

flujo

BIGINT

Flujo a través de la arista en la dirección (origen, destino).

residual_capacity (capacidad residual)

BIGINT

Capacidad residual de la arista en la dirección (origen, destino).

cost

FLOAT

El costo de enviar este flujo a través de la arista en la dirección (origen, destino).

agg_cost

FLOAT

El costo agregado.

Documentación Avanzada

Una red de flujo es un gráfico dirigido donde cada arista tiene una capacidad y un flujo. El flujo a través de una arista no debe exceder la capacidad de la misma. Además, el flujo entrante y saliente de un nodo debe ser igual, excepto para el origen que solo tiene flujo saliente, y el destino (receptor) que solo tiene flujo entrante.

Los algoritmos de Flujo Máximo calculan a través del grafo el flujo máximoy el flujo de cada arista

Se garantiza que el flujo máximo a través del grafo es el mismo con todas las implementaciones, pero el flujo real a través de cada arista puede variar. Dada la siguiente consulta:

pgr_maxFlow \((edges\_sql, source\_vertex, sink\_vertex)\)

where \(edges\_sql = \{(id_i, source_i, target_i, capacity_i, reverse\_capacity_i)\}\)

Definición del grafo

El grafo ponderado dirigido, \(G(V,E)\), se define como:

  • Conjunto de vértices \(V\)

    • \(source\_vertex \cup sink\_vertex \bigcup source_i \bigcup target_i\)

  • El conjunto de aristas \(E\)

    • \(E = \begin{cases} \text{ } \{(source_i, target_i, capacity_i) \text{ when } capacity > 0 \} & \quad \text{ if } reverse\_capacity = \varnothing \\ \text{ } & \quad \text{ } \\ \{(source_i, target_i, capacity_i) \text{ when } capacity > 0 \} & \text{ } \\ \cup \{(target_i, source_i, reverse\_capacity_i) \text{ when } reverse\_capacity_i > 0)\} & \quad \text{ if } reverse\_capacity \neq \varnothing \\ \end{cases}\)

Problema de Flujo Máximo

Dado:

  • \(G(V,E)\)

  • \(source\_vertex \in V\) el vértice de origen

  • \(sink\_vertex \in V\) el vértice pozo

Entonces:

  • \(pgr\_maxFlow(edges\_sql, source, sink) = \boldsymbol{\Phi}\)

  • \(\boldsymbol{\Phi} = {(id_i, edge\_id_i, source_i, target_i, flow_i, residual\_capacity_i)}\)

Donde:

\(\boldsymbol{\Phi}\) es un subconjunto de las aristas originales con su flujo y capacidad residual. El flujo máximo a través del grafo se puede obtrener agregando en el origen o sumidero y sumiendo el flujo hacia él. En particular:

  • \(id_i = i\)

  • \(edge\_id = id_i\) in edges_sql

  • \(residual\_capacity_i = capacity_i - flow_i\)

Ver también

Índices y tablas