dijkstra_sp_directed() not returning valid paths

Question

I think I have found a major issue with pgrouting. I hope I am just doing something wrong due to my inexperience.

I am plotting the following query using OpenLayers.

select transform(the_geom, 900913) from dijkstra_sp_directed('ways', 52343, 39219, true, true)

On first glance this appears to work perfectly.

-->http://dl.dropbox.com/u/11502389/Screenshot-1.png

However if I successively label the nodes in each way, I learn that the path is not defined as I would expect. I expected the below output.

Way 0: 1, 2, ...n Way 1: 1, 2, ...n . . . Way n: 1, 2, ...n

What I actually get is a mess, some ways are ordered 1, 2, ...n and some are ordered in reverse n,... 2, 1

Here is a zoomed screenshot of the start of the path, this should be labeled 1, 2, 3, 4, from the screenshot you can see that its backwards.

-->http://dl.dropbox.com/u/11502389/Screenshot.png

Here is a zoomed screenshot of the end of the path, this is labeled correctly.

-->http://dl.dropbox.com/u/11502389/JourneyEnd.png

Why are some of the ways reversed? As far as I am concerned this is not a valid path. If a person was to follow this path (1, 2, 3), (5, 4, 3, 2, 1) they would have to teleport from the end of the first way to the end of the second way and then walk backwards towards the end of the first way.

More information

The query I am using to label the nodes is below

select (ST_DumpPoints(transform(linemerge(the_geom), 900913))).geom, (ST_DumpPoints(transform(linemerge(the_geom), 900913))).path from dijkstra_sp_directed('ways', 52343, 39219, true, true)

The data is OSM data for Ireland imported using osm2pgrouting and I followed this blog post to import the data.

Any help with this issue would be greatly appreciated.

Kind regards, Cathal Coffey

Here is my attempt to modify the function dijkstra_sp_directed. I think my logic is correct. I must be doing something that SQL does not like because when I run it I get the below error

ERROR: record "previous_path_result" is not assigned yet

DECLARE 
    r record;
    path_result record;
    v_id integer;
    e_id integer;
    geom geoms;
    query text;
    id integer;

    previous_path_result record;
    temp integer;

BEGIN
    id :=0;

    query := 'SELECT gid,the_geom,source,target FROM ' ||
          'shortest_path(''SELECT gid as id, source::integer, target::integer, ' || 
          'length::double precision as cost ';

    IF rc THEN query := query || ', reverse_cost ';  
    END IF;

    query := query || 'FROM ' ||  quote_ident(geom_table) || ''', ' || quote_literal(source) || 
          ' , ' || quote_literal(target) || ' , '''||text(dir)||''', '''||text(rc)||'''), ' || 
          quote_ident(geom_table) || ' where edge_id = gid ';

    FOR path_result IN EXECUTE query
        LOOP             
             geom.gid      := path_result.gid;
             geom.the_geom := path_result.the_geom;
             id            := id+1;
             geom.id       := id;

             IF NOT previous_path_result IS NULL THEN
                 IF NOT path_result.source = previous_path_result.target THEN
                     temp := previous_path_result.source;
                     previous_path_result.source := previous_path_result.target;
                     previous_path_result.target := temp;
                     geom.the_geom := ST_Reverse(geom.the_geom);
                 END IF;
             END IF;

             previous_path_result := path_result;            
             RETURN NEXT geom;

        END LOOP;
    RETURN;
END;

Answer 1

The function you use is a wrapper function that modifies the dijkstra core function (shortest_path()) to output the geometries of the shortest path query, so you can plot it on a map like you did.

If you try the core function you will only get a list of points, which should be in the correct order, right? See an example here: http://workshop.pgrouting.org/chapters/shortest_path.html

The reason why some edges are in the wrong direction is because their geometries are stored like this in the database. The result of dijkstra_sp_directed() is a list of geometries and you had to extend the wrapper to flip them if you want to have them always in the correct direction.