pgr_withPointsKSP  Proposed¶
pgr_withPointsKSP
— Yen’s algorithm for K shortest paths using Dijkstra.
Warning
Proposed functions for next mayor release.
They are not officially in the current release.
They will likely officially be part of the next mayor release:
The functions make use of ANYINTEGER and ANYNUMERICAL
Name might not change. (But still can)
Signature might not change. (But still can)
Functionality might not change. (But still can)
pgTap tests have being done. But might need more.
Documentation might need refinement.
Availability
Version 2.2.0
New proposed function
Description¶
Modifies the graph to include the points defined in the Points SQL and using Yen algorithm, finds the \(K\) shortest paths.
Signatures¶
[directed, heap_paths, driving_side, details]
(seq, path_id, path_seq, node, edge, cost, agg_cost)
 Example:
Get 2 paths from Point \(1\) to point \(2\) on a directed graph.
For a directed graph.
The driving side is set as b both. So arriving/departing to/from the point(s) can be in any direction.
No details are given about distance of other points of the query.
No heap paths are returned.
SELECT * FROM pgr_withPointsKSP(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
1, 2, 2);
seq  path_id  path_seq  node  edge  cost  agg_cost
++++++
1  1  1  1  1  0.6  0
2  1  2  6  4  1  0.6
3  1  3  7  8  1  1.6
4  1  4  11  9  1  2.6
5  1  5  16  15  0.4  3.6
6  1  6  2  1  0  4
7  2  1  1  1  0.6  0
8  2  2  6  4  1  0.6
9  2  3  7  8  1  1.6
10  2  4  11  11  1  2.6
11  2  5  12  13  1  3.6
12  2  6  17  15  0.6  4.6
13  2  7  2  1  0  5.2
(13 rows)
Parameters¶
Column 
Type 
Description 


Edges SQL query as described. 


Points SQL query as described. 

start vid 
ANYINTEGER 
Identifier of the departure vertex.

end vid 
ANYINTEGER 
Identifier of the destination vertex.

K 
ANYINTEGER 
Number of required paths 
Where:
 ANYINTEGER:
SMALLINT
,INTEGER
,BIGINT
Optional parameters¶
Column 
Type 
Default 
Description 





KSP Optional parameters¶
Column 
Type 
Default 
Description 





With points optional parameters¶
Parameter 
Type 
Default 
Description 




Value in [





Inner Queries¶
Edges SQL¶
Column 
Type 
Default 
Description 


ANYINTEGER 
Identifier of the edge. 


ANYINTEGER 
Identifier of the first end point vertex of the edge. 


ANYINTEGER 
Identifier of the second end point vertex of the edge. 


ANYNUMERICAL 
Weight of the edge ( 


ANYNUMERICAL 
1 
Weight of the edge (

Where:
 ANYINTEGER:
SMALLINT
,INTEGER
,BIGINT
 ANYNUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Points SQL¶
Parameter 
Type 
Default 
Description 


ANYINTEGER 
value 
Identifier of the point.


ANYINTEGER 
Identifier of the “closest” edge to the point. 


ANYNUMERICAL 
Value in <0,1> that indicates the relative postition from the first end point of the edge. 




Value in [

Where:
 ANYINTEGER:
SMALLINT
,INTEGER
,BIGINT
 ANYNUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Result Columns¶
Returns 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 node in the path from start vid to end vid 


Identifier of the edge used to go from 


Cost to traverse from



Aggregate cost from start vid to 
Additional Examples¶
Use pgr_findCloseEdges in the Points SQL.¶
Get \(2\) paths using left side driving topology, from vertex \(1\) to the closest location on the graph of point (2.9, 1.8).
SELECT * FROM pgr_withPointsKSP(
$e$ SELECT * FROM edges $e$,
$p$ SELECT edge_id, round(fraction::numeric, 2) AS fraction, side
FROM pgr_findCloseEdges(
$$SELECT id, geom FROM edges$$,
(SELECT ST_POINT(2.9, 1.8)),
0.5, cap => 2)
$p$,
1, 1, 2,
driving_side := 'r');
seq  path_id  path_seq  node  edge  cost  agg_cost
++++++
1  1  1  1  6  1  0
2  1  2  3  7  1  1
3  1  3  7  8  1  2
4  1  4  11  9  1  3
5  1  5  16  16  1  4
6  1  6  15  3  1  5
7  1  7  10  5  0.8  6
8  1  8  1  1  0  6.8
9  2  1  1  6  1  0
10  2  2  3  7  1  1
11  2  3  7  10  1  2
12  2  4  8  12  1  3
13  2  5  12  13  1  4
14  2  6  17  15  1  5
15  2  7  16  16  1  6
16  2  8  15  3  1  7
17  2  9  10  5  0.8  8
18  2  10  1  1  0  8.8
(18 rows)
Point \(1\) corresponds to the closest edge from point (2.9,1.8).
Left driving side¶
Get \(2\) paths using left side driving topology, from point \(1\) to point \(2\) with details.
SELECT * FROM pgr_withPointsKSP(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
1, 2, 2,
driving_side := 'l', details := true);
seq  path_id  path_seq  node  edge  cost  agg_cost
++++++
1  1  1  1  1  0.6  0
2  1  2  6  4  0.7  0.6
3  1  3  6  4  0.3  1.3
4  1  4  7  8  1  1.6
5  1  5  11  11  1  2.6
6  1  6  12  13  1  3.6
7  1  7  17  15  0.6  4.6
8  1  8  2  1  0  5.2
9  2  1  1  1  0.6  0
10  2  2  6  4  0.7  0.6
11  2  3  6  4  0.3  1.3
12  2  4  7  8  1  1.6
13  2  5  11  9  1  2.6
14  2  6  16  15  1  3.6
15  2  7  17  15  0.6  4.6
16  2  8  2  1  0  5.2
(16 rows)
Right driving side¶
Get \(2\) paths using right side driving topology from, point \(1\) to point \(2\) with heap paths and details.
SELECT * FROM pgr_withPointsKSP(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction, side from pointsOfInterest',
1, 2, 2,
heap_paths := true, driving_side := 'r', details := true);
seq  path_id  path_seq  node  edge  cost  agg_cost
++++++
1  1  1  1  1  0.4  0
2  1  2  5  1  1  0.4
3  1  3  6  4  0.7  1.4
4  1  4  6  4  0.3  2.1
5  1  5  7  8  1  2.4
6  1  6  11  9  1  3.4
7  1  7  16  15  0.4  4.4
8  1  8  2  1  0  4.8
9  2  1  1  1  0.4  0
10  2  2  5  1  1  0.4
11  2  3  6  4  0.7  1.4
12  2  4  6  4  0.3  2.1
13  2  5  7  8  1  2.4
14  2  6  11  11  1  3.4
15  2  7  12  13  1  4.4
16  2  8  17  15  1  5.4
17  2  9  16  15  0.4  6.4
18  2  10  2  1  0  6.8
19  3  1  1  1  0.4  0
20  3  2  5  1  1  0.4
21  3  3  6  4  0.7  1.4
22  3  4  6  4  0.3  2.1
23  3  5  7  10  1  2.4
24  3  6  8  12  0.6  3.4
25  3  7  3  12  0.4  4
26  3  8  12  13  1  4.4
27  3  9  17  15  1  5.4
28  3  10  16  15  0.4  6.4
29  3  11  2  1  0  6.8
(29 rows)
The queries use the Sample Data network.
See Also¶
Indices and tables