pgr_edgeDisjointPaths¶
pgr_edgeDisjointPaths — Calculates edge disjoint paths between two groups of
vertices.
Boost Graph Inside¶
Availability
Version 3.2.0
New proposed function:
pgr_edgeDisjointPaths(Combinations)
Version 3.0.0
Official function
Version 2.5.0
Proposed function
Version 2.3.0
New Experimental function
Description¶
Calculates the edge disjoint paths between two groups of vertices. Utilizes underlying maximum flow algorithms to calculate the paths.
- The main characterics are:
Calculates the edge disjoint paths between any two groups of vertices.
Returns EMPTY SET when source and destination are the same, or cannot be reached.
The graph can be directed or undirected.
Uses pgr_boykovKolmogorov to calculate the paths.
Signatures¶
Summary
directed])directed])directed])directed])(seq, path_id, path_seq, [start_vid,] [end_vid,] node, edge, cost, agg_cost)One to One¶
directed])(seq, path_id, path_seq, node, edge, cost, agg_cost)- Example:
From vertex \(11\) to vertex \(12\)
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
11, 12);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 11 | 8 | 1 | 0
2 | 1 | 2 | 7 | 10 | 1 | 1
3 | 1 | 3 | 8 | 12 | 1 | 2
4 | 1 | 4 | 12 | -1 | 0 | 3
5 | 2 | 1 | 11 | 11 | 1 | 0
6 | 2 | 2 | 12 | -1 | 0 | 1
(6 rows)
One to Many¶
directed])(seq, path_id, path_seq, end_vid, node, edge, cost, agg_cost)- Example:
From vertex \(11\) to vertices \(\{5, 10, 12\}\)
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
11, ARRAY[5, 10, 12]);
seq | path_id | path_seq | end_vid | node | edge | cost | agg_cost
-----+---------+----------+---------+------+------+------+----------
1 | 1 | 1 | 5 | 11 | 8 | 1 | 0
2 | 1 | 2 | 5 | 7 | 4 | 1 | 1
3 | 1 | 3 | 5 | 6 | 1 | 1 | 2
4 | 1 | 4 | 5 | 5 | -1 | 0 | 3
5 | 2 | 1 | 10 | 11 | 9 | 1 | 0
6 | 2 | 2 | 10 | 16 | 16 | 1 | 1
7 | 2 | 3 | 10 | 15 | 3 | 1 | 2
8 | 2 | 4 | 10 | 10 | -1 | 0 | 3
9 | 3 | 1 | 12 | 11 | 8 | 1 | 0
10 | 3 | 2 | 12 | 7 | 10 | 1 | 1
11 | 3 | 3 | 12 | 8 | 12 | 1 | 2
12 | 3 | 4 | 12 | 12 | -1 | 0 | 3
13 | 4 | 1 | 12 | 11 | 11 | 1 | 0
14 | 4 | 2 | 12 | 12 | -1 | 0 | 1
(14 rows)
Many to One¶
directed])(seq, path_id, path_seq, start_vid, node, edge, cost, agg_cost)- Example:
From vertices \(\{11, 3, 17\}\) to vertex \(12\)
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
ARRAY[11, 3, 17], 12);
seq | path_id | path_seq | start_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+------+------+------+----------
1 | 1 | 1 | 3 | 3 | 7 | 1 | 0
2 | 1 | 2 | 3 | 7 | 8 | 1 | 1
3 | 1 | 3 | 3 | 11 | 11 | 1 | 2
4 | 1 | 4 | 3 | 12 | -1 | 0 | 3
5 | 2 | 1 | 11 | 11 | 8 | 1 | 0
6 | 2 | 2 | 11 | 7 | 10 | 1 | 1
7 | 2 | 3 | 11 | 8 | 12 | 1 | 2
8 | 2 | 4 | 11 | 12 | -1 | 0 | 3
9 | 3 | 1 | 11 | 11 | 11 | 1 | 0
10 | 3 | 2 | 11 | 12 | -1 | 0 | 1
11 | 4 | 1 | 17 | 17 | 15 | 1 | 0
12 | 4 | 2 | 17 | 16 | 9 | 1 | 1
13 | 4 | 3 | 17 | 11 | 11 | 1 | 2
14 | 4 | 4 | 17 | 12 | -1 | 0 | 3
(14 rows)
Many to Many¶
directed])(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- Example:
From vertices \(\{11, 3, 17\}\) to vertices \(\{5, 10, 12\}\)
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
ARRAY[11, 3, 17], ARRAY[5, 10, 12]);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 3 | 5 | 3 | 7 | 1 | 0
2 | 1 | 2 | 3 | 5 | 7 | 4 | 1 | 1
3 | 1 | 3 | 3 | 5 | 6 | 1 | 1 | 2
4 | 1 | 4 | 3 | 5 | 5 | -1 | 0 | 3
5 | 2 | 1 | 3 | 10 | 3 | 7 | 1 | 0
6 | 2 | 2 | 3 | 10 | 7 | 8 | 1 | 1
7 | 2 | 3 | 3 | 10 | 11 | 9 | 1 | 2
8 | 2 | 4 | 3 | 10 | 16 | 16 | 1 | 3
9 | 2 | 5 | 3 | 10 | 15 | 3 | 1 | 4
10 | 2 | 6 | 3 | 10 | 10 | -1 | 0 | 5
11 | 3 | 1 | 3 | 12 | 3 | 7 | 1 | 0
12 | 3 | 2 | 3 | 12 | 7 | 8 | 1 | 1
13 | 3 | 3 | 3 | 12 | 11 | 11 | 1 | 2
14 | 3 | 4 | 3 | 12 | 12 | -1 | 0 | 3
15 | 4 | 1 | 11 | 5 | 11 | 8 | 1 | 0
16 | 4 | 2 | 11 | 5 | 7 | 4 | 1 | 1
17 | 4 | 3 | 11 | 5 | 6 | 1 | 1 | 2
18 | 4 | 4 | 11 | 5 | 5 | -1 | 0 | 3
19 | 5 | 1 | 11 | 10 | 11 | 9 | 1 | 0
20 | 5 | 2 | 11 | 10 | 16 | 16 | 1 | 1
21 | 5 | 3 | 11 | 10 | 15 | 3 | 1 | 2
22 | 5 | 4 | 11 | 10 | 10 | -1 | 0 | 3
23 | 6 | 1 | 11 | 12 | 11 | 8 | 1 | 0
24 | 6 | 2 | 11 | 12 | 7 | 10 | 1 | 1
25 | 6 | 3 | 11 | 12 | 8 | 12 | 1 | 2
26 | 6 | 4 | 11 | 12 | 12 | -1 | 0 | 3
27 | 7 | 1 | 11 | 12 | 11 | 11 | 1 | 0
28 | 7 | 2 | 11 | 12 | 12 | -1 | 0 | 1
29 | 8 | 1 | 17 | 5 | 17 | 15 | 1 | 0
30 | 8 | 2 | 17 | 5 | 16 | 16 | 1 | 1
31 | 8 | 3 | 17 | 5 | 15 | 3 | 1 | 2
32 | 8 | 4 | 17 | 5 | 10 | 2 | 1 | 3
33 | 8 | 5 | 17 | 5 | 6 | 1 | 1 | 4
34 | 8 | 6 | 17 | 5 | 5 | -1 | 0 | 5
35 | 9 | 1 | 17 | 10 | 17 | 15 | 1 | 0
36 | 9 | 2 | 17 | 10 | 16 | 16 | 1 | 1
37 | 9 | 3 | 17 | 10 | 15 | 3 | 1 | 2
38 | 9 | 4 | 17 | 10 | 10 | -1 | 0 | 3
39 | 10 | 1 | 17 | 12 | 17 | 15 | 1 | 0
40 | 10 | 2 | 17 | 12 | 16 | 9 | 1 | 1
41 | 10 | 3 | 17 | 12 | 11 | 11 | 1 | 2
42 | 10 | 4 | 17 | 12 | 12 | -1 | 0 | 3
(42 rows)
Combinations¶
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- Example:
Using a combinations table, equivalent to calculating result from vertices \(\{5, 6\}\) to vertices \(\{10, 15, 14\}\) on an undirected graph.
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_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
'SELECT * FROM combinations WHERE target NOT IN (5, 6)',
directed => false);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 5 | 10 | 5 | 1 | 1 | 0
2 | 1 | 2 | 5 | 10 | 6 | 2 | -1 | 1
3 | 1 | 3 | 5 | 10 | 10 | -1 | 0 | 0
4 | 2 | 1 | 6 | 15 | 6 | 4 | 1 | 0
5 | 2 | 2 | 6 | 15 | 7 | 8 | 1 | 1
6 | 2 | 3 | 6 | 15 | 11 | 9 | 1 | 2
7 | 2 | 4 | 6 | 15 | 16 | 16 | 1 | 3
8 | 2 | 5 | 6 | 15 | 15 | -1 | 0 | 4
9 | 3 | 1 | 6 | 15 | 6 | 2 | -1 | 0
10 | 3 | 2 | 6 | 15 | 10 | 3 | -1 | -1
11 | 3 | 3 | 6 | 15 | 15 | -1 | 0 | -2
(11 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. |
Optional parameters¶
Column |
Type |
Default |
Description |
|---|---|---|---|
|
|
|
|
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-NUMERICAL |
Weight of the edge ( |
|
|
ANY-NUMERICAL |
-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¶
Set of (seq, path_id, path_seq [, start_vid] [, end_vid], node, edge, cost,
agg_cost)
Column |
Type |
Description |
|---|---|---|
|
|
Sequential value starting from 1. |
|
|
Path identifier.
|
|
|
Relative position in the path. Has value 1 for the beginning of a path. |
|
|
Identifier of the starting vertex. Returned when multiple starting vetrices are in the query. |
|
|
Identifier of the ending vertex. Returned when multiple ending vertices are in the query. |
|
|
Identifier of the node in the path from |
|
|
Identifier of the edge used to go from |
|
|
Cost to traverse from |
|
|
Aggregate cost from |
Additional Examples¶
- Example:
Manually assigned vertex combinations on an undirected graph.
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
'SELECT * FROM (VALUES (5, 10), (6, 15), (6, 14)) AS t(source, target)',
directed => false);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 5 | 10 | 5 | 1 | 1 | 0
2 | 1 | 2 | 5 | 10 | 6 | 2 | -1 | 1
3 | 1 | 3 | 5 | 10 | 10 | -1 | 0 | 0
4 | 2 | 1 | 6 | 15 | 6 | 4 | 1 | 0
5 | 2 | 2 | 6 | 15 | 7 | 8 | 1 | 1
6 | 2 | 3 | 6 | 15 | 11 | 9 | 1 | 2
7 | 2 | 4 | 6 | 15 | 16 | 16 | 1 | 3
8 | 2 | 5 | 6 | 15 | 15 | -1 | 0 | 4
9 | 3 | 1 | 6 | 15 | 6 | 2 | -1 | 0
10 | 3 | 2 | 6 | 15 | 10 | 3 | -1 | -1
11 | 3 | 3 | 6 | 15 | 15 | -1 | 0 | -2
(11 rows)
See Also¶
Indices and tables