First edge and last edge don't respect the one way restriction

[carlofrancesco]

As told here http://pgrouting.postlbs.org/discussion/topic/308#message1160 shortest_path_shooting_star algorithm doesn't respect one-way restriction of the first and last edge:

look at this image:  http://img132.imageshack.us/img132/8185/error2ia.jpg

edge_id|vertex_id|cost|street 4311;790;1001000138.79372;790;"RE G. (VIA)" 4150;501;61.479488767088;501;"PACCHIOTTI G. (VIA)" 6114;856;1001000142.27532;856;"LIONETTO (STR. DEL)"

Query is

SELECT ".TABLE.".*, AsText??(".TABLE.".the_geom) AS wkt FROM ".TABLE.", shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost,

x1, y1, x2, y2, rule, to_cost FROM ".TABLE."', ".$startEdgegid?.", ".$endEdgegid?.", true, true) as rt

WHERE ".TABLE.".gid=rt.edge_id;

[anton]

Can you please tell me the pgRouting version number? Did you try latest version from SVN?

[carlofrancesco]

Version : latest svn - revision 352

shortest_path instead is not affected by this bug, but obviously it doesn't consider first edge but first node.

[carlofrancesco]

Same thing if i don't consider the graph "directed", considering only costs and reverse_costs.
query:

set enable_hashjoin=false;set enable_mergejoin=false;

SELECT rt.cost,strade_select.*
FROM strade_select, shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost,x1, y1, x2, y2, rule, to_cost FROM strade_select', 5788, 5448, false, true) as rt

WHERE strade_select.gid=rt.edge_id;

[carlofrancesco]

this image can tell you more:  http://img245.imageshack.us/img245/4746/exampleq.jpg
routing works well in the first 2 and last images; doesn't works in the 3rd. Infact in the 3rd example the cost for last edge is 1000033.04920574 (33.04920574 + 1000000)

[anton]

Oh, now I got it!

We are using Boost Graph Library for creating a graph for shortest path computation. All edge ids in that graph should be unique for proper Shooting* computation, So for each edge we create 2 - one for normal direction (from source to target) and one for reverse direction (from target to source). For reverse direction edge we also calculate new unique id, which is calculated as max_id + id. OK, there is no any problem when edges like this are in the middle of a path, but if you start with an edge to calculate a shortest path with Shooting* (same with target edge) you specify an id, which might happen to be an id of reverse direction edge with really hight cost in case of one way street.

To fix this bug I'm going to check if there is an alternative for choosen source and target edges with lower costs before path calculation. Please wait for a while - I need some time to brush up my Shooting* skills :)

[carlofrancesco]

Changing from directed graph to undirected and using cost and reverse_cost seems that only last edge doesn't respect the one-way direction. The first edge always respect it. I'm trying many times, but seems it works. Problem remain on the last edge

[anton]

Wait, undirected graph has same cost for both directions, so there shouldn't be any problem with it.

[carlofrancesco]

Yes my fault sorry. The last edge problem is not solved by these querys:

set enable_hashjoin=false;set enable_mergejoin=false;SELECT ".TABLE.".*, AsText?(".TABLE.".the_geom) AS wkt, rt.cost as costo FROM ".TABLE.", shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost,

x1, y1, x2, y2, rule, to_cost FROM ".TABLE."', ".$startEdgegid?.", ".$endEdgegid?.", false, true) as rt

WHERE ".TABLE.".gid=rt.edge_id;

or this:

set enable_hashjoin=false;set enable_mergejoin=false;SELECT ".TABLE.".*, AsText?(".TABLE.".the_geom) AS wkt, rt.cost as costo FROM ".TABLE.", shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost,

x1, y1, x2, y2, rule, to_cost FROM ".TABLE."', ".$startEdgegid?.", ".$endEdgegid?.", true, true) as rt

WHERE ".TABLE.".gid=rt.edge_id;

[anton]

Can you please try the newest version from SVN now?

[carlofrancesco]

ERROR: Error computing path: Source edge not found

[carlofrancesco]

same problem regenrating tables from zero doing this:

##Prepare the new table for Dijkstra by adding source, target, and length columns. In this #example “length” will be the cost of the edges.: ALTER TABLE strade_select ADD COLUMN source integer; ALTER TABLE strade_select ADD COLUMN target integer; ALTER TABLE strade_select ADD COLUMN length double precision;

