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
- Version 3.0.0
- Version 2.4.0
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
pgr_maxFlow(Edges SQL, start vid, end vid)
pgr_maxFlow(Edges SQL, start vid, end vids)
pgr_maxFlow(Edges SQL, start vids, end vid)
pgr_maxFlow(Edges SQL, start vids, end vids)
pgr_maxFlow(Edges SQL, Combinations SQL)
RETURNS BIGINT
One to One
pgr_maxFlow(Edges SQL, start vid, end vid)
RETURNS 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
pgr_maxFlow(Edges SQL, start vid, end vids)
RETURNS 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
pgr_maxFlow(Edges SQL, start vids, end vid)
RETURNS 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
pgr_maxFlow(Edges SQL, start vids, end vids)
RETURNS 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
pgr_maxFlow(Edges SQL, Combinations SQL)
RETURNS 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 |
TEXT |
Edges SQL as described below |
Combinations SQL |
TEXT |
Combinations SQL as described below |
start vid |
BIGINT |
Identifier of the starting vertex of the path. |
start vids |
ARRAY[BIGINT] |
Array of identifiers of starting vertices. |
end vid |
BIGINT |
Identifier of the ending vertex of the path. |
end vids |
ARRAY[BIGINT] |
Array of identifiers of ending vertices. |
Inner Queries
Edges SQL
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 |
|
Weight of the edge (source , target ) |
reverse_capacity |
ANY-INTEGER |
-1 |
Weight of the edge (target , source )
- When negative: edge (
target , source ) does not exist, therefore
it’s not part of the graph.
|
Where:
ANY-INTEGER: | SMALLINT , INTEGER , BIGINT |
ANY-NUMERICAL: | SMALLINT , INTEGER , BIGINT , REAL , FLOAT |
Combinations SQL
Parameter |
Type |
Description |
source |
ANY-INTEGER |
Identifier of the departure vertex. |
target |
ANY-INTEGER |
Identifier of the arrival vertex. |
Where:
ANY-INTEGER: | SMALLINT , INTEGER , BIGINT |
Result Columns
Type |
Description |
BIGINT |
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
Indices and tables