• Supported versions:

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

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

  • Nueva función experimental:

    • pgr_maxFlowMinCost_Cost(Combinaciones)

• Versión 3.0.0

  • Nueva función experimental

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)
pgr_maxFlowMinCost_Cost(Edges SQL, Combinations SQL) -- Experimental on v3.2
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)

Combinaciones

pgr_maxFlowMinCost_Cost(Edges SQL, Combinations SQL)
RETURNS FLOAT

Ejemplo

Usando una tabla de combinaciones, equivalente a calcular el resultado de los vértices \(\{7, 13\} a los vértices :math:\){3, 9}`.

SELECT * FROM pgr_MaxFlowMinCost_Cost(
    'SELECT id,
     source, target,
     capacity, reverse_capacity,
     cost, reverse_cost FROM edge_table',
    'SELECT * FROM ( VALUES (7, 3), (13, 9) ) AS t(source, target)'
);
 pgr_maxflowmincost_cost
-------------------------
                     600
(1 row)

Parámetros

Columna	Tipo	Valores predeterminados	Descripción
Edges SQL	TEXT		Consulta de bordes como se describe en Consultas internas.
Combinaciones SQL	TEXT		Consultas de combinaciones como se describe en Consultas internas.
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.

Consultas internas

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

Combinaciones SQL

una consulta SQL que debe devolver un conjunto de filas con las siguientes columnas:

Columna	Tipo	Valores predeterminados	Descripción
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.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

La función agrega los orígenes y los destinos, quita los duplicados y, a continuación, calcula el resultado de los vértices de origen resultantes a los vértices de destino.

Columnas de Resultados

Tipo	Descripción
FLOAT	Coste Mínimo Flujo Máximo posible desde el/los origen(es) hasta el/los objetivo(s)

Ver también

• Flow - Familia de funciones.

• https://www.boost.org/libs/graph/doc/successive_shortest_path_nonnegative_weights.html

Índices y tablas

• Índice

• Página de Búsqueda