##Create the network topology in the “strade_select” table. Also populate the “length” field ##which is to be the edge cost in the network topology.

SELECT assign_vertex_id('strade_select', 0.00001, 'the_geom', 'gid'); UPDATE strade_select SET length = length(the_geom);

CREATE INDEX source_idx ON strade_select(source);

CREATE INDEX target_idx ON strade_select(target);

CREATE INDEX geom_idx ON strade_select USING GIST(the_geom GIST_GEOMETRY_OPS);

ALTER TABLE strade_select ADD COLUMN cost double precision; ALTER TABLE strade_select ADD COLUMN reverse_cost double precision; UPDATE strade_select SET cost=length(the_geom), reverse_cost=length(the_geom);

#Prepare routing table for A-Star

Add x1, y1 and x2, y2 column

ALTER TABLE strade_select ADD COLUMN x1 double precision; ALTER TABLE strade_select ADD COLUMN y1 double precision; ALTER TABLE strade_select ADD COLUMN x2 double precision; ALTER TABLE strade_select ADD COLUMN y2 double precision; UPDATE strade_select SET x1 = x(startpoint(the_geom)); UPDATE strade_select SET y1 = y(startpoint(the_geom)); UPDATE strade_select SET x2 = x(endpoint(the_geom)); UPDATE strade_select SET y2 = y(endpoint(the_geom));

##Prepare routing table for Shooting-Star ALTER TABLE strade_select ADD COLUMN to_cost double precision; ALTER TABLE strade_select ADD COLUMN rule text;

#query set enable_hashjoin=false;set enable_mergejoin=false; SELECT strade_select.*, AsText?(strade_select.the_geom)

AS wkt FROM strade_select, shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost,

x1, y1, x2, y2, rule, to_cost FROM strade_select', 1244, 1290, true, true) as rt

WHERE strade_select.gid=rt.edge_id;

[carlofrancesco]

I can confirm that installing all from scratch shooting_star doesn't work. Alway result query is :

ERROR: Error computing path: Source edge not found

[carlofrancesco]

I have updated to revision 354, and now shooting star works again with same problem for the first and last edge.

[jcelda]

Dear collegues,

We are using pg_routing at www.icv.gva.es for experimental routing, and I appreciate a problem, surely related to this ticket issue.

In my roadmap (entire graph of valencian community roads network, spain) I noticed that the first edge *always* act as "one way direction".

If you are insterested on it, I can prepare some sample pictures and data to testcasing the issue.

[anton]

I am aware about this problem and I am really sorry about this. The problem is with the graph construction, not with the algorithm itself. Unfortunately, I can fix this problem right now, because currently I have no access to any sample data to test and debug. It would be really great if you could provide me small piece of data I can install on my laptop together with sample queries.

[carlofrancesco]

Strade_select doesn't working with shooting star

[carlofrancesco]

I have attached Strade_Select.sql.tar.bz2. Unbzip this and do this:

createdb -U postgres edimap
createlang -U postgres plpgsql edimap
psql -U postgres -f /usr/share/postgresql-8.3-postgis/lwpostgis.sql -d edimap
psql -U postgres -f /usr/share/postgresql-8.3-postgis/spatial_ref_sys.sql -d edimap
psql -U postgres -f /usr/share/postlbs/routing_core.sql -d edimap
psql -U postgres -f /usr/share/postlbs/routing_core_wrappers.sql -d edimap
psql -U postgres -f /usr/share/postlbs/routing_topology.sql -d edimap
psql -U postgres -f /usr/share/postlbs/routing_tsp.sql -d edimap
psql -U postgres -f /usr/share/postlbs/routing_tsp_wrappers.sql -d edimap
psql -U postgres -f /usr/share/postlbs/routing_dd.sql -d edimap
psql -U postgres -f /usr/share/postlbs/routing_dd_wrappers.sql -d edimap

psql -U postgres -f Strade_Select.sql -d edimap


##Prepare the new table for Dijkstra by adding source, target, and length columns. In this example “length” will be the cost of the edges.:
ALTER TABLE strade_select ADD COLUMN source integer;
ALTER TABLE strade_select ADD COLUMN target integer;
ALTER TABLE strade_select ADD COLUMN length double precision;


##Create the network topology in the “totalpro” table. Also populate the “length” field which is to be the edge cost in the network topology.

SELECT assign_vertex_id('strade_select', 0.00001, 'the_geom', 'gid');
UPDATE strade_select SET length = length(the_geom);

