Supported versions: latest (3.8) 3.7 3.6 3.5 3.4 main dev

pgr_withPointsVia

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

Availability

Version 4.0.0

  • Function promoted to official.

  • Driving side parameter is positional unnamed and compulsory.

    • Valid values depend on kind of graph

  • Breaking change, signatures no longer available:

    • pgr_withpointsvia(text,text,anyarray,boolean,boolean,boolean,character,boolean)

Version 3.4.0

  • New proposed function.

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 vertexi and vertexi+1 (where vertex can be a vertex or a point on the graph) for all i<size_of(viavertices).

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.

Boost Graph inside Boost Graph Inside

Signatures

One Via

pgr_withPointsVia(Edges SQL, Points SQL, via vertices, driving side [options])
options: [directed, strict, U_turn_on_edge, details]
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 with right driving side in directed graph..

SELECT * FROM pgr_withPointsVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
  $$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
  ARRAY[-6, 15, -5], 'R');
 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 |      -5 |   15 |    3 |    1 |        0 |            3.3
   7 |       2 |        2 |        15 |      -5 |   10 |    5 |  0.8 |        1 |            4.3
   8 |       2 |        3 |        15 |      -5 |   -5 |   -2 |    0 |      1.8 |            5.1
(8 rows)

Parameters

Parameter

Type

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

driving side

CHAR

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

  • [r, R] for right driving side (for directed graph only)

  • [l, L] for left driving side (for directed graph only)

  • [b, B] for both (only for undirected graph)

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

details

BOOLEAN

false

For showing points stops.

  • 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 position 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], 'r', 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 |    1 |      0.2 |              7
  12 |       2 |        3 |        -1 |      -2 |    7 |    8 |  0.9 |      1.2 |              8
  13 |       2 |        4 |        -1 |      -2 |   -2 |   -2 |    0 |      2.1 |            8.9
(13 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, side, fraction FROM pointsOfInterest$$,
  ARRAY[-6, 7, -4, 8, -2], 'L', directed => true);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |        -6 |       7 |   -6 |    4 |  0.3 |        0 |              0
   2 |       1 |        2 |        -6 |       7 |    7 |   -1 |    0 |      0.3 |            0.3
   3 |       2 |        1 |         7 |      -4 |    7 |    7 |    1 |        0 |            0.3
   4 |       2 |        2 |         7 |      -4 |    3 |    6 |  0.7 |        1 |            1.3
   5 |       2 |        3 |         7 |      -4 |   -4 |   -1 |    0 |      1.7 |              2
   6 |       3 |        1 |        -4 |       8 |   -4 |    6 |  1.3 |        0 |              2
   7 |       3 |        2 |        -4 |       8 |    3 |    7 |    1 |      1.3 |            3.3
   8 |       3 |        3 |        -4 |       8 |    7 |   10 |    1 |      2.3 |            4.3
   9 |       3 |        4 |        -4 |       8 |    8 |   -1 |    0 |      3.3 |            5.3
  10 |       4 |        1 |         8 |      -2 |    8 |   12 |    1 |        0 |            5.3
  11 |       4 |        2 |         8 |      -2 |   12 |   13 |    1 |        1 |            6.3
  12 |       4 |        3 |         8 |      -2 |   17 |   15 |  0.6 |        2 |            7.3
  13 |       4 |        4 |         8 |      -2 |   -2 |   -2 |    0 |      2.6 |            7.9
(13 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, side, fraction FROM pointsOfInterest$$,
  ARRAY[-6, 7, -4, 8, -2], 'B', false)
WHERE path_id = 3 AND edge < 0;
 agg_cost
----------
      2.7
(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, side, fraction FROM pointsOfInterest$$,
  ARRAY[-6, 7, -4, 8, -2], 'r')
WHERE path_id = 3 AND edge < 0;
 route_agg_cost
----------------
            5.3
(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, side, fraction FROM pointsOfInterest$$,
  ARRAY[-6, 7, -4, 8, -2], 'r')
WHERE edge <> -1 ORDER BY seq;
 node_seq | node
----------+------
        1 |   -6
        2 |    7
        3 |    3
        4 |   -4
        5 |    3
        6 |    7
        7 |    8
        8 |    7
        9 |   11
       10 |   16
       11 |   -2
(11 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, side, fraction FROM pointsOfInterest$$,
  ARRAY[-6, 7, -4, 8, -2], 'r')
WHERE edge < 0;
 path_id | route_agg_cost
---------+----------------
       1 |            0.3
       2 |            2.6
       3 |            5.3
       4 |            8.7
(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, side, fraction FROM pointsOfInterest$$,
  ARRAY[-6, 7, -4, 8, -2], 'r', details => true)
WHERE agg_cost <> 0 or seq = 1;
 seq | node |     status
-----+------+-----------------
   1 |   -6 | passes in front
   2 |    7 | visits
   4 |    3 | passes in front
   5 |    1 | passes in front
   6 |   -4 | visits
   8 |    3 | passes in front
   9 |    7 | passes in front
  10 |    8 | visits
  12 |    7 | passes in front
  13 |   11 | passes in front
  14 |   16 | passes in front
  15 |   -2 | passes in front
(12 rows)

See Also

Indices and tables