pgr_edmondsKarp - Proposed¶

Synopsis¶

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:

Renamed 2.5.0, Previous name pgr_maxFlowEdmondsKarp
New in 2.3.0

Warning

Experimental 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

Characteristics

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)\)

Signature Summary¶

pgr_edmondsKarp(edges_sql, source,  target) - Proposed
pgr_edmondsKarp(edges_sql, sources, target) - Proposed
pgr_edmondsKarp(edges_sql, source,  targets) - Proposed
pgr_edmondsKarp(edges_sql, sources, targets) - Proposed
RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)
OR EMPTY SET

One to One¶

Calculates the flow on the graph edges that maximizes the flow from the source to the target.

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

Example:

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¶

Calculates the flow on the graph edges that maximizes the flow from the source to all of the targets.

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

Example:

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¶

Calculates the flow on the graph edges that maximizes the flow from all of the sources to the target.

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

Example:

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¶

Calculates the flow on the graph edges that maximizes the flow from all of the sources to all of the targets.

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

Example:

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)

Description of the Signatures¶

Description of the edges_sql query for Max-flow like functions¶

edges_sql:	an SQL query, 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

Description of the Parameters of the Flow Signatures¶

Column	Type	Description
edges_sql	`TEXT`	The edges SQL query as described above.
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.

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