pgr_withPointsCostMatrix
 proposed¶
pgr_withPointsCostMatrix
 Calculates a cost matrix using
pgr_withPoints  Proposed.
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¶
Using Dijkstra algorithm, calculate and return a cost matrix.
Dijkstra’s algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956. It is a graph search algorithm that solves the shortest path problem for a graph with nonnegative edge path costs, producing a shortest path from a starting vertex to an ending vertex. This implementation can be used with a directed graph and an undirected graph.
The main Characteristics are:
Can be used as input to pgr_TSP.
Use directly when the resulting matrix is symmetric and there is no \(\infty\) value.
It will be the users responsibility to make the matrix symmetric.
By using geometric or harmonic average of the non symmetric values.
By using max or min the non symmetric values.
By setting the upper triangle to be the mirror image of the lower triangle.
By setting the lower triangle to be the mirror image of the upper triangle.
It is also the users responsibility to fix an \(\infty\) value.
Each function works as part of the family it belongs to.
It does not return a path.
Returns the sum of the costs of the shortest path for pair combination of nodes in the graph.
Process is done only on edges with positive costs.
Values are returned when there is a path.
When the starting vertex and ending vertex are the same, there is no path.
The aggregate cost in the non included values (v, v) is 0.
When the starting vertex and ending vertex are the different and there is no path.
The aggregate cost in the non included values (u, v) is \(\infty\).
Let be the case the values returned are stored in a table:
The unique index would be the pair:
(start_vid, end_vid)
.
Depending on the function and its parameters, the results can be symmetric.
The aggregate cost of (u, v) is the same as for (v, u).
Any duplicated value in the start vids are ignored.
The returned values are ordered:
start_vid
ascendingend_vid
ascending
Signatures¶
Summary
[directed, driving_side]
(start_vid, end_vid, agg_cost)
Note
There is no details flag, unlike the other members of the withPoints family of functions.
 Example:
Cost matrix for points \(\{1, 6\}\) and vertices \(\{10, 11\}\) on an undirected graph
Returning a symmetrical cost matrix
Using the default
side
value on the points_sql queryUsing the default
driving_side
value
SELECT * FROM pgr_withPointsCostMatrix(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction from pointsOfInterest',
array[1, 10, 11, 6], directed := false);
start_vid  end_vid  agg_cost
++
6  1  1.3
6  10  1.7
6  11  1.3
1  6  1.3
1  10  1.6
1  11  2.6
10  6  1.7
10  1  1.6
10  11  1
11  6  1.3
11  1  2.6
11  10  1
(12 rows)
Parameters¶
Column 
Type 
Description 


Edges SQL as described below 


Points SQL as described below 

start vids 

Array of identifiers of starting vertices. 
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¶
Set of (start_vid, end_vid, agg_cost)
Column 
Type 
Description 



Identifier of the starting vertex. 


Identifier of the ending vertex. 


Aggregate cost from 
Note
When start_vid or end_vid columns have negative values, the identifier is for a Point.
Additional Examples¶
Use pgr_findCloseEdges in the Points SQL.¶
Find the matrix cost of the routes from vertex \(1\) and the two closest locations on the graph of point (2.9, 1.8).
SELECT * FROM pgr_withPointsCostMatrix(
$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$,
ARRAY[5, 10, 1, 2]);
start_vid  end_vid  agg_cost
++
2  1  3.9
2  5  2.9
2  10  3.1
1  2  0.3
1  5  3.2
1  10  3.2
5  2  2.9
5  1  6.8
5  10  6
10  2  1.1
10  1  0.8
10  5  2
(12 rows)
Point \(1\) corresponds to the closest edge from point (2.9, 1.8).
Point \(2\) corresponds to the next close edge from point (2.9, 1.8).
Use with pgr_TSP.¶
SELECT * FROM pgr_TSP(
$$
SELECT * FROM pgr_withPointsCostMatrix(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
'SELECT pid, edge_id, fraction from pointsOfInterest',
array[1, 10, 11, 6], directed := false);
$$
);
NOTICE: pgr_TSP no longer solving with simulated annaeling
HINT: Ignoring annaeling parameters
seq  node  cost  agg_cost
+++
1  6  0  0
2  1  1.3  1.3
3  10  1.6  2.9
4  11  1  3.9
5  6  1.3  5.2
(5 rows)
See Also¶
Indices and tables