Skip to content

Notes on pgr_trsp (2.3.2 release)

Jump to bottom Edit New page
Vicky Vergara edited this page Jan 5, 2017 · 19 revisions

Introduction

pgr_trsp code has issues that are not being fixed yet, but as time passes and new functionality is added to pgRouting with wrappers to hide the issues, not to fix them.

For clarity on the queries:

  • _pgr_trsp (with underscore) is the original code
  • pgr_trsp (lower case) represents the wrapper calling the original code
  • pgr_TRSP (upper case) represents the wrapper calling the replacement function, depending on the function, it can be:
    • pgr_dijkstra
    • pgr_dijkstraVia
    • pgr_withPoints
    • _pgr_withPointsVia

This page intentions is to compare the original code with the wrapped version of the trsp group of functions.

the restriction used in the examples

The restriction used in the examples does not have to do anything with the graph:

  • No vertex has id: 25, 32 or 33
  • No edge has id: 25, 32 or 33
$$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, 32, 33::TEXT AS via_path$$

therefore the shortest path expected are as if there was no restriction involved

No path representation differences

Original code of pgr_trsp throws Error to represent no path found

SELECT * FROM _pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edge_table$$,
    1, 15, true, true
);
ERROR:  Error computing path: Path Not Found

dijkstra returns EMPTY SET to represent no path found

SELECT * FROM pgr_dijkstra(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edge_table$$,
    1, 15
);
 seq | path_seq | node | edge | cost | agg_cost 
-----+----------+------+------+------+----------
(0 rows)

pgr_trsp use the pgr_dijkstra when there are no restrictions therefore returns EMPTY SET to represent no path found

SELECT * FROM pgr_TRSP(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edge_table$$,
    1, 15, true, true
);
 seq | id1 | id2 | cost 
-----+-----+-----+------
(0 rows)

pgr_trsp use the original code when there are restrictions therefore throws Error to represent no path found

SELECT * FROM pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edge_table$$,
    1, 15, true, true,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
ERROR:  Error computing path: Path Not Found
CONTEXT:  PL/pgSQL function pgr_trsp(text,integer,integer,boolean,boolean,text) line 29 at RETURN QUERY

routing from/to same location there should be no path

using dijkstra to verify (1 to 1)

SELECT * FROM pgr_dijkstra(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edge_table$$,
    1, 1
);
 seq | path_seq | node | edge | cost | agg_cost 
-----+----------+------+------+------+----------
(0 rows)

This call uses the replacement function because there are no restrictions (1 to 1) therefore is expected to return EMPTY SET to represent no path found

SELECT * FROM pgr_TRSP(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    1, 1,  
    true, 
    true
);
 seq | id1 | id2 | cost 
-----+-----+-----+------
(0 rows)

call forcing the use of the original code (1 to 1) therefore is expected to return Error to represent no path found but "finds" a path when there should be no path.

SELECT * FROM _pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    1, 1,  
    true, 
    true
);
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |   1 |   1 |    1
   1 |   2 |   4 |    1
   2 |   5 |   8 |    1
   3 |   6 |   9 |    1
   4 |   9 |  16 |    1
   5 |   4 |   3 |    1
   6 |   3 |   2 |    1
   7 |   2 |   1 |    1
   8 |   1 |  -1 |    0
(9 rows)

trsp with restrictions (1 to 1) use the original code is expected to return Error to represent no path found

SELECT * FROM pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    1, 1,  
    true, 
    true,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |   1 |   1 |    1
   1 |   2 |   4 |    1
   2 |   5 |   8 |    1
   3 |   6 |   9 |    1
   4 |   9 |  16 |    1
   5 |   4 |   3 |    1
   6 |   3 |   2 |    1
   7 |   2 |   1 |    1
   8 |   1 |  -1 |    0
(9 rows)

trsp calling the original code with restrictions (1 to 1) is expected to return Error to represent no path found but "finds" a path when there should be no path.

SELECT * FROM _pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    1, 1,  
    true, 
    true,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |   1 |   1 |    1
   1 |   2 |   4 |    1
   2 |   5 |   8 |    1
   3 |   6 |   9 |    1
   4 |   9 |  16 |    1
   5 |   4 |   3 |    1
   6 |   3 |   2 |    1
   7 |   2 |   1 |    1
   8 |   1 |  -1 |    0
