pgr_boykovKolmogorov
— Calculates the flow on the graph edges that maximizes the flow from the sources to the targets using Boykov Kolmogorov algorithm.
Availability:
Warning
Experimental functions
Characteristics
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
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)
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)
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)
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)
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)
|
|
reverse_capacity | ANY-INTEGER |
-1 | Weight of the edge (target, source),
|
Where:
ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
---|
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. |
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). |
Indices and tables