pgr_withPointsVia - Proposed

pgr_withPointsVia - Route that goes through a list of vertices and/or points.

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 ANY-INTEGER and ANY-NUMERICAL

    • 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.

images/boost-inside.jpeg

Boost Graph Inside

Availability

  • Version 3.4.0

    • New proposed function pgr_withPointsVia ( One Via )

Description

Given a graph, a set of points on the graphs edges and a list of vertices, this function is equivalent to finding the shortest path between \(vertex_i\) and \(vertex_{i+1}\) (where \(vertex\) can be a vertex or a point on the graph) for all \(i < size\_of(via\;vertices)\) .

Route :

is a sequence of paths.

Path :

is a section of the route.

The general algorithm is as follows:

  • Build the Graph with the new points.

    • The points identifiers will be converted to negative values.

    • The vertices identifiers will remain positive.

  • Execute a pgr_dijkstraVia - Proposed .

Signatures

One Via

pgr_withPointsVia( Edges SQL , Points SQL , via vertices , [ options ])
options: [directed, strict, U_turn_on_edge]
RETURNS SET OF (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost, route_agg_cost)
OR EMPTY SET
Example :

Find the route that visits the vertices \(\{ -6, 15, -1\}\) in that order on a directed graph. 

SELECT * FROM pgr_withPointsVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  'SELECT pid, edge_id, fraction, side from pointsOfInterest',
  ARRAY[-6, 15, -1]);
 seq  path_id  path_seq  start_vid  end_vid  node  edge  cost  agg_cost  route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1        1         1         -6       15    -6     4   0.3         0               0
   2        1         2         -6       15     7     8     1       0.3             0.3
   3        1         3         -6       15    11     9     1       1.3             1.3
   4        1         4         -6       15    16    16     1       2.3             2.3
   5        1         5         -6       15    15    -1     0       3.3             3.3
   6        2         1         15       -1    15     3     1         0             3.3
   7        2         2         15       -1    10     2     1         1             4.3
   8        2         3         15       -1     6     1   0.6         2             5.3
   9        2         4         15       -1    -1    -2     0       2.6             5.9
(9 rows)

Parameters

Parameter

Type

Default

Description

Edges SQL

TEXT

SQL query as described.

Points SQL

TEXT

SQL query as described.

via vertices

ARRAY [ ANY-INTEGER ]

Array of ordered vertices identifiers that are going to be visited.

  • When positive it is considered a vertex identifier

  • When negative it is considered a point identifier

Where:

ANY-INTEGER :

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL :

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Optional parameters

Column

Type

Default

Description

directed

BOOLEAN

true

  • When true the graph is considered Directed

  • When false the graph is considered as Undirected .

Via optional parameters

Parameter

Type

Default

Description

strict

BOOLEAN

false

  • When true if a path is missing stops and returns EMPTY SET

  • When false ignores missing paths returning all paths found

U_turn_on_edge

BOOLEAN

true

  • When true departing from a visited vertex will not try to avoid

With points optional parameters

Parameter

Type

Default

Description

driving_side

CHAR

b

Value in [ r , l , b ] indicating if the driving side is:

  • r for right driving side.

  • l for left driving side.

  • b for both.

details

BOOLEAN

false

  • When true the results will include the points that are in the path.

  • When false the results will not include the points that are in the path.

Inner Queries

Edges SQL

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 )

  • When negative: edge ( target , source ) does not exist, therefore it’s not part of the graph.

Where:

ANY-INTEGER :

SMALLINT , INTEGER , BIGINT

ANY-NUMERICAL :

SMALLINT , INTEGER , BIGINT , REAL , FLOAT

Points SQL

Parameter

Type

Default

Description

pid

ANY-INTEGER

value

Identifier of the point.

  • Use with positive value, as internally will be converted to negative value

  • If column is present, it can not be NULL.

  • If column is not present, a sequential negative value will be given automatically.

edge_id

ANY-INTEGER

Identifier of the "closest" edge to the point.

fraction

ANY-NUMERICAL

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

side

CHAR

b

Value in [ b , r , l , NULL ] indicating if the point is:

  • In the right r ,

  • In the left l ,

  • In both sides b , NULL

Where:

ANY-INTEGER :

SMALLINT , INTEGER , BIGINT

ANY-NUMERICAL :

SMALLINT , INTEGER , BIGINT , REAL , FLOAT

Result Columns

Column

Type

Description

seq

INTEGER

Sequential value starting from 1 .

path_id

INTEGER

Identifier of a path. Has value 1 for the first path.

path_seq

INTEGER

Relative position in the path. Has value 1 for the beginning of a path.

start_vid

BIGINT

Identifier of the starting vertex of the path.

end_vid

BIGINT

Identifier of the ending vertex of the path.

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.

  • -2 for the last node of the route.

cost

FLOAT

Cost to traverse from node using edge to the next node in the path sequence.

agg_cost

FLOAT

Aggregate cost from start_vid to node .

route_agg_cost

FLOAT

