pgr_maxFlowPushRelabel Proposed¶
Name¶
pgr_maxFlowPushRelabel — Calculates the maximum flow in a directed graph given a source and a destination.
Warning
These are proposed functions
- They are not officially of the current release.
- They likely will not be officially be part of the next release:
- The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
- Name might change.
- Signature might change.
- Functionality might change.
- pgTap tests might be missing.
- Might need c/c++ coding.
- May lack documentation.
- Documentation if any might need to be rewritten.
- Documentation examples might need to be automatically generated.
- Might need a lot of feedback from the comunity.
- Might depend on a proposed function of pgRouting
- Might depend on a deprecated function of pgRouting
Synopsis¶
Calculates the maximum flow in a directed graph from a source node to a sink node. Edges must be weighted with non-negative capacities.
Characteristics:¶
- The main characterics are:
- Calculates the flow/residual capacity for each edge. In the output, edges with zero flow are omitted.
- The maximum flow through the graph can be calculated by aggregation on source/sink.
- Returns nothing if source and sink are the same.
- Allows multiple sources and sinks.
- Running time: \(O( V ^ 3)\)
Signature Summary¶
pgr_maxFlowPushRelabel(edges_sql, source_vertex, sink_vertex)
pgr_maxFlowPushRelabel(edges_sql, source_vertices, sink_vertex)
pgr_maxFlowPushRelabel(edges_sql, source_vertex, sink_vertices)
pgr_maxFlowPushRelabel(edges_sql, source_vertices, sink_vertices)
RETURNS SET OF (id, edge_id, source, target, flow, residual_capacity)
OR EMPTY SET
Signatures¶
One to One¶
Calculates the maximum flow from one source vertex to one sink vertex in a directed graph.
pgr_maxFlowPushRelabel(edges_sql, source_vertex, sink_vertex)
RETURNS SET OF (id, edge_id, source, target, flow, residual_capacity)
OR EMPTY SET
Example: |
---|
SELECT * FROM pgr_maxFlowPushRelabel(
'SELECT id,
source,
target,
c1.capacity as capacity,
c2.capacity as reverse_capacity
FROM edge_table JOIN categories AS c1 USING(category_id), categories AS c2
WHERE edge_table.reverse_category_id = c2.category_id
ORDER BY id'
, 6, 11
);
seq | edge_id | source | target | flow | residual_capacity
-----+---------+--------+--------+------+-------------------
1 | 10 | 5 | 10 | 100 | 30
2 | 8 | 6 | 5 | 100 | 30
3 | 9 | 6 | 9 | 50 | 80
4 | 11 | 6 | 11 | 130 | 0
5 | 15 | 9 | 12 | 50 | 30
6 | 12 | 10 | 11 | 100 | 0
7 | 13 | 12 | 11 | 50 | 0
(7 rows)
One to Many¶
Ccalculates the maximum flow from one source vertex to many sink vertices in a directed graph.
pgr_maxFlowPushRelabel(edges_sql, source_vertex, sink_vertices)
RETURNS SET OF (id, edge_id, source, target, flow, residual_capacity)
OR EMPTY SET
Example: |
---|
SELECT * FROM pgr_maxFlowPushRelabel(
'SELECT id,
source,
target,
c1.capacity as capacity,
c2.capacity as reverse_capacity
FROM edge_table JOIN categories AS c1 USING(category_id), categories AS c2
WHERE edge_table.reverse_category_id = c2.category_id
ORDER BY id'
, 6, ARRAY[11, 1, 13]
);
seq | edge_id | source | target | flow | residual_capacity
-----+---------+--------+--------+------+-------------------
1 | 1 | 2 | 1 | 130 | 0
2 | 4 | 2 | 5 | 20 | 80
3 | 2 | 3 | 2 | 100 | 0
4 | 3 | 4 | 3 | 50 | 80
5 | 4 | 5 | 2 | 50 | 0
6 | 7 | 5 | 8 | 50 | 80
7 | 10 | 5 | 10 | 100 | 30
8 | 5 | 6 | 3 | 50 | 0
9 | 8 | 6 | 5 | 130 | 0
10 | 9 | 6 | 9 | 100 | 30
11 | 11 | 6 | 11 | 130 | 0
12 | 6 | 7 | 8 | 50 | 0
13 | 6 | 8 | 7 | 50 | 50
14 | 7 | 8 | 5 | 50 | 0
15 | 15 | 9 | 12 | 50 | 30
16 | 16 | 9 | 4 | 50 | 30
17 | 12 | 10 | 11 | 100 | 0
18 | 13 | 12 | 11 | 50 | 0
(18 rows)
Many to One¶
Calculates the maximum flow from many source vertices to one sink vertex in a directed graph.
pgr_maxFlowPushRelabel(edges_sql, source_vertices, sink_vertex)
RETURNS SET OF (id, edge_id, source, target, flow, residual_capacity)
OR EMPTY SET
Example: |
---|
SELECT * FROM pgr_maxFlowPushRelabel(
'SELECT id,
source,
target,
c1.capacity as capacity,
c2.capacity as reverse_capacity
FROM edge_table JOIN categories AS c1 USING(category_id), categories AS c2
WHERE edge_table.reverse_category_id = c2.category_id
ORDER BY id'
, ARRAY[6, 8, 12], 11
);
seq | edge_id | source | target | 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
5 | 13 | 12 | 11 | 50 | 0
(5 rows)
Many to Many¶
Calculates the maximum flow from many sources to many sinks in a directed graph.
pgr_maxFlowPushRelabel(edges_sql, source_vertices, sink_vertices)
RETURNS SET OF (id, edge_id, source, target, flow, residual_capacity)
OR EMPTY SET
Example: |
---|
SELECT * FROM pgr_maxFlowPushRelabel(
'SELECT id,
source,
target,
c1.capacity as capacity,
c2.capacity as reverse_capacity
FROM edge_table JOIN categories AS c1 USING(category_id), categories AS c2
WHERE edge_table.reverse_category_id = c2.category_id
ORDER BY id'
, ARRAY[6, 8, 12], ARRAY[1, 3, 11]
);
seq | edge_id | source | target | 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 | 5 | 6 | 3 | 50 | 0
6 | 8 | 6 | 5 | 130 | 0
7 | 9 | 6 | 9 | 30 | 100
8 | 11 | 6 | 11 | 130 | 0
9 | 7 | 8 | 5 | 20 | 30
10 | 16 | 9 | 4 | 80 | 0
11 | 12 | 10 | 11 | 100 | 0
12 | 13 | 12 | 11 | 50 | 0
13 | 15 | 12 | 9 | 50 | 0
(13 rows)
Description of the Signatures¶
Description of the SQL query¶
edges_sql: | an SQL query, which should return a set of rows with the following columns: |
---|
Column | Type | 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 | Capacity of the edge (source, target). Must be positive. |
reverse_capacity | ANY-INTEGER | (optional) Weight of the edge (target, source). Must be positive or null. |
Where:
ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
---|
Description of the parameters of the signatures¶
Column | Type | Description |
---|---|---|
edges_sql | TEXT | SQL query as described above. |
source_vertex | BIGINT | Identifier of the source vertex(or vertices). |
sink_vertex | BIGINT | Identifier of the sink vertex(or vertices). |
Description of the Return Values¶
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). |