pgr_maxFlow
¶
pgr_maxFlow
— Calculates the maximum flow in a directed graph from the
source(s) to the targets(s) using the Push Relabel algorithm.
Availability
Version 3.2.0
New proposed signature
pgr_maxFlow
(Combinations)
Version 3.0.0
Official function
Version 2.4.0
New Proposed function
Description¶
The main characteristics are:
The graph is directed.
Calculates the maximum flow from the source(s) to the target(s).
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 the pgr_pushRelabel algorithm.
Running time: \(O( V ^ 3)\)
Signatures¶
Summary
BIGINT
One to One¶
BIGINT
- Example:
From vertex \(11\) to vertex \(12\)
SELECT * FROM pgr_maxFlow(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
11, 12);
pgr_maxflow
-------------
230
(1 row)
One to Many¶
BIGINT
- Example:
From vertex \(11\) to vertices \(\{5, 10, 12\}\)
SELECT * FROM pgr_maxFlow(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
11, ARRAY[5, 10, 12]);
pgr_maxflow
-------------
340
(1 row)
Many to One¶
BIGINT
- Example:
From vertices \(\{11, 3, 17\}\) to vertex \(12\)
SELECT * FROM pgr_maxFlow(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
ARRAY[11, 3, 17], 12);
pgr_maxflow
-------------
230
(1 row)
Many to Many¶
BIGINT
- Example:
From vertices \(\{11, 3, 17\}\) to vertices \(\{5, 10, 12\}\)
SELECT * FROM pgr_maxFlow(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
ARRAY[11, 3, 17], ARRAY[5, 10, 12]);
pgr_maxflow
-------------
360
(1 row)
Combinations¶
BIGINT
- 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_maxFlow(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
'SELECT * FROM combinations WHERE target NOT IN (5, 6)');
pgr_maxflow
-------------
80
(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 |
Weight of the edge ( |
|
|
ANY-INTEGER |
-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¶
Type |
Description |
---|---|
|
Maximum flow possible from the source(s) to the target(s) |
Additional Examples¶
- Example:
Manually assigned vertex combinations.
SELECT * FROM pgr_maxFlow(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
'SELECT * FROM (VALUES (5, 10), (6, 15), (6, 14)) AS t(source, target)');
pgr_maxflow
-------------
80
(1 row)
See Also¶
https://www.boost.org/libs/graph/doc/push_relabel_max_flow.html
https://en.wikipedia.org/wiki/Push%E2%80%93relabel_maximum_flow_algorithm
Indices and tables