CREATE INDEX source_idx ON strade_select(source);

CREATE INDEX target_idx ON strade_select(target);

CREATE INDEX geom_idx ON strade_select USING GIST(the_geom GIST_GEOMETRY_OPS);

##After create edge costs

ALTER TABLE strade_select ADD COLUMN cost double precision;
ALTER TABLE strade_select ADD COLUMN reverse_cost double precision;
UPDATE strade_select SET cost=length(the_geom), reverse_cost=length(the_geom)

##Update with oneway defined in the coloumn "direzione"
## direzione=-1: oneway against edge direction
## direzione=1: oneway in the same edge direction

UPDATE strade_select SET reverse_cost=reverse_cost + 1000000 WHERE direzione = 1;
UPDATE strade_select SET cost=cost + 1000000 WHERE direzione = -1;
#######################




#Prepare routing table for A-Star Adding x1, y1 and x2, y2 column

ALTER TABLE strade_select ADD COLUMN x1 double precision;
ALTER TABLE strade_select ADD COLUMN y1 double precision;
ALTER TABLE strade_select ADD COLUMN x2 double precision;
ALTER TABLE strade_select ADD COLUMN y2 double precision;
UPDATE strade_select SET x1 = x(startpoint(the_geom));
UPDATE strade_select SET y1 = y(startpoint(the_geom));
UPDATE strade_select SET x2 = x(endpoint(the_geom));
UPDATE strade_select SET y2 = y(endpoint(the_geom));

###Prepare routing table for Shooting-Star
ALTER TABLE strade_select ADD COLUMN to_cost double precision;
ALTER TABLE strade_select ADD COLUMN rule text;

[carlofrancesco]

Update: query that doesn't works for me:

set enable_hashjoin=false;set enable_mergejoin=false;

SELECT rt.cost,strade_select.* FROM strade_select, shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM strade_select', 856, 575, true, true) as rt

WHERE strade_select.gid=rt.edge_id;

Two edge id that doesn't works to me are from 856 to 575. There are others. If you do not have my same topology, you have to find two one way streets, and make route between them

[anton]

Please see [355] - the bug is partially fixed. The route is correct now, but the cost in output is always a value of 'cost' column even if 'reverse_cost' was used in the calculation. Give me a little bit more time to fix this, but I encourage you to try it in the current stage.

[carlofrancesco]

I have updated to revision 355. Now it doesn't consider reverse_cost but only cost. It doesn't work on my map. Example of query (on my map i have shared here)

set enable_hashjoin=false;set enable_mergejoin=false;

SELECT rt.cost,strade_select.* FROM strade_select, shortest_path_shooting_star ('SELECT gid as id, source, target, cost, reverse_cost, x1, y1,

x2, y2, rule, to_cost FROM strade_select', 500, 502, true, true) as rt

WHERE strade_select.gid=rt.edge_id;

It goes against two one-ways... (on a primary way he goes aganist all edges) In general all route don't work. I have only updated pgrouting. I have to do something else? (eg. update boost graph library or other things)

[anton]

It seems strange because for me it works, the paths are correct, but yes - as I told it outputs wrong cost sometimes.

OK, can you please upload full dump of your table with your topology? Now we have different vertex ids, so I want to test it with exactly the same queries you are trying to run.

[carlofrancesco]

what i'm doing:

1) rm /usr/lib/postgresql/8.3/lib/librouting.so /usr/share/postlbs/routing_core.sql /usr/share/postlbs/routing_core_wrappers.sql /usr/share/postlbs/routing_topology.sql /usr/share/postlbs/matching.sql /usr/lib/postgresql/8.3/lib/librouting_tsp.so /usr/lib/postgresql/8.3/lib/librouting_tsp.so /usr/share/postlbs/routing_tsp.sql /usr/share/postlbs/routing_tsp_wrappers.sql /usr/lib/postgresql/8.3/lib/librouting_dd.so /usr/share/postlbs/routing_dd.sql /usr/share/postlbs/routing_dd_wrappers.sql

2)svn checkout http://pgrouting.postlbs.org/svn/pgrouting/trunk pgrouting cd pgrouting/ cmake -DWITH_TSP=ON -DWITH_DD=ON . make sudo make install

3)pg_dump -U postgres edimap > /root/Scrivania/edimap.sql (i'll attach it on this tiket) to restore it psql edimap < /root/Scrivania/edimap.sql

4)example of a query that doesn't work:

