5

What will be the difference on the routing behaviour when I try to play with the directed and has_reverse_cost arguments on all the three routing algorithms?

Example: the following SQL queries give me a different result each time.

SELECT rt.gid, ST_AsGeoJSON(rt.the_geom) AS geojson, at_2po_4pgr.gid FROM at_2po_4pgr, (SELECT gid, the_geom FROM dijkstra_sp_delta_directed( 'at_2po_4pgr', 66126, 9013, 0.1, false, false) ) as rt WHERE at_2po_4pgr.gid=rt.gid;

SELECT rt.gid, ST_AsGeoJSON(rt.the_geom) AS geojson, at_2po_4pgr.gid FROM at_2po_4pgr, (SELECT gid, the_geom FROM dijkstra_sp_delta_directed( 'at_2po_4pgr', 66126, 9013, 0.1, true, false) ) as rt WHERE at_2po_4pgr.gid=rt.gid;

SELECT rt.gid, ST_AsGeoJSON(rt.the_geom) AS geojson, at_2po_4pgr.gid FROM at_2po_4pgr, (SELECT gid, the_geom FROM dijkstra_sp_delta_directed( 'at_2po_4pgr', 66126, 9013, 0.1, true, true) ) as rt WHERE at_2po_4pgr.gid=rt.gid;

I can understand if both are set to false but what if one is true and the other is false?

Any explanation please?

Thanks.

Improve this question

3 Answers 3

Reset to default
3

Only matched booleans make any sense. Unmatched ones are either irrelevant or 'broken':

  1. FALSE FALSE: Undirected graphs (“directed false”) ignore “has_reverse_cost” setting, which means you can travel in both directions between any pair of nodes and the cost is the same both ways.
  2. TRUE TRUE: This is a directed graph and the cost of reverse travel is taken from a reverse cost attribute column. For instance, if you have a one-way street, you would set this to be negative (which stops the link being used in the calculation), or perhaps your cost is fuel consumption rather than distance and the reverse link is uphill, in which case you would have a higher figure for the reverse direction.
  3. FALSE TRUE: This is an undirected graph, so setting the 'has_reverse_cost' to TRUE is irrelevant.
  4. TRUE FALSE: This is a directed graph, so setting the 'has_reverse_cost' to FALSE does not make any sense. PgRouting will expect a reverse_cost column in the data so this statement is broken.

So your only logical options are when both booleans match. Of course, that begs the question why the developers implemented the two booleans as it would indeed seem that the second one is redundant in all cases and only the 'directed' true/false option is necessary.

Improve this answer
2
  • i tried to re-read the latest pgrouting workshop tutorial, workshop.pgrouting.org/chapters/shortest_path.html, then i notice under the note tag on each routing algorithm, it mentions this "Undirected graphs (“directed false”) ignore “has_reverse_cost” setting" what exactly does try to tell me? that if i want either directed or undirected graph, just set the directed accordingly and ignore the has_reverse_cost? Commented Jan 16, 2013 at 4:01
  • Not quite. For an undirected graph set False False. For a directed graph make sure you have a 'reverse-cost' attribute and set True True. Commented Jan 16, 2013 at 8:51
1

I'm not really sure, but as far as I remember pgRouting creates edges on-the-fly each time you calculate a route. Hence a combination of FALSE TRUE does make sense because in this case pgRouting creates additional reverse ones. osm2po outputs undirected graphs with reverse_cost, meaning you should get correct results with regards to the one-ways. Here FALSE TRUE should be set. As a consequence TRUE TRUE is the combination which doesn't make sense. Because the reverse cost is implicitly set by the forward cost of the reverse edge. But maybe Daniel is following this thread and can give us a final best-practise.

Improve this answer
2
  • i tried to re-read the latest pgrouting workshop tutorial, workshop.pgrouting.org/chapters/shortest_path.html, then i notice under the note tag on each routing algorithm, it mentions this "Undirected graphs (“directed false”) ignore “has_reverse_cost” setting" what exactly does try to tell me? that if i want either directed or undirected graph, just set the directed accordingly and ignore the has_reverse_cost? Commented Jan 16, 2013 at 4:02
  • I've just checked it and my assumption above is correct. For osm2po-tables you'll have to set either FALSE TRUE or FALSE FALSE. The first pair does take oneways into account, the second ignores them. But I used shortest_path() instead of dijkstra_sp_delta_directed() which is a wrapper. The name implies that it expects directed graphs only. If so, don't use it for osm2po-tables. Commented Jan 16, 2013 at 8:45
1

The behaviour on matching booleans is trivial and well understood (Refer to answer provided by MappaGnosis). But non-matching booleans are not irrelevant and the corresponding behaviour justifies the need of these two arguments. I would try to state the behaviour with non-matching booleans with examples.

  1. False, True Ignores directed graph settings but distinguishes edges of the corresponding graph according to the direction in which it is travelled. Shown below are two example queries and outputs on a single segment path. Both queries are exactly similar except for the parameter settings. First one corresponds to False, False settings and the latter one corresponds to False, True settings:

Query-1

 select seq, id1 as node, id2 as edge, cost FROM pgr_dijkstra('SELECT gid AS id, source::integer, target::integer, length::double precision AS cost, length::double precision/2 AS reverse_cost FROM links_topology', (select source from links_topology where gid=199591), (select target from links_topology where gid=200466), false, false) as A;

Output:

 seq | node | edge | cost | -----+--------+--------+------------- 0 | 165702 | 199931 | 66.04336762 | 1 | 165969 | -1 | 0 |

Query-2

 select seq, id1 as node, id2 as edge, cost FROM pgr_dijkstra('SELECT gid AS id, source::integer, target::integer, length::double precision AS cost, length::double precision/2 AS reverse_cost FROM links_topology', (select source from links_topology where gid=199591), (select target from links_topology where gid=200466), false, true) as A;

Output:

 seq | node | edge | cost | -----+--------+--------+------------- 0 | 165702 | 199931 | 33.02168381 | 1 | 165969 | -1 | 0 |

The path segment in the route was from target node to source node of edge 199931. Choosing (False, False) settings ignored the reverse cost but (False, True) chose the reverse cost for computing shortest path.

  1. True, False Expects a directed graph but ignores reverse costs if provided which anyways wouldn't make sense because in a directed graph, edges can't be travelled in opposite direction.

Having understood the behaviour, one may ask:

How can (False, True) be used in a real world application?

There are two uses I can think of:

a) Reliably updating a map on temporary basis: can be done without making changes to the existing map to convert a two-way lane to one-way (make the reverse cost 0 for the required edges which are stored in a seperate table with which a join should be computed to get the reverse costs).

b) Fetching ETA: a 2-WAY road would have different time cost according to the speed differences in the opposite directions. Using a directed graph could be a solution, but then the graph size needs to be doubled which would have performance overheads on route computations and other graph based queries.

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.