pgr_maxFlowMinCost_Cost - Experimental

pgr_maxFlowMinCost_Cost — Calculates the minimum total cost of the maximum flow on a graph

_images/boost-inside.jpeg

Adentro: Boost Graph

Advertencia

Posible bloqueo del servidor

  • Estas funciones pueden crear un bloque 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:

  • Versión 3.0.0

    • Nueva función experimental

Descripción

Las características principales son:

  • El grafo es dirigido.

  • Process is done only on edges with positive capacities.

  • When the maximum flow is 0 then there is no flow and EMPTY SET is returned.

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

  • Calculates the flow/residual capacity for each edge. In the output

    • Edges with zero flow are omitted.

  • Creates a super source and edges to all the source(s), and a super target and the edges from all the targets(s).

  • The maximum flow through the graph is guaranteed to be the value returned by pgr_maxFlow when executed with the same parameters and can be calculated:

    • By aggregation of the outgoing flow from the sources

    • By aggregation of the incoming flow to the targets

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.

  • Uses pgr_maxFlowMinCost - Experimental.

  • Running time: \(O(U * (E + V * logV))\)

    • where \(U\) is the value of the max flow.

    • \(U\) is upper bound on number of iterations. In many real world cases number of iterations is much smaller than \(U\).

Firmas

Resumen

pgr_maxFlowMinCost_Cost(Edges SQL, start vid, end vid)
pgr_maxFlowMinCost_Cost(Edges SQL, start vid, end vids)
pgr_maxFlowMinCost_Cost(Edges SQL, start vids, end vid)
pgr_maxFlowMinCost_Cost(Edges SQL, start vids, end vids)
pgr_maxFlowMinCost_Cost(Edges SQL, Combinations SQL)
RETURNS FLOAT

Uno a Uno

pgr_maxFlowMinCost_Cost(Edges SQL, start vid, end vid)
RETURNS FLOAT
Ejemplo:

From vertex \(11\) to vertex \(12\)

SELECT * FROM pgr_maxFlowMinCost_Cost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
  FROM edges',
  11, 12);
 pgr_maxflowmincost_cost
-------------------------
                     430
(1 row)

Uno a Muchos

pgr_maxFlowMinCost_Cost(Edges SQL, start vid, end vids)
RETURNS FLOAT
Ejemplo:

From vertex \(11\) to vertices \(\{5, 10, 12\}\)

SELECT * FROM pgr_maxFlowMinCost_Cost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
  FROM edges',
  ARRAY[11, 3, 17], 12);
 pgr_maxflowmincost_cost
-------------------------
                     430
(1 row)

Muchos a Uno

pgr_maxFlowMinCost_Cost(Edges SQL, start vids, end vid)
RETURNS FLOAT
Ejemplo:

From vertices \(\{11, 3, 17\}\) to vertex \(12\)

SELECT * FROM pgr_maxFlowMinCost_Cost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
  FROM edges',
  11, ARRAY[5, 10, 12]);
 pgr_maxflowmincost_cost
-------------------------
                     760
(1 row)

Muchos a Muchos

pgr_maxFlowMinCost_Cost(Edges SQL, start vids, end vids)
RETURNS FLOAT
Ejemplo:

From vertices \(\{11, 3, 17\}\) to vertices \(\{5, 10, 12\}\)

SELECT * FROM pgr_maxFlowMinCost_Cost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
  FROM edges',
  ARRAY[11, 3, 17], ARRAY[5, 10, 12]);
 pgr_maxflowmincost_cost
-------------------------
                     820
(1 row)

Combinaciones

pgr_maxFlowMinCost_Cost(Edges SQL, Combinations SQL)
RETURNS FLOAT
Ejemplo:

Using a combinations table, equivalent to calculating result from vertices \(\{5, 6\}\) to vertices \(\{10, 15, 14\}\).

The combinations table:

SELECT source, target FROM combinations
WHERE target NOT IN (5, 6);
 source | target
--------+--------
      5 |     10
      6 |     15
      6 |     14
(3 rows)

The query:

SELECT * FROM pgr_maxFlowMinCost_Cost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
  FROM edges',
  'SELECT * FROM combinations WHERE target NOT IN (5, 6)');
 pgr_maxflowmincost_cost
-------------------------
                     320
(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.

Inner Queries

SQL de aristas

Columna

Tipo

x Defecto

Descripción

id

ANY-INTEGER

Identificador de la arista.

source

ANY-INTEGER

Identificador del primer vértice de la arista.

target

ANY-INTEGER

Identificador del segundo vértice 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:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

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:

ENTEROS:

SMALLINT, INTEGER, BIGINT

Resturn Columns

Tipo

Descripción

FLOAT

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

Additional Examples

Ejemplo:

Manually assigned vertex combinations.

SELECT * FROM pgr_maxFlowMinCost_Cost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
  FROM edges',
  'SELECT * FROM (VALUES (5, 10), (6, 15), (6, 14)) AS t(source, target)');
 pgr_maxflowmincost_cost
-------------------------
                     320
(1 row)

Ver también

Índices y tablas