pgr_maxFlowMinCost - Experimental - pgRouting Manual (3.4)
pgr_maxFlowMinCost
- Experimental
pgr_maxFlowMinCost
- Calculates the edges that minimizes the total cost of
the maximum flow on a graph
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( 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
-
-
TODO check which statement is true:
-
The cost value of all input edges must be nonnegative.
-
Process is done when the cost value of all input edges is nonnegative.
-
Process is done on edges with nonnegative cost.
-
-
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
(seq,
edge,
source,
target,
flow,
residual_capacity,
cost,
agg_cost)
One to One
(seq,
edge,
source,
target,
flow,
residual_capacity,
cost,
agg_cost)
- Example :
-
From vertex \(11\) to vertex \(12\)
SELECT * FROM pgr_maxFlowMinCost(
'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
FROM edges',
11, 12);
seq edge source target flow residual_capacity cost agg_cost
-----+------+--------+--------+------+-------------------+------+----------
1 10 7 8 100 30 100 100
2 12 8 12 100 0 100 200
3 8 11 7 100 30 100 300
4 11 11 12 130 0 130 430
(4 rows)
One to Many
(seq,
edge,
source,
target,
flow,
residual_capacity,
cost,
agg_cost)
- Example :
-
From vertex \(11\) to vertices \(\{5, 10, 12\}\)
SELECT * FROM pgr_maxFlowMinCost(
'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
FROM edges',
11, ARRAY[5, 10, 12]);
seq edge source target flow residual_capacity cost agg_cost
-----+------+--------+--------+------+-------------------+------+----------
1 1 6 5 30 100 30 30
2 4 7 6 30 20 30 60
3 10 7 8 100 30 100 160
4 12 8 12 100 0 100 260
5 8 11 7 130 0 130 390
6 11 11 12 130 0 130 520
7 9 11 16 80 50 80 600
8 3 15 10 80 50 80 680
9 16 16 15 80 0 80 760
(9 rows)
Many to One
(seq,
edge,
source,
target,
flow,
residual_capacity,
cost,
agg_cost)
- Example :
-
From vertices \(\{11, 3, 17\}\) to vertex \(12\)
SELECT * FROM pgr_maxFlowMinCost(
'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
FROM edges',
ARRAY[11, 3, 17], 12);
seq edge source target flow residual_capacity cost agg_cost
-----+------+--------+--------+------+-------------------+------+----------
1 7 3 7 50 0 50 50
2 10 7 8 100 30 100 150
3 12 8 12 100 0 100 250
4 8 11 7 50 80 50 300
5 11 11 12 130 0 130 430
(5 rows)
Many to Many
(seq,
edge,
source,
target,
flow,
residual_capacity,
cost,
agg_cost)
- Example :
-
From vertices \(\{11, 3, 17\}\) to vertices \(\{5, 10, 12\}\)
SELECT * FROM pgr_maxFlowMinCost(
'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
FROM edges',
ARRAY[11, 3, 17], ARRAY[5, 10, 12]);
seq edge source target flow residual_capacity cost agg_cost
-----+------+--------+--------+------+-------------------+------+----------
1 7 3 7 50 0 50 50
2 1 6 5 50 80 50 100
3 4 7 6 50 0 50 150
4 10 7 8 100 30 100 250
5 12 8 12 100 0 100 350
6 8 11 7 100 30 100 450
7 11 11 12 130 0 130 580
8 9 11 16 30 100 30 610
9 3 15 10 80 50 80 690
10 16 16 15 80 0 80 770
11 15 17 16 50 0 50 820
(11 rows)
Combinations
(seq,
edge,
source,
target,
flow,
residual_capacity,
cost,
agg_cost)
- 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(
'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
FROM edges',
'SELECT * FROM combinations WHERE target NOT IN (5, 6)');
seq edge source target flow residual_capacity cost agg_cost
-----+------+--------+--------+------+-------------------+------+----------
1 4 6 7 80 20 80 80
2 8 7 11 80 20 80 160
3 9 11 16 80 50 80 240
4 16 16 15 80 0 80 320
(4 rows)
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 |
\(-1\) |
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
Result Columns
|
Column |
Type |
Description |
|---|---|---|
|
seq |
|
Sequential value starting from 1 . |
|
edge |
|
Identifier of the edge in the original query (edges_sql). |
|
source |
|
Identifier of the first end point vertex of the edge. |
|
target |
|
Identifier of the second end point vertex of the edge. |
|
flow |
|
Flow through the edge in the direction (source, target). |
|
residual_capacity |
|
Residual capacity of the edge in the direction (source, target). |
|
cost |
|
The cost of sending this flow through the edge in the direction (source, target). |
|
agg_cost |
|
The aggregate cost. |
Additional Examples
- Example :
-
Manually assigned vertex combinations.
SELECT * FROM pgr_maxFlowMinCost(
'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)');
seq edge source target flow residual_capacity cost agg_cost
-----+------+--------+--------+------+-------------------+------+----------
1 4 6 7 80 20 80 80
2 8 7 11 80 20 80 160
3 9 11 16 80 50 80 240
4 16 16 15 80 0 80 320
(4 rows)
See Also
Indices and tables