[pgrouting-users] Bug on Shooting Star

[Maria Arias de Reyna]

Hi,

I posted a bug[1] last month about a problem with the shortest path shooting 
star algorithm, but I didn't get any answer. So, I will ask here, hopefully 
someone will give me a clue:

At some point, the algorithm skips one edge/vertex and gets directly to the 
next one, creating a "new" edge.

The data I am working with:
INSERT INTO routing (id, source, target, cost, reverse_cost, x1, x2, y1, y2, 
rule, to_cost, the_geom) VALUES (1, 1, 2, 8, 8, 1, 3, 1, 1, '', 0, NULL);
INSERT INTO routing (id, source, target, cost, reverse_cost, x1, x2, y1, y2, 
rule, to_cost, the_geom) VALUES (2, 2, 4, 1000, 6, 3, 3, 1, 3, '', 0, NULL);
INSERT INTO routing (id, source, target, cost, reverse_cost, x1, x2, y1, y2, 
rule, to_cost, the_geom) VALUES (3, 2, 5, 4, 4, 3, 5, 1, 2, '', 0, NULL);
INSERT INTO routing (id, source, target, cost, reverse_cost, x1, x2, y1, y2, 
rule, to_cost, the_geom) VALUES (4, 6, 5, 3, 3, 5, 5, 4, 2, '', 0, NULL);
INSERT INTO routing (id, source, target, cost, reverse_cost, x1, x2, y1, y2, 
rule, to_cost, the_geom) VALUES (5, 4, 6, 10, 1000, 3, 5, 3, 4, '', 0, NULL);
INSERT INTO routing (id, source, target, cost, reverse_cost, x1, x2, y1, y2, 
rule, to_cost, the_geom) VALUES (6, 7, 6, 1000, 3, 4, 5, 4, 4, '', 0, NULL);
INSERT INTO routing (id, source, target, cost, reverse_cost, x1, x2, y1, y2, 
rule, to_cost, the_geom) VALUES (7, 7, 4, 4, 1000, 4, 3, 4, 3, '', 0, NULL);
INSERT INTO routing (id, source, target, cost, reverse_cost, x1, x2, y1, y2, 
rule, to_cost, the_geom) VALUES (8, 3, 4, 1000, 8, 1, 3, 3, 3, '', 0, NULL);

The SQL I am using is:

SELECT * from shortest_path_shooting_star( 
'select id as id, 
source::integer, 
target::integer, 
x1 ::double precision,
y1 ::double precision,
x2 ::double precision,
y2 ::double precision,
rule,
cost ::double precision,
to_cost ::double precision,
reverse_cost ::double precision 
from routing',
1,
8,
true,
true);

And the result it shows is:
vertex_id;edge_id;cost
1;1;8
2;3;4
6;4;3
7;5;10
4;8;1000

The result should have been something like:
1;1;8
2;3;4
5;4;3
6;6;3
7;7;4
4;8;8

I am using the Ubuntu version from the repositories:
SELECT version(); says "PostgreSQL 8.4.7 on x86_64-pc-linux-gnu, compiled by 
GCC gcc-4.4.real (Ubuntu 4.4.3-4ubuntu5) 4.4.3, 64-bit"
SELECT postgis_full_version(); says "POSTGIS="1.4.0" GEOS="3.1.0-CAPI-1.5.0" 
PROJ="Rel. 4.7.1, 23 September 2009" USE_STATS"

The pgrouting installed is the one from the subversion:
$ svn info
Ruta: .
URL: http://pgrouting.postlbs.org/svn/pgrouting/trunk
Raíz del repositorio: http://pgrouting.postlbs.org/svn/pgrouting
UUID del repositorio: d21bcd6f-0036-404f-87c1-d983b28855fd
Revisión: 358



[1]https://github.com/pgRouting/pgrouting/issues/31

-- 
María Arias de Reyna Domínguez
Área de Operaciones

Emergya Consultoría 
Tfno: +34 954 51 75 77 / +34 607 43 74 27
Fax: +34 954 51 64 73 
www.emergya.es