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

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)