## ``` 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.2.0

• New proposed signature

• Version 3.0.0

• Official function

• Version 2.5.0

• Renamed from ``` pgr_maxFlowBoykovKolmogorov ```

• Proposed function

• Version 2.3.0

• New Experimental function

### 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 , start vid , end vid )
pgr_boykovKolmogorov( Edges SQL , start vid , end vids )
pgr_boykovKolmogorov( Edges SQL , start vids , end vid )
pgr_boykovKolmogorov( Edges SQL , start vids , end vids )
pgr_boykovKolmogorov( Edges SQL , Combinations SQL )
RETURNS SET OF ``` (seq, edge, start_vid, end_vid, flow, residual_capacity) ```
OR EMPTY SET

#### One to One

pgr_boykovKolmogorov( Edges SQL , start vid , end vid )
RETURNS SET OF ``` (seq, edge, start_vid, end_vid, flow, residual_capacity) ```
OR EMPTY SET
Example :

From vertex \(11\) to vertex \(12\)

```SELECT * FROM pgr_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
11, 12);
seq  edge  start_vid  end_vid  flow  residual_capacity
-----+------+-----------+---------+------+-------------------
1    10          7        8   100                 30
2    12          8       12   100                  0
3     8         11        7   100                 30
4    11         11       12   130                  0
(4 rows)

```

#### One to Many

pgr_boykovKolmogorov( Edges SQL , start vid , end vids )
RETURNS SET OF ``` (seq, edge, start_vid, end_vid, flow, residual_capacity) ```
OR EMPTY SET
Example :

From vertex \(11\) to vertices \(\{5, 10, 12\}\)

```SELECT * FROM pgr_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
11, ARRAY[5, 10, 12]);
seq  edge  start_vid  end_vid  flow  residual_capacity
-----+------+-----------+---------+------+-------------------
1     1          6        5    50                 80
2     4          7        6    50                  0
3    10          7        8    80                 50
4    12          8       12    80                 20
5     8         11        7   130                  0
6    11         11       12   130                  0
7     9         11       16    80                 50
8     3         15       10    80                 50
9    16         16       15    80                  0
(9 rows)

```

#### Many to One

pgr_boykovKolmogorov( Edges SQL , start vids , end vid )
RETURNS SET OF ``` (seq, edge, start_vid, end_vid, flow, residual_capacity) ```
OR EMPTY SET
Example :

From vertices \(\{11, 3, 17\}\) to vertex \(12\)

```SELECT * FROM pgr_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
ARRAY[11, 3, 17], 12);
seq  edge  start_vid  end_vid  flow  residual_capacity
-----+------+-----------+---------+------+-------------------
1     7          3        7    50                  0
2    10          7        8   100                 30
3    12          8       12   100                  0
4     8         11        7    50                 80
5    11         11       12   130                  0
(5 rows)

```

#### Many to Many

pgr_boykovKolmogorov( Edges SQL , start vids , end vids )
RETURNS SET OF ``` (seq, edge, start_vid, end_vid, flow, residual_capacity) ```
OR EMPTY SET
Example :

From vertices \(\{11, 3, 17\}\) to vertices \(\{5, 10, 12\}\)

```SELECT * FROM pgr_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
ARRAY[11, 3, 17], ARRAY[5, 10, 12]);
seq  edge  start_vid  end_vid  flow  residual_capacity
-----+------+-----------+---------+------+-------------------
1     7          3        7    50                  0
2     1          6        5    50                 80
3     4          7        6    50                  0
4    10          7        8   100                 30
5    12          8       12   100                  0
6     8         11        7   100                 30
7    11         11       12   130                  0
8     9         11       16    80                 50
9     3         15       10    80                 50
10    16         16       15    80                  0
(10 rows)

```

#### Combinations

pgr_boykovKolmogorov( Edges SQL , Combinations SQL )
RETURNS SET OF ``` (seq, edge, start_vid, end_vid, flow, residual_capacity) ```
OR EMPTY SET
Example :

Using a combinations table, equivalent to calculating result from vertices \(\{5, 6\}\) to vertices \(\{10, 15, 14\}\) .

The combinations table:

```SELECT source, target FROM combinations
WHERE target NOT IN (5, 6);
source  target
--------+--------
5      10
6      15
6      14
(3 rows)

```

The query:

```SELECT * FROM pgr_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
'SELECT * FROM combinations WHERE target NOT IN (5, 6)');
seq  edge  start_vid  end_vid  flow  residual_capacity
-----+------+-----------+---------+------+-------------------
1     4          6        7    80                 20
2     8          7       11    80                 20
3     9         11       16    80                 50
4    16         16       15    80                  0
(4 rows)

```

### Parameters

Column

Type

Description

``` TEXT ```

Edges SQL as described below

``` TEXT ```

Combinations SQL as described below

start vid

``` BIGINT ```

Identifier of the starting vertex of the path.

start vids

``` ARRAY[BIGINT] ```

Array of identifiers of starting vertices.

end vid

``` BIGINT ```

Identifier of the ending vertex of the path.

end vids

``` ARRAY[BIGINT] ```

Array of identifiers of ending vertices.

### Inner Queries

#### Edges SQL

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

``` 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 ```

ANY-NUMERICAL :

``` SMALLINT ``` , ``` INTEGER ``` , ``` BIGINT ``` , ``` REAL ``` , ``` FLOAT ```

#### Combinations SQL

Parameter

Type

Description

``` source ```

ANY-INTEGER

Identifier of the departure vertex.

``` target ```

ANY-INTEGER

Identifier of the arrival vertex.

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

Example :

Manually assigned vertex combinations.

```SELECT * FROM pgr_boykovKolmogorov(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
'SELECT * FROM (VALUES (5, 10), (6, 15), (6, 14)) AS t(source, target)');
seq  edge  start_vid  end_vid  flow  residual_capacity
-----+------+-----------+---------+------+-------------------
1     4          6        7    80                 20
2     8          7       11    80                 20
3     9         11       16    80                 50
4    16         16       15    80                  0
(4 rows)

```