Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

trsp() doesnt find a route if Start_Edge = End_Edge #704

Closed
dropyghost opened this issue Dec 7, 2016 · 27 comments
Closed

trsp() doesnt find a route if Start_Edge = End_Edge #704

dropyghost opened this issue Dec 7, 2016 · 27 comments

Comments

@dropyghost
Copy link

dropyghost commented Dec 7, 2016

I use it to my AVL app and sometimes the car doesnt move much or the link is too long, so stay in the same link.

Expected behavior and actual behavior

When try to calculate a route using pgr_trsp() and start_edge = end_edge

In version "pgrouting-2.0.0" using offset return a single row with node -1 and the edge, the cost to travel is just between those offset. In this case I use offset (0, 0.5)
image

In "pgrouting-2.2.2" doesnt return anything
image

Steps to reproduce the problem

image

CREATE TABLE map.test as 
SELECT  671222::integer as id, 318255::integer as  source, 222698::integer as target, 14.02::float8 as cost, 14.02::float8 as reverse_cost UNION ALL
SELECT  671223, 222698, 36655, 197.16, 197.16 UNION ALL
SELECT  582877, 408918, 5556, 458.09, 458.09 UNION ALL
SELECT  582876, 318255, 408918, 3.89, 3.89 UNION ALL
SELECT  585280, 5556, 454424, 54.84, 54.84;

SELECT seq, id1 AS node, id2 AS edge, cost::numeric(11,4)
FROM pgr_trsp(
	'select * from map.test',
	582877,     -- edge_id for start
	0,          -- ini_offset
	582877,     -- edge_id of route end
	0.5,        -- end_offset
	true,        -- directed graph?
	true,  	   -- has_reverse_cost?
    null -- include the turn restrictions
	) PG ; 

If start_edge <> end_edge work ok in both versions.

image

SELECT seq, id1 AS node, id2 AS edge, cost::numeric(11,4)
FROM pgr_trsp(
	'select * from map.test',
	582877,     -- edge_id for start
	0,          -- ini_offset
	585280,     -- edge_id of route end
	0.5,        -- end_offset
	true,        -- directed graph?
	true,  	   -- has_reverse_cost?
    null -- include the turn restrictions
	) PG ; 

Specifications like the version of pgRouting/PostGIS and PostgreSQL as well as Operating System

Have two postgres server:

This is my oldest server where was working ok.
Windows Server 2008 R2
"PostgreSQL 9.3.2, compiled by Visual C++ build 1600, 64-bit"
"POSTGIS="2.1.1 r12113" GEOS="3.4.2-CAPI-1.8.2 r3924" PROJ="Rel. 4.8.0, 6 March 2012" GDAL="GDAL 1.10.0, released 2013/04/24" LIBXML="2.7.8" LIBJSON="UNKNOWN" RASTER"
"(2.0.0,pgrouting-2.0.0,0,d6ed2cb,master,1.53.0)"

This is my newest install and doesnt work.
Windows 10
"PostgreSQL 9.5.3, compiled by Visual C++ build 1800, 64-bit"
"POSTGIS="2.2.2 r14797" GEOS="3.5.0-CAPI-1.9.0 r4090" PROJ="Rel. 4.9.1, 04 March 2015" GDAL="GDAL 2.0.2, released 2016/01/26" LIBXML="2.7.8" LIBJSON="0.12" RASTER"
"(2.2.2,pgrouting-2.2.2,544044b,master,1.59.0)"

@cvvergara
Copy link
Member

I can see that you are not using restrictions, then I strongly suggest that you use
pgr_withPoints

I have an answer here that looks like your problem where actually one "point" is actually a vertex on the topology (offset is 0 or 1)
My answer was using pgRouting 2.3 but I think it applies to 2.2.

@dropyghost
Copy link
Author

Hi again @cvvergara, if you remember my stackoverflow question from yesterday I have restrictions. I just remove it to make the sample easy to reproduce.

Same thing regarding the offset I choose (0, 0.5) to make easy see the offset is working and return half of the cost. But you get same result with (0.25, 0.75)

And again, my storeprocs are working fine in old version, the problem is now I have a different development enviroment and doesn't work as expected.

@cvvergara
Copy link
Member

cvvergara commented Dec 8, 2016

Was it you whom asked this question?

As I mentioned there, I can not be more of help on pgr_trsp, It is known to have bugs, and starting from version pgRouting v2.2 its being wrapped with pgr_dijkstra & pgr_withPoints when there are no restrictions. When there are restrictions, it might give some "good" enough results that is why is being kept.

