# pgRouting Manual (2.5)

## pgr_boykovKolmogorov - Proposed

## Synopsis

`pgr_boykovKolmogorov` — Calculates the flow on the graph edges that maximizes the flow from the sources to the targets using Boykov Kolmogorov algorithm.

Boost Graph Inside

Availability:

- Renamed 2.5.0, Previous name pgr_maxFlowBoykovKolmogorov
- 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: Polynomial

## Signature Summary

    pgr_boykovKolmogorov(edges_sql, source,  target) - Proposed
    pgr_boykovKolmogorov(edges_sql, sources, target) - Proposed
    pgr_boykovKolmogorov(edges_sql, source,  targets) - Proposed
    pgr_boykovKolmogorov(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_boykovKolmogorov(edges_sql, source,  target)
    RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)
    OR EMPTY SET

Example: |

    SELECT * FROM pgr_boykovKolmogorov(
        '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_boykovKolmogorov(edges_sql, source,  targets)
    RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)
    OR EMPTY SET

Example: |

    SELECT * FROM pgr_boykovKolmogorov(
        '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_boykovKolmogorov(edges_sql, sources,  target)
    RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)
    OR EMPTY SET

Example: |

    SELECT * FROM pgr_boykovKolmogorov(
        '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_boykovKolmogorov(edges_sql, sources,  targets)
    RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)
    OR EMPTY SET

Example: |

    SELECT * FROM pgr_boykovKolmogorov(
        '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 | Default | 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).

## See Also

- Flow - Family of functions, pgr_pushRelabel, pgr_EdmondsKarp
- http://www.boost.org/libs/graph/doc/boykov_kolmogorov_max_flow.html

Indices and tables

- Index
- Search Page