# pgr_boykovKolmogorov¶

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

Availability:

• Version 3.0.0
• Official function
• Version 2.5.0
• Renamed from pgr_maxFlowBoykovKolmogorov
• 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: Polynomial

## Signatures¶

Summary

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


### One to One¶

pgr_boykovKolmogorov(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_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¶

pgr_boykovKolmogorov(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_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¶

pgr_boykovKolmogorov(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_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¶

pgr_boykovKolmogorov(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_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)



## Parameters¶

Column Type Default 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).