About the other functions (including this one): gradually, I've being enforcing what the documentation says about them. When 2.0 that was not done.To keep the old signatures for backwards compatibility, its done with wrappers.

This has some comparison on the pgr_dijkstra signatures on 2.2
http://docs.pgrouting.org/2.2/en/src/dijkstra/doc/pgr_dijkstra.html#id2
and the one that needs to have ::INTEGER is the old signature.

Some examples without turn restrictions from version 2.0 are the following:
for this data:
http://docs.pgrouting.org/2.0/en/doc/src/developer/sampledata.html#sampledata

example: starting is same as destination

This example shows shows that if you want to go from 1 to 1, that is you are already there so there is no need to have a path, this is what happens:
trsp

the same data with 2.2 or higher
trsp3

example on undirected graph, from 2 to 3

the expected path is 2->3 as its undirected, but this is what happens
trsp1

vs with 2.2 or higher

trsp4

My guess on why your storeprocs are not working well

pgr_dijkstra on v2.0 has the same problem as pgr_trsp, as well as many other functions (besides their own internal problems): the way internally they read & interpret the data.

Now it catches user's contradictions:

pgr_dijkstra('select id::INTGER,
  source::INTEGER, target::INTEGER,
  cost::FLOAT, reverse_cost::FLOAT
 FROM edge_table', false, FALSE')  -- undirected don't have/use reverse_cost

its a contradiction: the FALSE indicates that the column reverse_cost is not to be used but has_rcost is FALSE,

has_rcost mean has or use?,

has_rcost:
if true, the reverse_cost column of the SQL generated set of rows will be used for the cost of the traversal of the edge in the opposite direction.

If it means has, well there you are contradicted, you are saying it does not has it but you are providing it. so the intention is not to have it, so lets remove it
if it means use, then lets remove it, because its not going to be used. (being on the safe side, nothing on that column should be used):

so, which ever interpretation was (has or use), that contradiction is converted to the following:

pgr_dijkstra('select id::INTGER,
  source::INTEGER,
  target::INTEGER,
  cost::FLOAT,
FROM edge_table, false, FALSE')

As you can see FALSE indicates that you don't want to use the column reverse_cost, also means its not there, now there is no contradiction.

to avoid that kind of problem the new signatures avoid that flag, so if its there is because you want to use it, if its not there is because you don't want to use it, also see there is no need of the type casting:

pgr_dijkstra('select id,
  source,
  target,
  cost, reverse_cost
FROM edge_table, false) -- only the directed flag is used (set to be undirected in this case)

pgr_dijkstra('select id,
  source,
  target,
  cost
FROM edge_table, false)

Gradually they are being fixed on the 2.x series.
http://docs.pgrouting.org/latest/en/doc/src/changelog/release_notes.html

how to migrate from 2.0 to a higher version

make sure all of your queries are not contradictory.
then the migration will:

  • use the wrapped query needed for the backwards compatibility
  • give better results.

@dropyghost
Copy link
Author

@cvvergara Yes, that is me :). Forgot here Im using my nick name instead of my real name.

I really need restrictions. What you recomend:

  • Should I downgrade to v2.0?
  • The other thing I can do to solve this bug is if same link I can create that one row result by myself and not call pgr_trsp

What is that UI to test the function show in your pictures ?

@cvvergara
Copy link
Member

Please do not downgrade, the 2.x series main objective is to rewrite the functions because of old designs, bugs, etc.

I'll rephrase:
"you need the original pgr_trsp without the wrappers"

The original code hasn't changed. (except some function renames, and that the compiler was generating many warnings because of bad type handling)

This are the calls to the original functions without the wrappers:
https://github.com/pgRouting/pgrouting/blob/master/src/trsp/sql/trsp_V2.2.sql#L30
So basically where you are calling

pgr_trsp(....)

add an underscore to the function

_pgr_trsp(....)

answer to some of your questions:

I used Qgis and the pgRoutingLayer plugin.
about the Q about version 2.4 due on march, its already in develop.
And the documentation is available.

