Navigation :

Table of Contents - pgRouting Manual (3.4) > pgr_maxFlowMinCost_Cost - Experimental - pgRouting Manual (3.4)

pgr_maxFlowMinCost_Cost - Experimental - pgRouting Manual (3.4)

Supported versions: Latest ( 3.4 ) 3.3 3.2 3.1 3.0

`pgr_maxFlowMinCost_Cost` - Experimental

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

images/boost-inside.jpeg — Boost Graph Inside

Warning

Possible server crash

These functions might create a server crash

Warning

Experimental functions

They are not officially of the current release.
They likely will not be officially be part of the next release:
- The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
- Name might change.
- Signature might change.
- Functionality might change.
- pgTap tests might be missing.
- Might need c/c++ coding.
- May lack documentation.
- Documentation if any might need to be rewritten.
- Documentation examples might need to be automatically generated.
- Might need a lot of feedback from the comunity.
- Might depend on a proposed function of pgRouting
- Might depend on a deprecated function of pgRouting

Availability

Version 3.2.0
- New experimental function:
  - pgr_maxFlowMinCost_Cost ( Combinations )
Version 3.0.0
- New experimental function

Description

The main characteristics are:

The graph is directed .
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.
- There is no flow when a source is the same as a target .
Any duplicated value in the source(s) or target(s) are ignored.
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

The main characteristics are:

The graph is directed .
The cost value of all input edges must be nonnegative.
When the maximum flow is 0 then there is no flow and 0 is returned.
- There is no flow when a source is the same as a target .
Any duplicated value in the source(s) or target(s) are ignored.
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\) .

Signatures

Summary

      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

One to One

pgr_maxFlowMinCost_Cost( Edges SQL , start vid , end vid )

RETURNS FLOAT

Example :: 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)


     

One to Many

pgr_maxFlowMinCost_Cost( Edges SQL , start vid , end vids )

RETURNS FLOAT

Example :: 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)


     

Many to One

pgr_maxFlowMinCost_Cost( Edges SQL , start vids , end vid )

RETURNS FLOAT

Example :: 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)


     

Many to Many

pgr_maxFlowMinCost_Cost( Edges SQL , start vids , end vids )

RETURNS FLOAT

Example :: 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)


     

Combinations

pgr_maxFlowMinCost_Cost( Edges SQL , Combinations SQL )

RETURNS FLOAT

Example :: 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)


     

Parameters

Column	Type	Description
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

Edges SQL

Column	Type	Default	Description
`id`	ANY-INTEGER		Identifier of the edge.
`source`	ANY-INTEGER		Identifier of the first end point vertex of the edge.
`target`	ANY-INTEGER		Identifier of the second end point vertex of the edge.
`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

Where:

ANY-INTEGER :: SMALLINT , INTEGER , BIGINT
ANY-NUMERICAL :: SMALLINT , INTEGER , BIGINT , REAL , FLOAT

Combinations SQL

Parameter	Type	Description
`source`	ANY-INTEGER	Identifier of the departure vertex.
`target`	ANY-INTEGER	Identifier of the arrival vertex.

Where:

ANY-INTEGER :: SMALLINT , INTEGER , BIGINT

Resturn Columns

Type	Description
`FLOAT`	Minimum Cost Maximum Flow possible from the source(s) to the target(s)

Additional Examples

Example :: 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)


    

pgr_maxFlowMinCost_Cost - Experimental - pgRouting Manual (3.4)