pgr_edgeDisjointPaths - pgRouting Manual (3.0)
pgr_edgeDisjointPaths
pgr_edgeDisjointPaths
- Calculates edge disjoint paths between two groups of vertices.
Availability
-
Version 3.0.0
-
Official function
-
-
Version 2.5.0
-
Proposed function
-
-
Version 2.3.0
-
New Experimental function
-
Support
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.
-
One to many, many to one, many to many versions are also supported.
-
Uses pgr_boykovKolmogorov to calculate the paths.
-
Signatures
Summary
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
Using defaults
pgr_edgeDisjointPaths(Edges SQL, start_vid, end_vid)
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET
- Example :
-
From vertex \(3\) to vertex \(5\) on a directed graph
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)
One to One
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 :
-
From vertex \(3\) to vertex \(5\) on an undirected graph
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)
One to Many
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 :
-
From vertex \(3\) to vertices \(\{4, 5, 10\}\) on a directed graph
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)
Many to One
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 :
-
From vertices \(\{3, 6\}\) to vertex \(5\) on a directed graph
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)
Many to Many
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 :
-
From vertices \(\{3, 6\}\) to vertices \(\{4, 5, 10\}\) on a directed graph
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)
Parameters
|
Parameter |
Type |
Default |
Description |
|---|---|---|---|
|
edges_sql |
|
Inner SQL query 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. |
|
|
directed |
|
|
|
Inner query
|
Column |
Type |
Default |
Description |
|---|---|---|---|
|
id |
|
Identifier of the edge. |
|
|
source |
|
Identifier of the first end point vertex of the edge. |
|
|
target |
|
Identifier of the second end point vertex of the edge. |
|
|
cost |
|
Weight of the edge (source, target)
|
|
|
reverse_cost |
|
-1 |
Weight of the edge (target, source) ,
|
Where:
- ANY-INTEGER :
-
SMALLINT, INTEGER, BIGINT
- ANY-NUMERICAL :
-
SMALLINT, INTEGER, BIGINT, REAL, FLOAT
Return Columns
Returns set of
(seq,
path_id,
path_seq
[,
start_vid]
[,
end_vid],
node,
edge,
cost,
agg_cost)
|
Column |
Type |
Description |
|---|---|---|
|
seq |
|
Sequential value starting from 1 . |
|
path_id |
|
Path identifier. Has value
1
for the first of a path. Used when there are multiple paths for the same
|
|
path_seq |
|
Relative position in the path. Has value 1 for the beginning of a path. |
|
start_vid |
|
Identifier of the starting vertex. Returned when multiple starting vetrices are in the query. |
|
end_vid |
|
Identifier of the ending vertex. Returned when multiple ending vertices are in the query. |
|
node |
|
Identifier of the node in the path from
|
|
edge |
|
Identifier of the edge used to go from
|
|
cost |
|
Cost to traverse from
|
|
agg_cost |
|
Aggregate cost from
|
See Also
Indices and tables