back to pgr_trsp.

  • I tried once rewriting the code (to remove some bugs), and failed.
    • Conclusion: I don't understand the code
  • it has a lot of bugs,
  • bugs not mentioned like: It uses pointers, has leaks.
  • I really don't understand the developer's intention on having the restrictions table as it is in the documentation
  • I don't understand why the developer is using a text string of ids (of nodes or edges is not clear) as parameter (I would have used array)
  • I don't understand the reason of why is in reverse order
  • I don't understand why the from_id is not part of that sequence of ids, and is a separate parameter.
  • I don't understand the documentation of that function.
  • it had 4 functions named dijkstra, that are not doing a dijkstra (I just renamed them dijkstra1, dijsktra2, dijkstra3, dijkstra4) but is like naming a function that reads the data instead of "read_data" the name is "dijkstra".
  • it does not accept ANY-INTEGER as Ids
  • it does not accept ANY-NUMERICAL as costs
  • the types change internally from integer to long

I other words, its doing magic, because on large scale it gives an answer, might not be perfect on unit tests, as you can see in the previous comment's images, but its better than nothing.

Any improvement on C/C++ code, , improvement on the wrappers, your own design (even if its on plpgsql), improvement to the documentation is welcome.

everything related to trsp is here:
https://github.com/pgRouting/pgrouting/tree/master/src/trsp

@dropyghost
Copy link
Author

I'll rephrase:
"you need the original pgr_trsp without the wrappers"

Sorry sometime I have problem undesrtanding the negatives in english.

Which one do you suggest I use ?

1 ) pgr_trsp(....)
or
2 ) _pgr_trsp(....)

@cvvergara
Copy link
Member

Sorry, can not suggest anything.
You will need to try what is best for your application (and/or migration to new version)
if you use (1) you will use the code that 'Hides' the bugs when there are no restrictions, and it will still use the buggy code when there are restrictions.
if you use (2) you will get wrong results when there are no restrictions, and it will still use the buggy code when there are restrictions.

@woodbri
Copy link
Contributor

woodbri commented Dec 12, 2016

Option 2 should be the same as what you were getting with version 2.0.0.
Try _pgr_trsp() and you should get the same results as before.

@dropyghost
Copy link
Author

