Wednesday, July 25, 2012

pgRouting's hardcoded behavior ruined my day

Or: How I worked 11 hours yesterday debugging one line of code.

WEIGHTING PATHS TO PREFER TRAILS

We have been using dijkstra_sp() for routing over these trails I've been talking about lately. Works great.

So we made an adjustment: for all of the trails which are actually Road, multiply its cost by 3.0 so the trails are more preferable. This was pretty simple:
-- the second line is new: the pathfinder will walk 3 blocks of trail vs 1 block of street
UPDATE trails SET cost=length;
UPDATE trails SET cost=length * 3.0 WHERE trail_type='Road' OR trail_type='Street';
Also works great: dijkstra_sp() now routes people out of their way to get them onto a trail, and routes them over streets only when necessary, and 3.0 seemed to be the magic number here. Yay!

ADD A BBOX FILTER AND IT WON'T WEIGHT ANYMORE

But dijkstra_sp_delta() was ignoring this weighting and routing over streets anyway. That's too bad: now that we have quintupled the volume of data, we could really use the performance boost. I cranked up the multiplier to 10.0, checked the node connectivity, and was definitely in a location where a road was straighter but trails were only slightly longer. But no, streets are straighter so that's what goes.

This went on for over two hours. I re-analyzed the trail network with tighter tolerance and with looser tolerance. I tried dijkstra_sp() and dijkstra_sp_delta() I tried astar_sp_delta() too and same thing. I even wrote test cases in Shooting Star and was very unimpressed with the results.

Yes, Dijkstra can account for weights but Dikstra-with-box cannot and neither can A* That can't possibly be true.

USE THE SOURCE!

The key was to mis-type a vertex ID. I got the "query argument to EXECUTE is null" message, meaning that something had failed to look up the vertex. I popped open routing_core_wrappers.sql so I could find the line and figure out what wasn't being found.

And I was horrified at what I saw:
query := 'SELECT gid,the_geom FROM ' ||
'shortest_path_astar(''SELECT gid as id, source::integer, ' ||
'target::integer, length::double precision as cost, ' ||
'x1::double precision, y1::double precision, x2::double ' ||
'precision, y2::double precision ';
Hold on a second! "length::double precision as cost" Really? Oh geez! The length field was being used as the cost, and the cost field was being ignored completely!

I looked over the rest of routing_core_wrappers.sql and did a search-n-replace of "length::double precision as cost" to "cost", then reloaded routing_core_wrappers.sql to replace the functions.

Success!

HARDCODED BEHAVIORS

At one point in the past, I found in my notes later, I had updated routing_core_wrappers.sql to correct the "length as cost" issue in dijkstra_sp() But I had not done it globally (that was back on Day One, I didn't even know if it was a good idea back then) including the A* and Dijkstra-with-bbox wrappers.

The pgRouting functions have other hardcoded field names too:
  • the primary key must be "gid"
  • the geometry must be "the_geom"
  • the cost field must be "length"
Fortunately, it's pretty easy to pop open the wrappers and correct these to suit your situation.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.