pgr_trspVia_withPoints - Proposed

pgr_trspVia_withPoints - Route that goes through a list of vertices and/or points with restrictions.

images/boost-inside.jpeg

Boost Graph Inside

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.

Availability

  • Version 3.4.0

    • New proposed function:

      pgr_trspVia_withPoints ( One Via )

Description

Given a graph, a set of restriction on the graph edges, 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)\) trying not to use restricted paths.

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_withPointsVia - Proposed .

  • For the set of paths of the solution that pass through a restriction then

    • Execute the TRSP algorithm with restrictions for the path.

    • NOTE when this is done, U_turn_on_edge flag is ignored.

Note

Do not use negative values on identifiers of the inner queries.

Signatures

One Via

pgr_trspVia_withPoints( Edges SQL , Restrictions 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, -5\}\) in that order on an directed graph. 

SELECT * FROM pgr_trspVia_withPoints(
  $$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
  $$SELECT path, cost FROM restrictions$$,
  $$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
  ARRAY[-6, 15, -5]);
 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    10     1       0.3             0.3
   3        1         3         -6       15     8    12     1       1.3             1.3
   4        1         4         -6       15    12    13     1       2.3             2.3
   5        1         5         -6       15    17    15     1       3.3             3.3
   6        1         6         -6       15    16    16     1       4.3             4.3
   7        1         7         -6       15    15    -1     0       5.3             5.3
   8        2         1         15       -5    15     3     1         0             5.3
   9        2         2         15       -5    10     5   0.8         1             6.3
  10        2         3         15       -5    -5    -2     0       1.8             7.1
