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.0.0
- Version 2.4.0
Support
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, source, target)
pgr_maxFlow(Edges SQL, sources, target)
pgr_maxFlow(Edges SQL, source, targets)
pgr_maxFlow(Edges SQL, sources, targets)
RETURNS BIGINT
One to One
pgr_maxFlow(Edges SQL, source, target)
RETURNS BIGINT
Example: | From vertex \(6\) to vertex \(11\) |
SELECT * FROM pgr_maxFlow(
'SELECT id,
source,
target,
capacity,
reverse_capacity
FROM edge_table'
, 6, 11
);
pgr_maxflow
-------------
230
(1 row)
One to Many
pgr_maxFlow(Edges SQL, source, targets)
RETURNS BIGINT
Example: | From vertex \(6\) to vertices \(\{11, 1, 13\}\) |
SELECT * FROM pgr_maxFlow(
'SELECT id,
source,
target,
capacity,
reverse_capacity
FROM edge_table'
, 6, ARRAY[11, 1, 13]
);
pgr_maxflow
-------------
340
(1 row)
Many to One
pgr_maxFlow(Edges SQL, sources, target)
RETURNS BIGINT
Example: | From vertices \(\{6, 8, 12\}\) to vertex \(11\) |
SELECT * FROM pgr_maxFlow(
'SELECT id,
source,
target,
capacity,
reverse_capacity
FROM edge_table'
, ARRAY[6, 8, 12], 11
);
pgr_maxflow
-------------
230
(1 row)
Many to Many
pgr_maxFlow(Edges SQL, sources, targets)
RETURNS BIGINT
Example: | From vertices \(\{6, 8, 12\}\) to vertices \(\{1, 3, 11\}\) |
SELECT * FROM pgr_maxFlow(
'SELECT id,
source,
target,
capacity,
reverse_capacity
FROM edge_table'
, ARRAY[6, 8, 12], ARRAY[1, 3, 11]
);
pgr_maxflow
-------------
360
(1 row)
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 |
|
Weight of the edge (source, target)
- When negative: edge (source, target) does not exist, therefore it’s not part of the graph.
|
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 |
Return Columns
Type |
Description |
BIGINT |
Maximum flow possible from the source(s) to the target(s) |
See Also
Indices and tables