pgr_maxFlowMinCost
— Calculates the flow on the graph edges that maximizes
the flow and minimizes the cost from the sources to the targets.
Warning
Possible server crash
Warning
Experimental functions
Availability
Support
The main characteristics are:
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
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)
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)
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)
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)
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. |
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 |
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. |