(9 rows)

routing from 2 to 3 on undirected graph

using Dijkstra to verify the shortest path from (2 to 3) on undirected graph

SELECT * FROM pgr_dijkstra(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edge_table$$,
    2, 3, false
);
 seq | path_seq | node | edge | cost | agg_cost 
-----+----------+------+------+------+----------
   1 |        1 |    2 |    2 |    1 |        0
   2 |        2 |    3 |   -1 |    0 |        1
(2 rows)

using the replacement function because there are no restrictions (2 to 3)

SELECT * FROM pgr_TRSP(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    2, 3,
    false, 
    true
);
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |   2 |   2 |    1
   1 |   3 |  -1 |    0
(2 rows)

call to the original function (2 to 3) does not find the shortest path

SELECT * FROM _pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    2, 3,
    false, 
    true
);
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |   2 |   4 |    1
   1 |   5 |   8 |    1
   2 |   6 |   9 |    1
   3 |   9 |  16 |    1
   4 |   4 |   3 |    1
   5 |   3 |  -1 |    0
(6 rows)

trsp with restrictions (2 to 3) does not find the shortest path

SELECT * FROM pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    2, 3,
    false, 
    true,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |   2 |   4 |    1
   1 |   5 |   8 |    1
   2 |   6 |   9 |    1
   3 |   9 |  16 |    1
   4 |   4 |   3 |    1
   5 |   3 |  -1 |    0
(6 rows)

calling the original code with restrictions (2 to 3) does not find the shortest path

SELECT * FROM _pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    2, 3,
    false, 
    true,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |   2 |   4 |    1
   1 |   5 |   8 |    1
   2 |   6 |   9 |    1
   3 |   9 |  16 |    1
   4 |   4 |   3 |    1
   5 |   3 |  -1 |    0
(6 rows)

from 1 to 1 to 2

pgr_trspViaVertices throws error when a path on the route was not found this example no path is found (vertex 15 is disconnected) from the big graph

SELECT * FROM _pgr_trspViaVertices(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    ARRAY[1, 15, 2],
    false, 
    true
);
ERROR:  Error computing path: Path Not Found
CONTEXT:  PL/pgSQL function _pgr_trspviavertices(text,integer[],boolean,boolean,text) line 23 at FOR over SELECT rows

In this example there exists a path from 2 to 1 but only complete routes are processed

SELECT * FROM _pgr_trspViaVertices(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    ARRAY[1, 15, 2, 1],
    false, 
    true
);
ERROR:  Error computing path: Path Not Found
CONTEXT:  PL/pgSQL function _pgr_trspviavertices(text,integer[],boolean,boolean,text) line 23 at FOR over SELECT rows

pgr_dijkstraVia returning what paths of the route it finds or EMPTY SET when non is found this case none is found

SELECT * FROM pgr_dijkstraVia(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    ARRAY[1, 15, 2],
    false
);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost 
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
(0 rows)

this case only from 2 to 1 is found

SELECT * FROM pgr_dijkstraVia(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    ARRAY[1, 15, 2, 1],
    false
);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost 
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       3 |        1 |         2 |       1 |    2 |    1 |    1 |        0 |              0
   2 |       3 |        2 |         2 |       1 |    1 |   -2 |    0 |        1 |              1
(2 rows)

the pgr_dijkstraVia used are for complete routes so its marked as strict:=true therefore the expected result is EMPTY SET to represent no route was found

SELECT * FROM pgr_dijkstraVia(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    ARRAY[1, 1, 2],
    false,
    strict := true
);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost 
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
(0 rows)

pgr_TRSPViaVertices using the replacement function when there are no restrictions. Because there is no path from 1 to 1 then there is no complete route 1 to 1 to 2 therefore the expected result is EMPTY SET to represent no route was found

SELECT * FROM pgr_TRSPViaVertices(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    ARRAY[1, 1, 2],
    false, 
    true
);
 seq | id1 | id2 | id3 | cost 
