pgRouting Manual (2.3)

pgr_maxFlowBoykovKolmogorov - Proposed

«  pgr_maxFlowEdmondsKarp - Proposed   ::   Contents   ::   Applications of Maximum Flow  »


pgr_maxFlowBoykovKolmogorov - Proposed

Name

pgr_maxFlowBoykovKolmogorov — 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
../../../_images/boost-inside8.jpeg

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 Boykov and Kolmogorov.

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: in general polynomial complexity, performs well on graphs that represent 2D grids (eg.: roads).

Signature Summary

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

Signatures

One to One

The available signature calculates the maximum flow from one source vertex to one sink vertex.

pgr_maxFlowBoykovKolmogorov(edges_sql, source_vertex,  sink_vertex)
RETURNS SET OF (id, edge_id, source, target, flow, residual_capacity)
  OR EMPTY SET
Example:
SELECT * FROM pgr_maxFlowBoykovKolmogorov(
    '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

The available signature calculates the maximum flow from one source vertex to many sink vertices.

pgr_maxFlowBoykovKolmogorov(edges_sql, source_vertex,  sink_vertices)
RETURNS SET OF (id, edge_id, source, target, flow, residual_capacity)
  OR EMPTY SET
Example:
SELECT * FROM pgr_maxFlowBoykovKolmogorov(
    '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

The available signature calculates the maximum flow from many source vertices to one sink vertex.

pgr_maxFlowBoykovKolmogorov(edges_sql, source_vertices,  sink_vertex)
RETURNS SET OF (id, edge_id, source, target, flow, residual_capacity)
  OR EMPTY SET
Example:
SELECT * FROM pgr_maxFlowBoykovKolmogorov(
    '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

The available signature calculates the maximum flow from many sources to many sinks.

pgr_maxFlowBoykovKolmogorov(edges_sql, source_vertices,  sink_vertices)
RETURNS SET OF (id, edge_id, source, target, flow, residual_capacity)
  OR EMPTY SET
Example:
SELECT * FROM pgr_maxFlowBoykovKolmogorov(
    '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).

«  pgr_maxFlowEdmondsKarp - Proposed   ::   Contents   ::   Applications of Maximum Flow  »