@woodbri I try it, but _pgr_trsp() doesnt have offset :(

@woodbri
Copy link
Contributor

woodbri commented Dec 12, 2016

The file "sql/trsp_V2.2.sql" in the repository has the following two functions defined. The 2nd one is the trsp with with edged_id and fraction along the edge. You should see these in pgAdmin3 of via the psql command to view functions. Please make sure you have the correct arguments in the correct order.

CREATE OR REPLACE FUNCTION _pgr_trsp(
    sql text,
    source_vid integer,
    target_vid integer,
    directed boolean,
    has_reverse_cost boolean,
    turn_restrict_sql text DEFAULT null)
RETURNS SETOF pgr_costResult
AS '$libdir/${PGROUTING_LIBRARY_NAME}', 'turn_restrict_shortest_path_vertex'
LANGUAGE 'c' IMMUTABLE;


CREATE OR REPLACE FUNCTION _pgr_trsp(
    sql text,
    source_eid integer,
    source_pos float8,
    target_eid integer,
    target_pos float8,
    directed boolean,
    has_reverse_cost boolean,
    turn_restrict_sql text DEFAULT null)
RETURNS SETOF pgr_costResult
AS '$libdir/${PGROUTING_LIBRARY_NAME}', 'turn_restrict_shortest_path_edge'
LANGUAGE 'c' IMMUTABLE;

@dropyghost
Copy link
Author

@woodbri Weird I only have one signature.

image

@woodbri
Copy link
Contributor

woodbri commented Dec 12, 2016

Then copy and paste the other signature into a sql window and run it. Then you should be able to try it out.

@woodbri
Copy link
Contributor

woodbri commented Dec 12, 2016

@dropyghost Where do you get your pgrouting from? Do you compile it? Download it from somewhere? where?

@dropyghost
Copy link
Author

@woodbri I install with the stack Builder 3.1.1

@cvvergara
Copy link
Member

@dropyghost
On the upgrade you made mentioned on the first comment.
why pgrouting 2.2.2, the latest of the 2.2 minor is 2.2.4?
the latest pgrouting official version is 2.3.1.
I don't know what is stack builder is.

@woodbri
Copy link
Contributor

woodbri commented Dec 12, 2016

I just checked the code for ver 2.2.0 and it has the following signatures:

CREATE OR REPLACE FUNCTION _pgr_trsp(
    sql text,
    source_vid integer,
    target_vid integer,
    directed boolean,
    has_reverse_cost boolean,
    turn_restrict_sql text DEFAULT null)
RETURNS SETOF pgr_costResult
AS '$libdir/${PGROUTING_LIBRARY_NAME}', 'turn_restrict_shortest_path_vertex'
LANGUAGE 'c' IMMUTABLE;

CREATE OR REPLACE FUNCTION pgr_trsp(
    sql text,
    source_eid integer,
    source_pos float8,
    target_eid integer,
    target_pos float8,
    directed boolean,
    has_reverse_cost boolean,
    turn_restrict_sql text DEFAULT null)
RETURNS SETOF pgr_costResult
AS '$libdir/${PGROUTING_LIBRARY_NAME}', 'turn_restrict_shortest_path_edge'
LANGUAGE 'c' IMMUTABLE;

The 2nd one does not have the leading '_', and it should be the same as in 2.0.0, but there may have been some changes to try and fix some issues that changed behavior. Regardless, trsp is targeted to be rewritten so it will not get much developer attention until that happens and then the old code will get removed. The original developer no longer supports the code and we are trying to refactor all the functions to reuse code and to given consistent results regardless of what function you are using.

Sorry for the inconvenience, but these things take time and have to be worked in between other tasks.

@dropyghost
Copy link
Author

@cvvergara Sorry I dont know where to subscribe to get notification when new release appear. So that was the version available when I configure this PC and didnt change it since. Stack Builder is the app include in Postgres to allow you install plugins and other things, like postgis or pgAgent.

@dropyghost
Copy link
Author

dropyghost commented Dec 12, 2016

@woodbri Is ok, I understand. But I think you are mistaken, because as I show in the test, the result are different. My guess is when change the function didnt think be necesary route between same link, because didnt take offset into consideration.

But nevermind I patch it creating a case when the link is the same I create the Route myself.

    IF A.link_id = B.link_id THEN
        SELECT INTO offsetCost
                    ABS(ini_offset - end_offset) * tc   -- time cost
        FROM map.vzla_rto
        WHERE link_id = A.link_id;

	INSERT INTO traffic.Routes 
		(route_source_id, seq_id, node_id, link_id, cost)				
	VALUES  (int_route_source_id, 0, -1, A.link_id, offsetCost);

@cvvergara
Copy link
Member

yes, from 2.0 changes on the code were done because on 2.1 a developer added (on top of buggy code) the code for the pgr_trspViaEdges and pgr_trspViaVertex. And wrappers have being added since.
to "hide" some of the bugs.

@woodbri
Copy link
Contributor

woodbri commented Dec 13, 2016

@dropyghost OK, glad you have a work around solution that will work for you.

@sanak
Copy link
Member

sanak commented Dec 13, 2016

@dropyghost If your old pgRouting version is 2.0.0 on Windows,
there was the bug (#336) about trsp internal class initialization.
I fixed it on the following commit, but it may cause another issue.
848c7b8
I will check whether above my fix affect your test case, later.

@dropyghost
Copy link
Author

@sanak Again sorry for my english. Do you mean:

  1. pgrouting-2.2.2 has that bug, you solve it but hasnt been commit yet
  2. pgrouting-2.2.2 has that bug, you will handle on the next version
  3. pgrouting-2.2.0 has that bug but you solve it in 2.2

The problem is after solve the same link issue, I realize the process using pgrouting is causing my db to be frozen / hang up. Have to go back to slow old server again to process my data.

Im about to create a new bug regarding this issue.

@sanak
Copy link
Member

sanak commented Dec 23, 2016

@dropyghost
Sorry, my explanation might be bad and no progress about this.
I meant the following.

  1. pgrouting-2.0.0 has that bug, but I solve it in 2.0.1
    (The fix might be applied to pgrouting-2.2.x, but I have not checked it well...)

The problem is after solve the same link issue, I realize the process using pgrouting is causing my db to be frozen / hang up. Have to go back to slow old server again to process my data.

Okay, then some initialization parameter might be bad...

Im about to create a new bug regarding this issue.

Okay, please.
Thanks!

@cvvergara
Copy link
Member

I made more test, and I might say that the behaviour is undefined when the point is actually a vertex
So, as suggestion, use an offset like 0.00000000001 then it will be considered as a point that is not a vertex in the graph.

CREATE TABLE maptest as 
SELECT  671222::integer as id, 318255::integer as  source, 222698::integer as target, 14.02::float8 as cost, 14.02::float8 as reverse_cost UNION ALL
SELECT  671223, 222698, 36655, 197.16, 197.16 UNION ALL
SELECT  582877, 408918, 5556, 458.09, 458.09 UNION ALL
SELECT  582876, 318255, 408918, 3.89, 3.89 UNION ALL
SELECT  585280, 5556, 454424, 54.84, 54.84;
SELECT 5
q1
SELECT seq, id1 AS node, id2 AS edge, cost::numeric(11,4)
FROM pgr_trsp(
    'select * from maptest',
    582877,     
    0,          
    582877,     
    0.5,        
    true,        
    true,      
    null 
) PG ;
 seq | node | edge | cost 
-----+------+------+------
(0 rows)

q2
SELECT seq, id1 AS node, id2 AS edge, cost::numeric(11,4)
FROM pgr_trsp(
    'select * from maptest',
    582877,     
    0.0000000001,          
    582877,     
    0.5,        
    true,        
    true,      
    null 
) PG ;
 seq | node |  edge  |   cost   
-----+------+--------+----------
   0 |   -1 | 582877 | 229.0450
   1 |   -2 |     -1 |   0.0000
(2 rows)

q3
SELECT seq, id1 AS node, id2 AS edge, cost::numeric(11,4)
FROM pgr_trsp(
    'select * from maptest',
    582877,     
    0,         
    582877,     
    0.5,        
    true,        
    true,      
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
) PG ;
 seq | node |  edge  |   cost   
-----+------+--------+----------
   0 |   -1 | 582877 | 229.0450
(1 row)

q4
SELECT seq, id1 AS node, id2 AS edge, cost::numeric(11,4)
FROM pgr_trsp(
    'select * from maptest',
    582877,     
    0.0000000001,          
    582877,     
    0.5,        
    true,        
    true,      
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
) PG ;
 seq | node |  edge  |   cost   
-----+------+--------+----------
   0 |   -1 | 582877 | 229.0450
(1 row)

q5

@cvvergara
Copy link
Member

Note:
The previous suggestion hides the bug, it does not fix the bug

@cvvergara
Copy link
Member

Using the latest changes:

CREATE TABLE maptest as 
SELECT  671222::integer as id, 318255::integer as  source, 222698::integer as target, 14.02::float8 as cost, 14.02::float8 as reverse_cost UNION ALL
SELECT  671223, 222698, 36655, 197.16, 197.16 UNION ALL
SELECT  582877, 408918, 5556, 458.09, 458.09 UNION ALL
SELECT  582876, 318255, 408918, 3.89, 3.89 UNION ALL
SELECT  585280, 5556, 454424, 54.84, 54.84;

No restrictions:

SELECT *
FROM pgr_withPoints(
  $$SELECT * from maptest$$,
  $$SELECT * FROM (VALUES (1,582877, 0.5)) AS t(pid, edge_id, fraction)$$,
  408918, -1,
  details => false);	
 seq | path_seq |  node  |  edge  |  cost   | agg_cost 
-----+----------+--------+--------+---------+----------
   1 |        1 | 408918 | 582877 | 229.045 |        0
   2 |        2 |     -1 |     -1 |       0 |  229.045
(2 rows)

With Restrictions

from the sample data

CREATE TABLE restrictions (
    id SERIAL PRIMARY KEY,
    path BIGINT[],
    cost FLOAT
);

INSERT INTO restrictions (path, cost) VALUES
(ARRAY[4, 7], 100),
(ARRAY[8, 11], 100),
(ARRAY[7, 10], 100),
(ARRAY[3, 5, 9], 4),
(ARRAY[9, 16], 100);))

Then using the following query:

SELECT *
FROM pgr_trsp_withPoints(
  $$SELECT * FROM maptest$$,
  $$SELECT * FROM restrictions$$,
  $$SELECT * FROM (VALUES (1,582877, 0.5)) AS t(pid, edge_id, fraction)$$,
  408918, -1,
  details => false);	
SELECT *
 seq | path_seq | start_vid | end_vid |  node  |  edge  |  cost   | agg_cost 
-----+----------+-----------+---------+--------+--------+---------+----------
   1 |        1 |    408918 |      -1 | 408918 | 582877 | 229.045 |        0
   2 |        2 |    408918 |      -1 |     -1 |     -1 |       0 |  229.045
(2 rows)

@cvvergara cvvergara added this to the Release 3.4.0 milestone Mar 31, 2022
@cvvergara
Copy link
Member

Work has been done for TRSP on develop branch for version 3.4 (due to be released on September/October 2022:
#2238
Please check the documentation
https://docs.pgrouting.org/dev/en/TRSP-family.html
and the migration guide:
https://docs.pgrouting.org/dev/en/trsp_migration.html

For further similar problems with TRSP functions please open a new issue with the specific function name.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

4 participants