pgr_edgeDisjointPaths
— Calculates edge disjoint paths between two groups of vertices.
Availability: 2.3.0
Warning
Experimental functions
Calculates the edge disjoint paths between two groups of vertices. Utilizes underlying maximum flow algorithms to calculate the paths.
pgr_edgeDisjointPaths(edges_sql, start_vid, end_vid)
pgr_edgeDisjointPaths(edges_sql, start_vid, end_vid, directed)
pgr_edgeDisjointPaths(edges_sql, start_vid, end_vids, directed)
pgr_edgeDisjointPaths(edges_sql, start_vids, end_vid, directed)
pgr_edgeDisjointPaths(edges_sql, start_vids, end_vids, directed)
RETURNS SET OF (seq, path_id, path_seq, [start_vid,] [end_vid,] node, edge, cost, agg_cost)
OR EMPTY SET
pgr_edgeDisjointPaths(edges_sql, start_vid, end_vid)
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET
The minimal use is for a directed graph from one start_vid
to one end_vid
.
Example: |
---|
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
3, 5
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 3 | 2 | 1 | 0
2 | 1 | 2 | 2 | 4 | 1 | 1
3 | 1 | 3 | 5 | -1 | 0 | 2
4 | 2 | 1 | 3 | 5 | 1 | 0
5 | 2 | 2 | 6 | 8 | 1 | 1
6 | 2 | 3 | 5 | -1 | 0 | 2
(6 rows)
start_vid
to one end_vid
:directed
flag is missing or is set to true
.directed
flag is set to false
.pgr_edgeDisjointPaths(edges_sql, start_vid, end_vid, directed)
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET
Example: |
---|
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
3, 5,
directed := false
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 3 | 2 | 1 | 0
2 | 1 | 2 | 2 | 4 | 1 | 1
3 | 1 | 3 | 5 | -1 | 0 | 2
4 | 2 | 1 | 3 | 3 | -1 | 0
5 | 2 | 2 | 4 | 16 | 1 | -1
6 | 2 | 3 | 9 | 9 | 1 | 0
7 | 2 | 4 | 6 | 8 | 1 | 1
8 | 2 | 5 | 5 | -1 | 0 | 2
9 | 3 | 1 | 3 | 5 | 1 | 0
10 | 3 | 2 | 6 | 11 | 1 | 1
11 | 3 | 3 | 11 | 12 | -1 | 2
12 | 3 | 4 | 10 | 10 | 1 | 1
13 | 3 | 5 | 5 | -1 | 0 | 2
(13 rows)
start_vid
to each one of the end_vid
in end_vids
:directed
flag is missing or is set to true
.directed
flag is set to false
.end_vid
in the result is used to distinguish to which path it belongs.pgr_edgeDisjointPaths(edges_sql, start_vid, end_vids, directed)
RETURNS SET OF (seq, path_id, path_seq, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Example: |
---|
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
3, ARRAY[4, 5, 10]
);
seq | path_id | path_seq | end_vid | node | edge | cost | agg_cost
-----+---------+----------+---------+------+------+------+----------
1 | 1 | 1 | 4 | 3 | 5 | 1 | 0
2 | 1 | 2 | 4 | 6 | 9 | 1 | 1
3 | 1 | 3 | 4 | 9 | 16 | 1 | 2
4 | 1 | 4 | 4 | 4 | -1 | 0 | 3
5 | 2 | 1 | 5 | 3 | 2 | 1 | 0
6 | 2 | 2 | 5 | 2 | 4 | 1 | 1
7 | 2 | 3 | 5 | 5 | -1 | 0 | 2
8 | 3 | 1 | 5 | 3 | 5 | 1 | 0
9 | 3 | 2 | 5 | 6 | 8 | 1 | 1
10 | 3 | 3 | 5 | 5 | -1 | 0 | 2
11 | 4 | 1 | 10 | 3 | 2 | 1 | 0
12 | 4 | 2 | 10 | 2 | 4 | 1 | 1
13 | 4 | 3 | 10 | 5 | 10 | 1 | 2
14 | 4 | 4 | 10 | 10 | -1 | 0 | 3
(14 rows)
start_vid
in start_vids
to the end_vid
:directed
flag is missing or is set to true
.directed
flag is set to false
.start_vid
in the result is used to distinguish to which path it belongs.pgr_edgeDisjointPaths(edges_sql, start_vids, end_vid, directed)
RETURNS SET OF (seq, path_id, path_seq, start_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Example: |
---|
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[3, 6], 5
);
seq | path_id | path_seq | start_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+------+------+------+----------
1 | 1 | 1 | 0 | 3 | 2 | 1 | 0
2 | 1 | 2 | 0 | 2 | 4 | 1 | 1
3 | 1 | 3 | 0 | 5 | -1 | 0 | 2
4 | 2 | 1 | 1 | 3 | 5 | 1 | 0
5 | 2 | 2 | 1 | 6 | 8 | 1 | 1
6 | 2 | 3 | 1 | 5 | -1 | 0 | 2
7 | 3 | 1 | 2 | 6 | 8 | 1 | 0
8 | 3 | 2 | 2 | 5 | -1 | 0 | 1
9 | 4 | 1 | 3 | 6 | 9 | 1 | 0
10 | 4 | 2 | 3 | 9 | 16 | 1 | 1
11 | 4 | 3 | 3 | 4 | 3 | 1 | 2
12 | 4 | 4 | 3 | 3 | 2 | 1 | 3
13 | 4 | 5 | 3 | 2 | 4 | 1 | 4
14 | 4 | 6 | 3 | 5 | -1 | 0 | 5
(14 rows)
start_vid
in start_vids
to each one of the end_vid
in end_vids
:directed
flag is missing or is set to true
.directed
flag is set to false
.start_vid
and end_vid
in the result is used to distinguish to which path it belongs.pgr_edgeDisjointPaths(edges_sql, start_vids, end_vids, directed)
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Example: |
---|
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[3, 6], ARRAY[4, 5, 10]
);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 0 | 4 | 3 | 5 | 1 | 0
2 | 1 | 2 | 0 | 4 | 6 | 9 | 1 | 1
3 | 1 | 3 | 0 | 4 | 9 | 16 | 1 | 2
4 | 1 | 4 | 0 | 4 | 4 | -1 | 0 | 3
5 | 2 | 1 | 1 | 5 | 3 | 2 | 1 | 0
6 | 2 | 2 | 1 | 5 | 2 | 4 | 1 | 1
7 | 2 | 3 | 1 | 5 | 5 | -1 | 0 | 2
8 | 3 | 1 | 2 | 5 | 3 | 5 | 1 | 0
9 | 3 | 2 | 2 | 5 | 6 | 8 | 1 | 1
10 | 3 | 3 | 2 | 5 | 5 | -1 | 0 | 2
11 | 4 | 1 | 3 | 10 | 3 | 2 | 1 | 0
12 | 4 | 2 | 3 | 10 | 2 | 4 | 1 | 1
13 | 4 | 3 | 3 | 10 | 5 | 10 | 1 | 2
14 | 4 | 4 | 3 | 10 | 10 | -1 | 0 | 3
15 | 5 | 1 | 4 | 4 | 6 | 9 | 1 | 0
16 | 5 | 2 | 4 | 4 | 9 | 16 | 1 | 1
17 | 5 | 3 | 4 | 4 | 4 | -1 | 0 | 2
18 | 6 | 1 | 5 | 5 | 6 | 8 | 1 | 0
19 | 6 | 2 | 5 | 5 | 5 | -1 | 0 | 1
20 | 7 | 1 | 6 | 5 | 6 | 9 | 1 | 0
21 | 7 | 2 | 6 | 5 | 9 | 16 | 1 | 1
22 | 7 | 3 | 6 | 5 | 4 | 3 | 1 | 2
23 | 7 | 4 | 6 | 5 | 3 | 2 | 1 | 3
24 | 7 | 5 | 6 | 5 | 2 | 4 | 1 | 4
25 | 7 | 6 | 6 | 5 | 5 | -1 | 0 | 5
26 | 8 | 1 | 7 | 10 | 6 | 8 | 1 | 0
27 | 8 | 2 | 7 | 10 | 5 | 10 | 1 | 1
28 | 8 | 3 | 7 | 10 | 10 | -1 | 0 | 2
(28 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. | |
cost | ANY-NUMERICAL |
Weight of the edge (source, target)
|
|
reverse_cost | ANY-NUMERICAL |
-1 | Weight of the edge (target, source),
|
Where:
ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
---|---|
ANY-NUMERICAL: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT |
Column | Type | Default | Description |
---|---|---|---|
sql | TEXT |
SQL query as described above. | |
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. | |
directed | BOOLEAN |
true |
|
Returns set of (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
Column | Type | Description |
---|---|---|
seq | INT |
Sequential value starting from 1. |
path_id | INT |
Path identifier. Has value 1 for the first of a path. Used when there are multiple paths for the same start_vid to end_vid combination. |
path_seq | INT |
Relative position in the path. Has value 1 for the beginning of a path. |
start_vid | BIGINT |
Identifier of the starting vertex. Used when multiple starting vetrices are in the query. |
end_vid | BIGINT |
Identifier of the ending vertex. Used when multiple ending vertices are in the query. |
node | BIGINT |
Identifier of the node in the path from start_vid to end_vid . |
edge | BIGINT |
Identifier of the edge used to go from node to the next node in the path sequence. -1 for the last node of the path. |
cost | FLOAT |
Cost to traverse from node using edge to the next node in the path sequence. |
agg_cost | FLOAT |
Aggregate cost from start_v to node . |