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

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.
Running time:
where
is the value of the max flow. is upper bound on number of iterations. In many real world cases number of iterations is much smaller than .
Signatures¶
Summary
One to One¶
- Example:
From vertex
to vertex
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¶
- Example:
From vertex
to vertices
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¶
- Example:
From vertices
to vertex
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¶
- Example:
From vertices
to vertices
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¶
- Example:
Using a combinations table, equivalent to calculating result from vertices
to vertices .
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 as described below |
|
|
Combinations SQL as described below |
|
start vid |
|
Identifier of the starting vertex of the path. |
start vids |
|
Array of identifiers of starting vertices. |
end vid |
|
Identifier of the ending vertex of the path. |
end vids |
|
Array of identifiers of ending vertices. |
Inner Queries¶
Edges SQL¶
Column |
Type |
Default |
Description |
---|---|---|---|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
ANY-INTEGER |
Capacity of the edge (
|
|
|
ANY-INTEGER |
-1 |
Capacity of the edge (
|
|
ANY-NUMERICAL |
Weight of the edge ( |
|
|
ANY-NUMERICAL |
Weight of the edge ( |
Where:
- ANY-INTEGER:
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Combinations SQL¶
Parameter |
Type |
Description |
---|---|---|
|
ANY-INTEGER |
Identifier of the departure vertex. |
|
ANY-INTEGER |
Identifier of the arrival vertex. |
Where:
- ANY-INTEGER:
SMALLINT
,INTEGER
,BIGINT
Resturn Columns¶
Type |
Description |
---|---|
|
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)
See Also¶
Indices and tables