pgr_maxFlowMinCost - Experimental¶
pgr_maxFlowMinCost
— Calculates the flow on the graph edges that maximizes
the flow and minimizes the cost from the sources to the targets.
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.0.0
- New experimental function
Support
- Supported versions: current(3.0)
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
pgr_maxFlowMinCost(Edges SQL, source, target)
pgr_maxFlowMinCost(Edges SQL, sources, target)
pgr_maxFlowMinCost(Edges SQL, source, targets)
pgr_maxFlowMinCost(Edges SQL, sources, targets)
RETURNS SET OF (seq, edge, source, target, flow, residual_capacity, cost, agg_cost)
OR EMPTY SET
One to One¶
pgr_maxFlowMinCost(Edges SQL, source, target)
RETURNS SET OF (seq, edge, source, target, flow, residual_capacity, cost, agg_cost)
OR EMPTY SET
Example: | From vertex \(2\) to vertex \(3\) |
---|
SELECT * FROM pgr_MaxFlowMinCost(
'SELECT id,
source, target,
capacity, reverse_capacity,
cost, reverse_cost FROM edge_table',
2, 3
);
seq | edge | source | target | flow | residual_capacity | cost | agg_cost
-----+------+--------+--------+------+-------------------+------+----------
1 | 4 | 2 | 5 | 80 | 20 | 80 | 80
2 | 3 | 4 | 3 | 80 | 50 | 80 | 160
3 | 8 | 5 | 6 | 80 | 20 | 80 | 240
4 | 9 | 6 | 9 | 80 | 50 | 80 | 320
5 | 16 | 9 | 4 | 80 | 0 | 80 | 400
(5 rows)
One to Many¶
pgr_maxFlowMinCost(Edges SQL, source, targets)
RETURNS SET OF (seq, edge, source, target, flow, residual_capacity, cost, agg_cost)
OR EMPTY SET
Example: | From vertex \(13\) to vertices \(\{7, 1, 4\}\) |
---|
SELECT * FROM pgr_MaxFlowMinCost(
'SELECT id,
source, target,
capacity, reverse_capacity,
cost, reverse_cost FROM edge_table',
13, ARRAY[7, 1, 4]
);
seq | edge | source | target | flow | residual_capacity | cost | agg_cost
-----+------+--------+--------+------+-------------------+------+----------
1 | 1 | 2 | 1 | 50 | 80 | 50 | 50
2 | 4 | 5 | 2 | 50 | 0 | 50 | 100
3 | 16 | 9 | 4 | 50 | 30 | 50 | 150
4 | 10 | 10 | 5 | 50 | 0 | 50 | 200
5 | 12 | 10 | 11 | 50 | 50 | 50 | 250
6 | 13 | 11 | 12 | 50 | 50 | 50 | 300
7 | 15 | 12 | 9 | 50 | 0 | 50 | 350
8 | 14 | 13 | 10 | 100 | 30 | 100 | 450
(8 rows)
Many to One¶
pgr_maxFlowMinCost(Edges SQL, sources, target)
RETURNS SET OF (seq, edge, source, target, flow, residual_capacity, cost, agg_cost)
OR EMPTY SET
Example: | From vertices \(\{1, 7, 14\}\) to vertex \(12\) |
---|
SELECT * FROM pgr_MaxFlowMinCost(
'SELECT id,
source, target,
capacity, reverse_capacity,
cost, reverse_cost FROM edge_table',
ARRAY[1, 7, 14], 12
);
seq | edge | source | target | flow | residual_capacity | cost | agg_cost
-----+------+--------+--------+------+-------------------+------+----------
1 | 1 | 1 | 2 | 80 | 0 | 80 | 80
2 | 4 | 2 | 5 | 80 | 20 | 80 | 160
3 | 8 | 5 | 6 | 100 | 0 | 100 | 260
4 | 10 | 5 | 10 | 30 | 100 | 30 | 290
5 | 9 | 6 | 9 | 50 | 80 | 50 | 340
6 | 11 | 6 | 11 | 50 | 80 | 50 | 390
7 | 6 | 7 | 8 | 50 | 0 | 50 | 440
8 | 7 | 8 | 5 | 50 | 0 | 50 | 490
9 | 15 | 9 | 12 | 50 | 30 | 50 | 540
10 | 12 | 10 | 11 | 30 | 70 | 30 | 570
11 | 13 | 11 | 12 | 80 | 20 | 80 | 650
(11 rows)
Many to Many¶
pgr_maxFlowMinCost(Edges SQL, sources, targets)
RETURNS SET OF (seq, edge, source, target, flow, residual_capacity, cost, agg_cost)
OR EMPTY SET
Example: | From vertices \(\{7, 13\}\) to vertices \(\{3, 9\}\) |
---|
SELECT * FROM pgr_MaxFlowMinCost(
'SELECT id,
source, target,
capacity, reverse_capacity,
cost, reverse_cost FROM edge_table',
ARRAY[7, 13], ARRAY[3, 9]
);
seq | edge | source | target | flow | residual_capacity | cost | agg_cost
-----+------+--------+--------+------+-------------------+------+----------
1 | 8 | 5 | 6 | 100 | 0 | 100 | 100
2 | 9 | 6 | 9 | 100 | 30 | 100 | 200
3 | 6 | 7 | 8 | 50 | 0 | 50 | 250
4 | 7 | 8 | 5 | 50 | 0 | 50 | 300
5 | 10 | 10 | 5 | 50 | 0 | 50 | 350
6 | 12 | 10 | 11 | 50 | 50 | 50 | 400
7 | 13 | 11 | 12 | 50 | 50 | 50 | 450
8 | 15 | 12 | 9 | 50 | 0 | 50 | 500
9 | 14 | 13 | 10 | 100 | 30 | 100 | 600
(9 rows)
Parameters¶
Column | Type | Default | Description |
---|---|---|---|
Edges SQL | TEXT |
The edges SQL query as described in Inner Query. | |
source | BIGINT |
Identifier of the starting vertex of the flow. | |
sources | ARRAY[BIGINT] |
Array of identifiers of the starting vertices of the flow. | |
target | BIGINT |
Identifier of the ending vertex of the flow. | |
targets | ARRAY[BIGINT] |
Array of identifiers of the ending vertices of the flow. |
Inner query¶
Edges SQL: | an SQL query of a directed graph of capacities, which should return a set of rows with the following columns: |
---|
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)
|
|
reverse_capacity | ANY-INTEGER |
-1 | Capacity of the edge (target, source),
|
cost | ANY-NUMERICAL |
Weight of the edge (source, target) if it exists. | |
reverse_cost | ANY-NUMERICAL |
0 | Weight of the edge (target, source) if it exists. |
Where:
ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
---|---|
ANY-NUMERICAL: | smallint, int, bigint, real, float |
Result Columns¶
Column | Type | Description |
---|---|---|
seq | INT |
Sequential value starting from 1. |
edge | BIGINT |
Identifier of the edge in the original query(edges_sql). |
source | BIGINT |
Identifier of the first end point vertex of the edge. |
target | BIGINT |
Identifier of the second end point vertex of the edge. |
flow | BIGINT |
Flow through the edge in the direction (source, target). |
residual_capacity | BIGINT |
Residual capacity of the edge in the direction (source, target). |
cost | FLOAT |
The cost of sending this flow through the edge in the direction (source, target). |
agg_cost | FLOAT |
The aggregate cost. |