Total cost from start_vid of seq = 1 to end_vid of the current seq .

Note

When start_vid , end_vid and node columns have negative values, the identifier is for a Point.

Additional Examples

Use pgr_findCloseEdges in the Points SQL

Visit from vertex \(1\) to the two locations on the graph of point (2.9, 1.8) in order of closeness to the graph. 

SELECT * FROM pgr_withPointsVia(
  $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[1, -1, -2], details => true);
 seq  path_id  path_seq  start_vid  end_vid  node  edge  cost  agg_cost  route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1        1         1          1       -1     1     6     1         0               0
   2        1         2          1       -1     3     7     1         1               1
   3        1         3          1       -1     7     8   0.9         2               2
   4        1         4          1       -1    -2     8   0.1       2.9             2.9
   5        1         5          1       -1    11     9     1         3               3
   6        1         6          1       -1    16    16     1         4               4
   7        1         7          1       -1    15     3     1         5               5
   8        1         8          1       -1    10     5   0.8         6               6
   9        1         9          1       -1    -1    -1     0       6.8             6.8
  10        2         1         -1       -2    -1     5   0.2         0             6.8
  11        2         2         -1       -2    11     8   0.1       0.2               7
  12        2         3         -1       -2    -2    -2     0       0.3             7.1
(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) .

  • Point \(-2\) is visited on the route to from vertex \(1\) to Point \(-1\) (See row where \(seq = 4\) ).

Usage variations

All this examples are about the route that visits the vertices \(\{-1, 7, -3, 16, 15\}\) in that order on a directed graph. 

SELECT * FROM pgr_withPointsVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  'SELECT pid, edge_id, fraction, side from pointsOfInterest',
  ARRAY[-1, 7, -3, 16, 15]);
 seq  path_id  path_seq  start_vid  end_vid  node  edge  cost  agg_cost  route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1        1         1         -1        7    -1     1   0.6         0               0
   2        1         2         -1        7     6     4     1       0.6             0.6
   3        1         3         -1        7     7    -1     0       1.6             1.6
   4        2         1          7       -3     7    10     1         0             1.6
   5        2         2          7       -3     8    12   0.6         1             2.6
   6        2         3          7       -3    -3    -1     0       1.6             3.2
   7        3         1         -3       16    -3    12   0.4         0             3.2
   8        3         2         -3       16    12    13     1       0.4             3.6
   9        3         3         -3       16    17    15     1       1.4             4.6
  10        3         4         -3       16    16    -1     0       2.4             5.6
  11        4         1         16       15    16    16     1         0             5.6
  12        4         2         16       15    15    -2     0         1             6.6
(12 rows)
Aggregate cost of the third path. 
SELECT agg_cost FROM  pgr_withPointsVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  'SELECT pid, edge_id, fraction, side from pointsOfInterest',
  ARRAY[-1, 7, -3, 16, 15])
WHERE path_id = 3 AND edge < 0;
 agg_cost
----------
      2.4
(1 row)
Route’s aggregate cost of the route at the end of the third path. 
SELECT route_agg_cost FROM  pgr_withPointsVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  'SELECT pid, edge_id, fraction, side from pointsOfInterest',
  ARRAY[-1, 7, -3, 16, 15])
WHERE path_id = 3 AND edge < 0;
 route_agg_cost
----------------
            5.6
(1 row)
Nodes visited in the route. 
SELECT row_number() over () as node_seq, node
FROM  pgr_withPointsVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  'SELECT pid, edge_id, fraction, side from pointsOfInterest',
  ARRAY[-1, 7, -3, 16, 15])
WHERE edge <> -1 ORDER BY seq;
 node_seq  node
----------+------
        1    -1
        2     6
        3     7
        4     8
        5    -3
        6    12
        7    17
        8    16
        9    15
(9 rows)
The aggregate costs of the route when the visited vertices are reached. 
SELECT path_id, route_agg_cost FROM  pgr_withPointsVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  'SELECT pid, edge_id, fraction, side from pointsOfInterest',
  ARRAY[-1, 7, -3, 16, 15])
WHERE edge < 0;
 path_id  route_agg_cost
---------+----------------
       1             1.6
       2             3.2
       3             5.6
       4             6.6
(4 rows)
Status of "passes in front" or "visits" of the nodes and points. 
SELECT seq, node,
CASE WHEN edge = -1 THEN 'visits'
ELSE 'passes in front'
END as status
FROM  pgr_withPointsVia(
  'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
  'SELECT pid, edge_id, fraction, side from pointsOfInterest',
  ARRAY[-1, 7, -3, 16, 15], details => true)
WHERE agg_cost <> 0 or seq = 1;
 seq  node      status
-----+------+-----------------
   1    -1  passes in front
   2     6  passes in front
   3    -6  passes in front
   4     7  visits
   6     8  passes in front
   7    -3  visits
   9    12  passes in front
  10    17  passes in front
  11    -2  passes in front
  12    16  visits
  14    15  passes in front
(11 rows)

See Also

Indices and tables