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.

Boost Graph Inside¶
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 |
|
The edges SQL query as described in Inner Query. |
|
source |
|
Identifier of the starting vertex of the flow. |
|
sources |
|
Array of identifiers of the starting vertices of the flow. |
|
target |
|
Identifier of the ending vertex of the flow. |
|
targets |
|
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 |
|
Identifier of the edge. |
|
source |
|
Identifier of the first end point vertex of the edge. |
|
target |
|
Identifier of the second end point vertex of the edge. |
|
capacity |
|
Weight of the edge (source, target)
|
|
reverse_capacity |
|
-1 |
Weight of the edge (target, source),
|
Where:
- ANY-INTEGER
SMALLINT, INTEGER, BIGINT
Result Columns¶
Column |
Type |
Description |
---|---|---|
seq |
|
Sequential value starting from 1. |
edge |
|
Identifier of the edge in the original query(edges_sql). |
start_vid |
|
Identifier of the first end point vertex of the edge. |
end_vid |
|
Identifier of the second end point vertex of the edge. |
flow |
|
Flow through the edge in the direction ( |
residual_capacity |
|
Residual capacity of the edge in the direction ( |