-----+-----+-----+-----+------
(0 rows)

Using the original code Because there is no path from 1 to 1 then there is no complete route 1 to 1 to 2 therefore the expected result is Error to represent no route was found gives a result even that there is no path from 1 to 1

SELECT * FROM _pgr_trspViaVertices(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    ARRAY[1, 1, 2],
    false, 
    true
);
 seq | id1 | id2 | id3 | cost 
-----+-----+-----+-----+------
   1 |   1 |   1 |   1 |    1
   2 |   1 |   2 |   4 |    1
   3 |   1 |   5 |   8 |    1
   4 |   1 |   6 |   9 |    1
   5 |   1 |   9 |  16 |    1
   6 |   1 |   4 |   3 |    1
   7 |   1 |   3 |   2 |    1
   8 |   1 |   2 |   1 |    1
   9 |   2 |   1 |   1 |    1
  10 |   2 |   2 |  -1 |    0
(10 rows)

with restrictions the original code is used

SELECT * FROM pgr_trspViaVertices(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    ARRAY[1, 1, 2],
    false, 
    true,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
 seq | id1 | id2 | id3 | cost 
-----+-----+-----+-----+------
   1 |   1 |   1 |   1 |    1
   2 |   1 |   2 |   4 |    1
   3 |   1 |   5 |   8 |    1
   4 |   1 |   6 |   9 |    1
   5 |   1 |   9 |  16 |    1
   6 |   1 |   4 |   3 |    1
   7 |   1 |   3 |   2 |    1
   8 |   1 |   2 |   1 |    1
   9 |   2 |   1 |   1 |    1
  10 |   2 |   2 |  -1 |    0
(10 rows)

Using explicitly the original code

SELECT * FROM _pgr_trspViaVertices(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    ARRAY[1, 1, 2],
    false, 
    true,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
 seq | id1 | id2 | id3 | cost 
-----+-----+-----+-----+------
   1 |   1 |   1 |   1 |    1
   2 |   1 |   2 |   4 |    1
   3 |   1 |   5 |   8 |    1
   4 |   1 |   6 |   9 |    1
   5 |   1 |   9 |  16 |    1
   6 |   1 |   4 |   3 |    1
   7 |   1 |   3 |   2 |    1
   8 |   1 |   2 |   1 |    1
   9 |   2 |   1 |   1 |    1
  10 |   2 |   2 |  -1 |    0
(10 rows)

from 2 to 3 to 2

dijkstra via shows the shortest route on the two paths

SELECT * FROM pgr_dijkstraVia(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    ARRAY[2, 3, 2],
    false 
);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost 
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |         2 |       3 |    2 |    2 |    1 |        0 |              0
   2 |       1 |        2 |         2 |       3 |    3 |   -1 |    0 |        1 |              1
   3 |       2 |        1 |         3 |       2 |    3 |    2 |    1 |        0 |              1
   4 |       2 |        2 |         3 |       2 |    2 |   -2 |    0 |        1 |              2
(4 rows)

the replacement function pgr_dijkstraVia is used because there are no restrictions

SELECT * FROM pgr_TRSPViaVertices(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    ARRAY[2, 3, 2],
    false, 
    true
);
 seq | id1 | id2 | id3 | cost 
-----+-----+-----+-----+------
   1 |   1 |   2 |   2 |    1
   2 |   2 |   3 |   2 |    1
   3 |   2 |   2 |  -1 |    0
(3 rows)

forcing to use the original code, it give not give the shortest path from 2 to 3

SELECT * FROM _pgr_trspViaVertices(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table$$,
    ARRAY[2, 3, 2],
    false, 
    true
);
 seq | id1 | id2 | id3 | cost 
-----+-----+-----+-----+------
   1 |   1 |   2 |   4 |    1
   2 |   1 |   5 |   8 |    1
   3 |   1 |   6 |   9 |    1
   4 |   1 |   9 |  16 |    1
   5 |   1 |   4 |   3 |    1
   6 |   2 |   3 |   2 |    1
   7 |   2 |   2 |  -1 |    0
(7 rows)

Contact: https://discourse.osgeo.org/c/pgrouting/pgrouting-dev

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally