`pgr_pushRelabel`¶

pgr_pushRelabel — Calculates the flow on the graph edges that maximizes the flow from the sources to the targets using Push Relabel Algorithm.

_images/boost-inside.jpeg — Boost Graph Inside¶

Availability

Version 3.2.0
- New proposed signature
  - pgr_pushRelabel (Combinations)
Version 3.0.0
- Official function
Version 2.5.0
- Renamed from pgr_maxFlowPushRelabel
- Proposed function
Version 2.3.0
- New Experimental function

Description¶

The main characteristics are:

The graph is directed.
Process is done only on edges with positive capacities.
When the maximum flow is 0 then there is no flow and EMPTY SET 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.
Calculates the flow/residual capacity for each edge. In the output
- Edges with zero flow are omitted.
Creates a super source and edges to all the source(s), and a super target and the edges from all the targets(s).
The maximum flow through the graph is guaranteed to be the value returned by pgr_maxFlow when executed with the same parameters and can be calculated:
- By aggregation of the outgoing flow from the sources
- By aggregation of the incoming flow to the targets

Running time: \(O( V ^ 3)\)

Signatures¶

Summary

pgr_pushRelabel(Edges SQL, start vid, end vid)
pgr_pushRelabel(Edges SQL, start vid, end vids)
pgr_pushRelabel(Edges SQL, start vids, end vid)
pgr_pushRelabel(Edges SQL, start vids, end vids)
pgr_pushRelabel(Edges SQL, Combinations SQL)

RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)

OR EMPTY SET

One to One¶

pgr_pushRelabel(Edges SQL, start vid, end vid)

RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)

OR EMPTY SET

Example:: From vertex \(11\) to vertex \(12\)

SELECT * FROM pgr_pushRelabel(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  11, 12);
 seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
   1 |   10 |         7 |       8 |  100 |                30
   2 |   12 |         8 |      12 |  100 |                 0
   3 |    8 |        11 |       7 |  100 |                30
   4 |   11 |        11 |      12 |  130 |                 0
(4 rows)

One to Many¶

pgr_pushRelabel(Edges SQL, start vid, end vids)

RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)

OR EMPTY SET

Example:: From vertex \(11\) to vertices \(\{5, 10, 12\}\)

SELECT * FROM pgr_pushRelabel(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  11, ARRAY[5, 10, 12]);
 seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
   1 |    6 |         1 |       3 |   50 |                 0
   2 |    6 |         3 |       1 |   50 |                50
   3 |    7 |         3 |       7 |   50 |                 0
   4 |    1 |         6 |       5 |   30 |               100
   5 |    7 |         7 |       3 |   50 |                80
   6 |    4 |         7 |       6 |   30 |                20
   7 |   10 |         7 |       8 |  100 |                30
   8 |   12 |         8 |      12 |  100 |                 0
   9 |    8 |        11 |       7 |  130 |                 0
  10 |   11 |        11 |      12 |  130 |                 0
  11 |    9 |        11 |      16 |   80 |                50
  12 |    3 |        15 |      10 |   80 |                50
  13 |   16 |        16 |      15 |   80 |                 0
(13 rows)

Many to One¶

pgr_pushRelabel(Edges SQL, start vids, end vid)

RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)

OR EMPTY SET

Example:: From vertices \(\{11, 3, 17\}\) to vertex \(12\)

SELECT * FROM pgr_pushRelabel(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  ARRAY[11, 3, 17], 12);
 seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
   1 |   10 |         7 |       8 |  100 |                30
   2 |   12 |         8 |      12 |  100 |                 0
   3 |    8 |        11 |       7 |  100 |                30
   4 |   11 |        11 |      12 |  130 |                 0
(4 rows)

Many to Many¶

pgr_pushRelabel(Edges SQL, start vids, end vids)

RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)

OR EMPTY SET

Example:: From vertices \(\{11, 3, 17\}\) to vertices \(\{5, 10, 12\}\)

SELECT * FROM pgr_pushRelabel(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  ARRAY[11, 3, 17], ARRAY[5, 10, 12]);
 seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
   1 |    7 |         3 |       7 |   20 |                30
   2 |    1 |         6 |       5 |   50 |                80
   3 |    4 |         7 |       6 |   50 |                 0
   4 |   10 |         7 |       8 |  100 |                30
   5 |   12 |         8 |      12 |  100 |                 0
   6 |    8 |        11 |       7 |  130 |                 0
   7 |   11 |        11 |      12 |  130 |                 0
   8 |    9 |        11 |      16 |   80 |                50
   9 |    3 |        15 |      10 |   80 |                50
  10 |   16 |        16 |      15 |   80 |                 0
(10 rows)

Combinations¶

pgr_pushRelabel(Edges SQL, Combinations SQL)

RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)

OR EMPTY SET

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_pushRelabel(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  'SELECT * FROM combinations WHERE target NOT IN (5, 6)');
 seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
   1 |    4 |         6 |       7 |   80 |                20
   2 |    8 |         7 |      11 |   80 |                20
   3 |   11 |        11 |      12 |   50 |                80
   4 |    9 |        11 |      16 |   30 |               100
   5 |   13 |        12 |      17 |   50 |                50
   6 |   16 |        16 |      15 |   80 |                 0
   7 |   15 |        17 |      16 |   50 |                 0
(7 rows)

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¶

Column	Type	Description
seq	`INT`	Sequential value starting from 1.
edge	`BIGINT`	Identifier of the edge in the original query (edges_sql).
start_vid	`BIGINT`	Identifier of the first end point vertex of the edge.
end_vid	`BIGINT`	Identifier of the second end point vertex of the edge.
flow	`BIGINT`	Flow through the edge in the direction (`start_vid`, `end_vid`).
residual_capacity	`BIGINT`	Residual capacity of the edge in the direction (`start_vid`, `end_vid`).

Additional Examples¶

Example:: Manually assigned vertex combinations.

SELECT * FROM pgr_pushRelabel(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  'SELECT * FROM (VALUES (5, 10), (6, 15), (6, 14)) AS t(source, target)');
 seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
   1 |    4 |         6 |       7 |   80 |                20
   2 |    8 |         7 |      11 |   80 |                20
   3 |   11 |        11 |      12 |   50 |                80
   4 |    9 |        11 |      16 |   30 |               100
   5 |   13 |        12 |      17 |   50 |                50
   6 |   16 |        16 |      15 |   80 |                 0
   7 |   15 |        17 |      16 |   50 |                 0
(7 rows)

pgr_pushRelabel¶

Description¶

Signatures¶

One to One¶

One to Many¶

Many to One¶

Many to Many¶

Combinations¶

Parameters¶

Inner Queries¶

Edges SQL¶

Combinations SQL¶

Result Columns¶

Additional Examples¶

See Also¶

`pgr_pushRelabel`¶