pgr_edmondsKarp¶

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

Boost Graph Inside

Availability

Version 3.0.0
- Official function
Version 2.5.0
- Renamed from pgr_maxFlowEdmondsKarp
- Proposed function
Version 2.3.0
- New Experimental function

Support

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 * E ^ 2)\)

Signatures¶

Summary

pgr_edmondsKarp(Edges SQL, source,  target)
pgr_edmondsKarp(Edges SQL, sources, target)
pgr_edmondsKarp(Edges SQL, source,  targets)
pgr_edmondsKarp(Edges SQL, sources, targets)
RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)
OR EMPTY SET

One to One¶

pgr_edmondsKarp(Edges SQL, source,  target)
RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)
OR EMPTY SET

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

SELECT * FROM pgr_edmondsKarp(
    'SELECT id,
            source,
            target,
            capacity,
            reverse_capacity
    FROM edge_table'
    , 6, 11
);
 seq | edge | start_vid | end_vid | 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
(4 rows)

One to Many¶

pgr_edmondsKarp(Edges SQL, source,  targets)
RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)
OR EMPTY SET

Example:	From vertex \(6\) to vertices \(\{1, 3, 11\}\)

SELECT * FROM pgr_edmondsKarp(
    'SELECT id,
            source,
            target,
            capacity,
            reverse_capacity
    FROM edge_table'
   , 6, ARRAY[1, 3, 11]
);
 seq | edge | start_vid | end_vid | 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 |   80 |                50
   5 |    8 |         6 |       5 |  130 |                 0
   6 |    9 |         6 |       9 |   80 |                50
   7 |   11 |         6 |      11 |  130 |                 0
   8 |   16 |         9 |       4 |   80 |                 0
   9 |   12 |        10 |      11 |   80 |                20
(9 rows)

Many to One¶

pgr_edmondsKarp(Edges SQL, sources,  target)
RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)
OR EMPTY SET

Example:	From vertices \(\{6, 8, 12\}\) to vertex \(11\)

SELECT * FROM pgr_edmondsKarp(
    'SELECT id,
            source,
            target,
            capacity,
            reverse_capacity
    FROM edge_table'
   , ARRAY[6, 8, 12], 11
);
 seq | edge | start_vid | end_vid | 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
(4 rows)

Many to Many¶

pgr_edmondsKarp(Edges SQL, sources,  targets)
RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)
OR EMPTY SET

Example:	From vertices \(\{6, 8, 12\}\) to vertices \(\{1, 3, 11\}\)

SELECT * FROM pgr_edmondsKarp(
    'SELECT id,
            source,
            target,
            capacity,
            reverse_capacity
    FROM edge_table'
   , ARRAY[6, 8, 12], ARRAY[1, 3, 11]
);
 seq | edge | start_vid | end_vid | 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 |    8 |         6 |       5 |  130 |                 0
   6 |    9 |         6 |       9 |   80 |                50
   7 |   11 |         6 |      11 |  130 |                 0
   8 |    7 |         8 |       5 |   20 |                30
   9 |   16 |         9 |       4 |   80 |                 0
  10 |   12 |        10 |      11 |  100 |                 0
(10 rows)

Parameters¶

Column	Type	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

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`).