pgr_boykovKolmogorov - pgRouting Manual (3.3)
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
-
pgr_boykovKolmogorov( Combinations )
-
-
-
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
(seq,
edge,
start_vid,
end_vid,
flow,
residual_capacity)
One to One
(seq,
edge,
start_vid,
end_vid,
flow,
residual_capacity)
- 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
(seq,
edge,
start_vid,
end_vid,
flow,
residual_capacity)
- 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
(seq,
edge,
start_vid,
end_vid,
flow,
residual_capacity)
- 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
(seq,
edge,
start_vid,
end_vid,
flow,
residual_capacity)
- 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
(seq,
edge,
start_vid,
end_vid,
flow,
residual_capacity)
- 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 |
|---|---|---|
|
|
Edges SQL as described below |
|
|
|
Combinations SQL as described below |
|
|
start vid |
|
Identifier of the starting vertex of the path. |
|
start vids |
|
Array of identifiers of starting vertices. |
|
end vid |
|
Identifier of the ending vertex of the path. |
|
end vids |
|
Array of identifiers of ending vertices. |
Inner Queries
Edges SQL
|
Column |
Type |
Default |
Description |
|---|---|---|---|
|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
|
ANY-INTEGER |
Weight of the edge (
|
|
|
|
ANY-INTEGER |
-1 |
Weight of the edge (
|
Where:
- ANY-INTEGER :
-
SMALLINT,INTEGER,BIGINT - ANY-NUMERICAL :
-
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
Combinations SQL
|
Parameter |
Type |
Description |
|---|---|---|
|
|
ANY-INTEGER |
Identifier of the departure vertex. |
|
|
ANY-INTEGER |
Identifier of the arrival vertex. |
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
(
|
Additional Examples
- 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)
See Also
Indices and tables