(10 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

r

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

  • r for right driving side

  • l for left driving side

  • Any other value will be considered as r

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

Restrictions SQL

Column

Type

Description

path

ARRAY [ ANY-INTEGER ]

Sequence of edge identifiers that form a path that is not allowed to be taken. - Empty arrays or NULL arrays are ignored. - Arrays that have a NULL element will raise an exception.

Cost

ANY-NUMERICAL

Cost of taking the forbidden path.

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 for points on the fly

Using pgr_findCloseEdges :

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_trspVia_withPoints(
  $e$ SELECT * FROM edges $e$,
  $r$ SELECT path, cost FROM restrictions $r$,
  $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     8     1         3               3
   6        1         6          1       -1     7    10     1         4               4
   7        1         7          1       -1     8    12     1         5               5
   8        1         8          1       -1    12    13     1         6               6
   9        1         9          1       -1    17    15     1         7               7
  10        1        10          1       -1    16    16     1         8               8
  11        1        11          1       -1    15     3     1         9               9
  12        1        12          1       -1    10     5   0.8        10              10
  13        1        13          1       -1    -1    -1     0      10.8            10.8
  14        2         1         -1       -2    -1     5   0.2         0            10.8
  15        2         2         -1       -2    11     8     1       0.2              11
  16        2         3         -1       -2     7     8   0.9       1.2              12
  17        2         4         -1       -2    -2    -2     0       2.1            12.9
(17 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 \(\{-6, 7, -4, 8, -2\}\) in that order on a directed graph. 

SELECT * FROM pgr_trspVia_withPoints(
  $$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
  $$SELECT path, cost FROM restrictions$$,
  $$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
  ARRAY[-6, 7, -4, 8, -2]
);
 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   1.3         1             1.3
   5        2         3          7       -4    -4    -1     0       2.3             2.6
   6        3         1         -4        8    -4     6   0.7         0             2.6
   7        3         2         -4        8     3     7     1       0.7             3.3
   8        3         3         -4        8     7     4   0.6       1.7             4.3
   9        3         4         -4        8     7    10     1       2.3             4.9
  10        3         5         -4        8     8    -1     0       3.3             5.9
  11        4         1          8       -2     8    10     1         0             5.9
  12        4         2          8       -2     7     8     1         1             6.9
  13        4         3          8       -2    11     9     1         2             7.9
  14        4         4          8       -2    16    15   0.4         3             8.9
  15        4         5          8       -2    -2    -2     0       3.4             9.3
(15 rows)
Aggregate cost of the third path. 
SELECT agg_cost FROM  pgr_trspVia_withPoints(
  $$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
  $$SELECT path, cost FROM restrictions$$,
  $$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
  ARRAY[-6, 7, -4, 8, -2]
)
WHERE path_id = 3 AND edge <0;
 agg_cost
----------
      3.3
(1 row)
Route’s aggregate cost of the route at the end of the third path. 
SELECT route_agg_cost FROM  pgr_trspVia_withPoints(
  $$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
  $$SELECT path, cost FROM restrictions$$,
  $$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
  ARRAY[-6, 7, -4, 8, -2]
)
WHERE path_id = 3 AND edge < 0;
 route_agg_cost
----------------
            5.9
(1 row)
Nodes visited in the route. 
SELECT row_number() over () as node_seq, node
FROM  pgr_trspVia_withPoints(
  $$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
  $$SELECT path, cost FROM restrictions$$,
  $$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
  ARRAY[-6, 7, -4, 8, -2]
)
WHERE edge <> -1 ORDER BY seq;
 node_seq  node
----------+------
        1    -6
        2     7
        3     3
        4    -4
        5     3
        6     7
        7     7
        8     8
        9     7
       10    11
       11    16
       12    -2
(12 rows)
The aggregate costs of the route when the visited vertices are reached. 
SELECT path_id, route_agg_cost FROM  pgr_trspVia_withPoints(
  $$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
  $$SELECT path, cost FROM restrictions$$,
  $$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
  ARRAY[-6, 7, -4, 8, -2]
)
WHERE edge < 0;
 path_id  route_agg_cost
---------+----------------
       1             0.3
       2             2.6
       3             5.9
       4             9.3
(4 rows)
Status of "passes in front" or "visits" of the nodes and points. 
SELECT seq, route_agg_cost, node, agg_cost ,
CASE WHEN edge = -1 THEN $$visits$$
ELSE $$passes in front$$
END as status
FROM  pgr_trspVia_withPoints(
  $$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
  $$SELECT path, cost FROM restrictions$$,
  $$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
  ARRAY[-6, 7, -4, 8, -2])
WHERE agg_cost  <> 0 or seq = 1;
 seq  route_agg_cost  node  agg_cost      status
-----+----------------+------+----------+-----------------
   1               0    -6         0  passes in front
   2             0.3     7       0.3  visits
   4             1.3     3         1  passes in front
   5             2.6    -4       2.3  visits
   7             3.3     3       0.7  passes in front
   8             4.3     7       1.7  passes in front
   9             4.9     7       2.3  passes in front
  10             5.9     8       3.3  visits
  12             6.9     7         1  passes in front
  13             7.9    11         2  passes in front
  14             8.9    16         3  passes in front
  15             9.3    -2       3.4  passes in front
(12 rows)

Simulation of how algorithm works.

The algorithm performs a pgr_withPointsVia - Proposed 

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]);
 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)

Detects which of the paths pass through a restriction in this case is for the path_id = 1 from -6 to 15 because the path \(9 \rightarrow 16\) is restricted.

Executes the TRSP algorithm for the conflicting paths. 

SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
FROM  pgr_trsp_withPoints(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  $$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
  -6, 15);
 path_id  path_seq  start_vid  end_vid  node  edge  cost  agg_cost
---------+----------+-----------+---------+------+------+------+----------
       1         1         -6       15    -6     4   0.3         0
       1         2         -6       15     7    10     1       0.3
       1         3         -6       15     8    12     1       1.3
       1         4         -6       15    12    13     1       2.3
       1         5         -6       15    17    15     1       3.3
       1         6         -6       15    16    16     1       4.3
       1         7         -6       15    15    -1     0       5.3
(7 rows)

From the pgr_withPointsVia - Proposed result it removes the conflicting paths and builds the solution with the results of the pgr_trsp - Proposed algorithm: 

WITH
solutions AS (
  SELECT path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
  FROM  pgr_withPointsVia(
    $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
    $$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
    ARRAY[-6, 15, -5]) WHERE path_id != 1
  UNION
  SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
  FROM  pgr_trsp_withPoints(
    $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
    $$SELECT path, cost FROM restrictions$$,
    $$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
    -6, 15)),
