pgr_maxFlowMinCost_Cost - Experimental

pgr_maxFlowMinCost_Cost — Calcula el costo mínimo para el máximo flujo en un grafo dirigido desde el/los origen(es) hacia el/los destino(s).

_images/boost-inside.jpeg

Adentro: Boost Graph

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

Disponibilidad

  • Versión 3.0.0

    • Nueva función experimental

Soporte

  • Versiones soportadas: actual(3.1) 3.0

Descripción

Las características principales son:

  • El grafo es dirigido.

  • El valor de coste de todas las aristas de entrada debe ser no negativo.

  • Cuando el flujo máximo es 0 entonces no hay flujo y se devuelve un 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.

  • Utiliza el algoritmo pgr_maxFlowMinCost .

  • Tiempo de ejecución: \(O(U * (E + V * logV))\), donde \(U\) es el valor del flujo máximo. \(U\) es el límite máximo en número de iteraciones is upper bound on number of iteration. En muchos casos reales, la cantidad de iteraciones es mucho menor que \(U\).

Firmas

Resumen

pgr_maxFlowMinCost_Cost(Edges SQL, source, target)
pgr_maxFlowMinCost_Cost(Edges SQL, sources, target)
pgr_maxFlowMinCost_Cost(Edges SQL, source, targets)
pgr_maxFlowMinCost_Cost(Edges SQL, sources, targets)
RETURNS FLOAT

Uno a Uno

pgr_maxFlowMinCost_Cost(Edges SQL, source, target)
RETURNS FLOAT
Ejemplo

Desde el vértice \(2\) al vértice \(3\)

SELECT * FROM pgr_MaxFlowMinCost_Cost(
    'SELECT id,
     source, target,
     capacity, reverse_capacity,
     cost, reverse_cost FROM edge_table',
    2, 3
);
 pgr_maxflowmincost_cost
-------------------------
                     400
(1 row)

Uno a Muchos

pgr_maxFlowMinCost_Cost(Edges SQL, source, targets)
RETURNS FLOAT
Ejemplo

Desde el vértice \(13\) a los vértices \(\{7, 1, 4\}\)

SELECT * FROM pgr_MaxFlowMinCost_Cost(
    'SELECT id,
     source, target,
     capacity, reverse_capacity,
     cost, reverse_cost FROM edge_table',
    13, ARRAY[7, 1, 4]
);
 pgr_maxflowmincost_cost
-------------------------
                     450
(1 row)

Muchos a Uno

pgr_maxFlowMinCost_Cost(Edges SQL, sources, target)
RETURNS FLOAT
Ejemplo

Desde los vértices \(\{1, 7, 14\}\) al vértice \(12\)

SELECT * FROM pgr_MaxFlowMinCost_Cost(
    'SELECT id,
     source, target,
     capacity, reverse_capacity,
     cost, reverse_cost FROM edge_table',
    ARRAY[1, 7, 14], 12
);
 pgr_maxflowmincost_cost
-------------------------
                     650
(1 row)

Muchos a Muchos

pgr_maxFlowMinCost_Cost(Edges SQL, sources, targets)
RETURNS FLOAT
Ejemplo

Desde los vértices \(\{7, 13\}\) a los vértices \(\{3, 9\}\)

SELECT * FROM pgr_MaxFlowMinCost_Cost(
    'SELECT id,
     source, target,
     capacity, reverse_capacity,
     cost, reverse_cost FROM edge_table',
    ARRAY[7, 13], ARRAY[3, 9]
);
 pgr_maxflowmincost_cost
-------------------------
                     600
(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

Capacidad de la arista (origen, destino)

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

reverse_capacity (capacidad inversa)

ANY-INTEGER

-1

Capacidad de la arista (destino, origen),

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

cost

ANY-NUMERICAL

Peso de la arista (origen, destino) si existe.

reverse_cost

ANY-NUMERICAL

0

Peso de la arista (destino, origen) si existe.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

smallint, int, bigint, real, float

Columnas de Resultados

Tipo

Descripción

FLOAT

Coste Mínimo Flujo Máximo posible desde el/los origen(es) hasta el/los objetivo(s)