set enable_hashjoin=false;set enable_mergejoin=false;

SELECT rt.cost,strade_select.* FROM strade_select, shortest_path_shooting_star ('SELECT gid as id, source, target, cost, reverse_cost, x1, y1,

x2, y2, rule, to_cost FROM strade_select', 790, 3771, true, true) as rt

WHERE strade_select.gid=rt.edge_id;

[carlofrancesco]

Compressed is 650 Kb... i have to find an service that host my file

[carlofrancesco]

here dump of my DB  http://89.97.190.173/edimap.sql.bz2

[carlofrancesco]

example: set enable_hashjoin=false;set enable_mergejoin=false;

SELECT rt.cost,strade_select.* FROM strade_select, shortest_path_shooting_star ('SELECT gid as id, source, target, cost, reverse_cost, x1, y1,

x2, y2, rule, to_cost FROM strade_select', 843, 416, true, true) as rt

WHERE strade_select.gid=rt.edge_id;

i don't know if it consider at random cost or reverse_cost. It displays only costs. In this case the route is wrong because all edges are traversed against one-way direction

1000116.22245978;843;"RE G. (VIA)";-1 1000116.22245978;843;"RE G. (VIA)";-1 40.237235941973;561;"VALGIOIE (VIA)";0 196.529918305235;502;"LIONETTO (STR. DEL)";1 21.2494715007809;842;"LIONETTO (STR. DEL)";1 10.605542846196;6755;"FRANCIA (C.SO)";0 18.1006571444934;536;"POZZO STRADA (VIA)";0 59.9363024515402;467;"POZZO STRADA (VIA)";0 97.7238665913425;554;"SARRE (VIA)";0 66.9111540706219;563;"QUART (VIA)";0 105.823782069828;559;"S. ANTONINO (VIA)";0 130.59957886609;416;"SAGRA DI S. MICHELE (VIA)";1

[carlofrancesco]

This query fault on first edge

set enable_hashjoin=false;set enable_mergejoin=false;

SELECT rt.cost,strade_select.* FROM strade_select, shortest_path_shooting_star ('SELECT gid as id, source, target, cost, reverse_cost, x1, y1,

x2, y2, rule, to_cost FROM strade_select', 430, 500, true, true) as rt

WHERE strade_select.gid=rt.edge_id;

[anton]

I tried your query and it works for me.

test=# select * from shortest_path_shooting_star('select gid as id, 
source, target, cost, reverse_cost, rule, to_cost,x1,y1,x2,y2 from 
strade_select',430,500,true,true);
 vertex_id | edge_id |       cost       
-----------+---------+------------------
      1044 |     430 | 1000188.76949661
      1501 |     805 | 44.6598253467252
      1474 |     779 |  77.033116571413
      1473 |    1018 |  99.205481396254
      1037 |     500 | 1000145.45188208
(5 rows)

As I told you, it DISPLAYS always 'cost' value, but USES 'cost' or 'reverse_cost' when it's needed. I need some more time to fix the cost display issue.

[carlofrancesco]

Yes, it is the same for me. But for edge_id = 430 (first edge) it considers COST. Infact to go from 430 to 805 (they have same endpoint ) I have to go from:

StartPoint? 430, EndPoint? 430 ---------------> Endpoint 805, StartPoint? 805.

So I have to consider Cost of 430 ------------> Reverse_Cost 805

Ok ?

So first edge (gid=430) consider cost an it has a value of 1000188.76949661

gid | x1 | y1 | x2 | y2 | cost | reverse_cost

---

430 | 391843.90625 | 4992550 | 391921.6875 | 4992722 | 1000188.76949661 | 188.769496613098 805 | 391963.1875 | 4992705.5 | 391921.6875 | 4992722 | 44.6598253467252 | 44.6598253467252

[carlofrancesco]

Yes, it is the same for me. But for edge_id = 430 (first edge) it

considers COST. Infact to go from 430 to 805 (they have same endpoint ) I have to go from:

StartPoint? 430, EndPoint? 430 ---------------> Endpoint 805, StartPoint? 805.

So I have to consider Cost of 430 ------------> Reverse_Cost 805

Ok ?

So for the first edge (gid=430) pgrouting considers COST and it has a value of 1000188.76949661

{{{edimap=# select gid,x1,y1,x2,y2,cost,reverse_cost from strade_select where gid = 430 or gid=805;

gid | x1 | y1 | x2 | y2 | cost | reverse_cost

---

805 | 391963.1875 | 4992705.5 | 391921.6875 | 4992722 | 44.6598253467252 | 44.6598253467252 430 | 391843.90625 | 4992550 | 391921.6875 | 4992722 | 1000188.76949661 | 188.769496613098

(2 rows) }}}

[anton]

OK, once again. It doesn't CONSIDER only cost, it SHOWS only cost. The route is calculated now with taking one way streets for start and end in account. It takes cost or reverse_cost when it is needed. But when it OUTPUTS the result it SHOWS only cost (even if reverse_cost was used for the calculation). It is also a bug and I'm going to fix it ASAP, I just wanted to make sure that a route (an order of visited edges) is correct now.

OK, now we could make sure that the path is correct, so now I start fixing the cost issue.

[carlofrancesco]

I have understood it... I know infact for the edge 500 pgrounting says cost=1000188.76949661 but he is correctly considering reverse cost=188.769496613098 How i can say it? In this way:

select gid,x1,y1,x2,y2,cost,reverse_cost from strade_select where gid = 1018 or gid=500;
 gid  |      x1      |    y1     |      x2      |    y2     |       cost       |   reverse_cost   
------+--------------+-----------+--------------+-----------+------------------+------------------
 1018 | 392137.40625 | 4992680.5 |  392038.8125 | 4992691.5 |  99.205481396254 |  99.205481396254
  500 | 392116.90625 | 4992536.5 | 392137.40625 | 4992680.5 | 1000145.45188208 | 145.451882077889
(2 rows)

So startpoint of 1018 = endpoint 500. So? So I have to go from: enpoint 1018 - startpoint 1018 ------> endpoint 500 - startpoint 500 in other words I'm considering: Reverse_Cost 1018 ------> Reverse cost 500

And what about for 430->805? Just same thing:

edimap=# select gid,x1,y1,x2,y2,cost,reverse_cost from strade_select where gid = 430 or gid=805;
 gid |      x1      |    y1     |     x2      |   y2    |       cost       |   reverse_cost   
-----+--------------+-----------+-------------+---------+------------------+------------------
 805 |  391963.1875 | 4992705.5 | 391921.6875 | 4992722 | 44.6598253467252 | 44.6598253467252
 430 | 391843.90625 |   4992550 | 391921.6875 | 4992722 | 1000188.76949661 | 188.769496613098

Endpoint of 430 is the SAME of endpoint of 805. So? So the path is this:

startpoint 430 - endpoint 430 --------------> endpoint 805 - startpoint 805 in other words i'm considering: COST 430 -> REVERSE_COST 805

In this pgrouting faults. I KNOW THAT SOMETIMES HE SHOWS COST BUT IT IS CONSIDERING REVERSE_COST BUT IN THIS CASE HE SHOWS COST AND IT IS CONSIDERING COST and it is 1000188.76949661. TAHT'S NORMAL BECAUSE IN THE PATH FROM 430 TO 805 I TRAVERSE 430 IN THE SAME DIRECTION OF THE EDGE SO I MUST CONSIDER COST.

In the example 1018 -> 500 instead both 1018 and 500 are traversed against their edges direction.

[carlofrancesco]

Hi Mr. Anton. Try from 451 to 575 all edge are taken against one-way direction (infact reverse_cost is 100000000)

set enable_hashjoin=false;set enable_mergejoin=false;

SELECT rt.cost,strade_select.* FROM strade_select, shortest_path_shooting_star ('SELECT gid as id, source, target, cost, reverse_cost, x1, y1,

    x2, y2, rule, to_cost FROM strade_select', 451, 575, true, true) as rt

        WHERE strade_select.gid=rt.edge_id;

[Dzouzeph]

Can I ask you if you solved problem you mentioned here somehow? I had same problem and dont know how to solve it.

[carlofrancesco]

Replying to carlofrancesco:

Hi Mr. Anton. Try from 451 to 575 all edge are taken against one-way direction (infact reverse_cost is 100000000) {{{ set enable_hashjoin=false;set enable_mergejoin=false; SELECT rt.cost,strade_select.* FROM strade_select, shortest_path_shooting_star ('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM strade_select', 451, 575, true, true) as rt WHERE strade_select.gid=rt.edge_id; }}}

I haven't resolved yet. I'm using A-star now instead of shooting star. In other post Anton explained the reasons of the problem. When i have time i will investigate again. Bye !