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.


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.


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


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.

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

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

    previous_path_result record;
    temp integer;

    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
             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;

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.

  • thank you for your reply. It seems odd to me that the default behavour for the wrapper function is to return a path with any of its ways reversed. Sure, these paths are visually appealing if they are graphed using a single color but they are not traversable, you cannot animate them, apply a gradient to them or offer directions based on them. – user2583 Apr 5 '11 at 14:42
  • I've been trying for an hour now and cannot figure out how to modify the function dijkstra_sp_directed(). I have never written an SQL function before. It seems to me that the following logic placed inside the FOR before RETURN NEXT geom; should do the trick. if geom.source != previous_geom.target geom.the_geom = ST_Reverse(geom.the_geom) Can you help me? A minute for a developer familiar with these functions might save me hours of guessing. – user2583 Apr 5 '11 at 14:52
  • I have tried explicitly assigning previous_path_result to NULL after I BEGIN but PostGres does not allow this. The error I get is ERROR: cannot assign non-composite value to a record variable – user2583 Apr 6 '11 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy