pgr_maxFlowEdmondsKarp - Proposed¶

Name¶

pgr_maxFlowEdmondsKarp — Calculates the maximum flow in a directed graph given a source and a destination. Implemented by Boost Graph Library.

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

Boost Graph Inside

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. Developed by Edmonds and Karp.

Characteristics:¶

The main characterics are:

The graph must be directed.
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 (See signatures below).
Running time: \(O(V * E^2)\).

Signature Summary¶

pgr_maxFlowEdmondsKarp(edges_sql, source_vertex,  sink_vertex)
pgr_maxFlowEdmondsKarp(edges_sql, source_vertices,  sink_vertex)
pgr_maxFlowEdmondsKarp(edges_sql, source_vertex,  sink_vertices)
pgr_maxFlowEdmondsKarp(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 on a directed graph.

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

Example:

SELECT * FROM pgr_maxFlowEdmondsKarp(
    '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¶

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

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

Example:

SELECT * FROM pgr_maxFlowEdmondsKarp(
    '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[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 |   80 |                50
   5 |       5 |      6 |      3 |   50 |                 0
   6 |       8 |      6 |      5 |  130 |                 0
   7 |       9 |      6 |      9 |  130 |                 0
   8 |      11 |      6 |     11 |  130 |                 0
   9 |      15 |      9 |     12 |   50 |                30
  10 |      16 |      9 |      4 |   80 |                 0
  11 |      12 |     10 |     11 |   80 |                20
  12 |      13 |     12 |     11 |   50 |                 0
(12 rows)

Many to One¶

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

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

Example:

SELECT * FROM pgr_maxFlowEdmondsKarp(
    '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 on a directed graph.

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

Example:

SELECT * FROM pgr_maxFlowEdmondsKarp(
    '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 |   80 |                50
   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
(12 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).

pgRouting Manual (2.3)