# pgr_maxFlowPushRelabel Proposed¶

## Name¶

pgr_maxFlowPushRelabel — Calculates the maximum flow in a directed graph given a source and a destination.

Warning

These are proposed 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

## Synopsis¶

Calculates the maximum flow in a directed graph from a source node to a sink node. Edges must be weighted with non-negative capacities.

## Characteristics:¶

The main characterics are:
• Calculates the flow/residual capacity for each edge. In the output, edges with zero flow are omitted.
• The maximum flow through the graph can be calculated by aggregation on source/sink.
• Returns nothing if source and sink are the same.
• Allows multiple sources and sinks.
• Running time: $$O( V ^ 3)$$

## Signature Summary¶

pgr_maxFlowPushRelabel(edges_sql, source_vertex,  sink_vertex)
pgr_maxFlowPushRelabel(edges_sql, source_vertices,  sink_vertex)
pgr_maxFlowPushRelabel(edges_sql, source_vertex,  sink_vertices)
pgr_maxFlowPushRelabel(edges_sql, source_vertices,  sink_vertices)
RETURNS SET OF (id, edge_id, source, target, flow, residual_capacity)
OR EMPTY SET


## Signatures¶

### One to One¶

Calculates the maximum flow from one source vertex to one sink vertex in a directed graph.

pgr_maxFlowPushRelabel(edges_sql, source_vertex,  sink_vertex)
RETURNS SET OF (id, edge_id, source, target, flow, residual_capacity)
OR EMPTY SET

SELECT * FROM pgr_maxFlowPushRelabel(
'SELECT id,
source,
target,
c1.capacity as capacity,
c2.capacity as reverse_capacity
FROM edge_table JOIN categories AS c1 USING(category_id), categories AS c2
WHERE edge_table.reverse_category_id = c2.category_id
ORDER BY id'
, 6, 11
);
seq | edge_id | source | target | flow | residual_capacity
-----+---------+--------+--------+------+-------------------
1 |      10 |      5 |     10 |  100 |                30
2 |       8 |      6 |      5 |  100 |                30
3 |       9 |      6 |      9 |   50 |                80
4 |      11 |      6 |     11 |  130 |                 0
5 |      15 |      9 |     12 |   50 |                30
6 |      12 |     10 |     11 |  100 |                 0
7 |      13 |     12 |     11 |   50 |                 0
(7 rows)


### One to Many¶

Ccalculates the maximum flow from one source vertex to many sink vertices in a directed graph.

pgr_maxFlowPushRelabel(edges_sql, source_vertex,  sink_vertices)
RETURNS SET OF (id, edge_id, source, target, flow, residual_capacity)
OR EMPTY SET

SELECT * FROM pgr_maxFlowPushRelabel(
'SELECT id,
source,
target,
c1.capacity as capacity,
c2.capacity as reverse_capacity
FROM edge_table JOIN categories AS c1 USING(category_id), categories AS c2
WHERE edge_table.reverse_category_id = c2.category_id
ORDER BY id'
, 6, ARRAY[11, 1, 13]
);
seq | edge_id | source | target | flow | residual_capacity
-----+---------+--------+--------+------+-------------------
1 |       1 |      2 |      1 |  130 |                 0
2 |       4 |      2 |      5 |   20 |                80
3 |       2 |      3 |      2 |  100 |                 0
4 |       3 |      4 |      3 |   50 |                80
5 |       4 |      5 |      2 |   50 |                 0
6 |       7 |      5 |      8 |   50 |                80
7 |      10 |      5 |     10 |  100 |                30
8 |       5 |      6 |      3 |   50 |                 0
9 |       8 |      6 |      5 |  130 |                 0
10 |       9 |      6 |      9 |  100 |                30
11 |      11 |      6 |     11 |  130 |                 0
12 |       6 |      7 |      8 |   50 |                 0
13 |       6 |      8 |      7 |   50 |                50
14 |       7 |      8 |      5 |   50 |                 0
15 |      15 |      9 |     12 |   50 |                30
16 |      16 |      9 |      4 |   50 |                30
17 |      12 |     10 |     11 |  100 |                 0
18 |      13 |     12 |     11 |   50 |                 0
(18 rows)


### Many to One¶

Calculates the maximum flow from many source vertices to one sink vertex in a directed graph.

pgr_maxFlowPushRelabel(edges_sql, source_vertices,  sink_vertex)
RETURNS SET OF (id, edge_id, source, target, flow, residual_capacity)
OR EMPTY SET

SELECT * FROM pgr_maxFlowPushRelabel(
'SELECT id,
source,
target,
c1.capacity as capacity,
c2.capacity as reverse_capacity
FROM edge_table JOIN categories AS c1 USING(category_id), categories AS c2
WHERE edge_table.reverse_category_id = c2.category_id
ORDER BY id'
, ARRAY[6, 8, 12], 11
);
seq | edge_id | source | target | flow | residual_capacity
-----+---------+--------+--------+------+-------------------
1 |      10 |      5 |     10 |  100 |                30
2 |       8 |      6 |      5 |  100 |                30
3 |      11 |      6 |     11 |  130 |                 0
4 |      12 |     10 |     11 |  100 |                 0
5 |      13 |     12 |     11 |   50 |                 0
(5 rows)


### Many to Many¶

Calculates the maximum flow from many sources to many sinks in a directed graph.

pgr_maxFlowPushRelabel(edges_sql, source_vertices,  sink_vertices)
RETURNS SET OF (id, edge_id, source, target, flow, residual_capacity)
OR EMPTY SET

SELECT * FROM pgr_maxFlowPushRelabel(
'SELECT id,
source,
target,
c1.capacity as capacity,
c2.capacity as reverse_capacity
FROM edge_table JOIN categories AS c1 USING(category_id), categories AS c2
WHERE edge_table.reverse_category_id = c2.category_id
ORDER BY id'
, ARRAY[6, 8, 12], ARRAY[1, 3, 11]
);
seq | edge_id | source | target | flow | residual_capacity
-----+---------+--------+--------+------+-------------------
1 |       1 |      2 |      1 |   50 |                80
2 |       3 |      4 |      3 |   80 |                50
3 |       4 |      5 |      2 |   50 |                 0
4 |      10 |      5 |     10 |  100 |                30
5 |       5 |      6 |      3 |   50 |                 0
6 |       8 |      6 |      5 |  130 |                 0
7 |       9 |      6 |      9 |   30 |               100
8 |      11 |      6 |     11 |  130 |                 0
9 |       7 |      8 |      5 |   20 |                30
10 |      16 |      9 |      4 |   80 |                 0
11 |      12 |     10 |     11 |  100 |                 0
12 |      13 |     12 |     11 |   50 |                 0
13 |      15 |     12 |      9 |   50 |                 0
(13 rows)


## Description of the Signatures¶

### Description of the SQL query¶

edges_sql: an SQL query, which should return a set of rows with the following columns:
Column Type 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). Must be positive.
reverse_capacity ANY-INTEGER (optional) Weight of the edge (target, source). Must be positive or null.

Where:

ANY-INTEGER: SMALLINT, INTEGER, BIGINT

### Description of the parameters of the signatures¶

Column Type Description
edges_sql TEXT SQL query as described above.
source_vertex BIGINT Identifier of the source vertex(or vertices).
sink_vertex BIGINT Identifier of the sink vertex(or vertices).

### Description of the Return Values¶

Column Type Description
seq INT Sequential value starting from 1.
edge_id 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).