with_seq AS (
  SELECT row_number() over(ORDER BY path_id, path_seq) AS seq, *
  FROM solutions),
aggregation AS (SELECT seq, SUM(cost) OVER(ORDER BY seq) AS route_agg_cost FROM with_seq)
SELECT with_seq.*, COALESCE(route_agg_cost, 0) AS route_agg_cost
FROM with_seq LEFT JOIN aggregation ON (with_seq.seq = aggregation.seq + 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    10     1       0.3             0.3
   3        1         3         -6       15     8    12     1       1.3             1.3
   4        1         4         -6       15    12    13     1       2.3             2.3
   5        1         5         -6       15    17    15     1       3.3             3.3
   6        1         6         -6       15    16    16     1       4.3             4.3
   7        1         7         -6       15    15    -1     0       5.3             5.3
   8        2         1         15       -5    15     3     1         0             5.3
   9        2         2         15       -5    10     5   0.8         1             6.3
  10        2         3         15       -5    -5    -2     0       1.8             7.1
(10 rows)

Getting the same result as pgr_trspVia_withPoints : 

SELECT * FROM  pgr_trspVia_withPoints(
  $$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
  $$SELECT path, cost FROM restrictions$$,
  $$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
  ARRAY[-6, 15, -5]);
 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    10     1       0.3             0.3
   3        1         3         -6       15     8    12     1       1.3             1.3
   4        1         4         -6       15    12    13     1       2.3             2.3
   5        1         5         -6       15    17    15     1       3.3             3.3
   6        1         6         -6       15    16    16     1       4.3             4.3
   7        1         7         -6       15    15    -1     0       5.3             5.3
   8        2         1         15       -5    15     3     1         0             5.3
   9        2         2         15       -5    10     5   0.8         1             6.3
  10        2         3         15       -5    -5    -2     0       1.8             7.1
(10 rows)
Example 8 :

Sometimes U_turn_on_edge flag is ignored when is set to false .

The first step, doing a pgr_withPointsVia - Proposed does consider not making a U turn on the same edge. But the path \(9 \rightarrow 16\) (Rows 4 and 5) is restricted and the result is using it. 

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, 6], U_turn_on_edge => false);
 seq  path_id  path_seq  start_vid  end_vid  node  edge  cost  agg_cost  route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1        1         1          6        7     6     4     1         0               0
   2        1         2          6        7     7    -1     0         1               1
   3        2         1          7        6     7     8     1         0               1
   4        2         2          7        6    11     9     1         1               2
   5        2         3          7        6    16    16     1         2               3
   6        2         4          7        6    15     3     1         3               4
   7        2         5          7        6    10     2     1         4               5
   8        2         6          7        6     6    -2     0         5               6
(8 rows)

When executing the pgr_trsp_withPoints - Proposed algorithm for the conflicting path, there is no U_turn_on_edge flag. 

SELECT 5 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
FROM  pgr_trsp_withPoints(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  $$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
  7, 6);
 path_id  path_seq  start_vid  end_vid  node  edge  cost  agg_cost
---------+----------+-----------+---------+------+------+------+----------
       5         1          7        6     7     4     1         0
       5         2          7        6     6    -1     0         1
(2 rows)

Therefore the result ignores the U_turn_on_edge flag when set to false . From the pgr_withPointsVia - Proposed result it removes the conflicting paths and builds the solution with the results of the pgr_trsp - Proposed algorithm. In this case a U turn is been done using the same edge. 

SELECT * FROM  pgr_trspVia_withPoints(
  $$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
  $$SELECT path, cost FROM restrictions$$,
  $$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
  ARRAY[6, 7, 6], U_turn_on_edge => false);
 seq  path_id  path_seq  start_vid  end_vid  node  edge  cost  agg_cost  route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1        1         1          6        7     6     4     1         0               0
   2        1         2          6        7     7    -1     0         1               1
   3        2         1          7        6     7     4     1         0               1
   4        2         2          7        6     6    -2     0         1               2
(4 rows)

See Also

Indices and tables