[pgrouting-users] Bug in TRSP?

Fabien Ancelin fabien.ancelin at gmail.com
Tue Feb 11 13:13:24 PST 2014

Hello all,

There is a piece of logic in the trsp algorithm that I suspect is a bug. It
happens in the file GraphDefinition.cpp, line 426

		if(m_lStartEdgeId == m_lEndEdgeId)
			if(get_single_cost(1000.0, path, path_count))
				return 0;
		*err_msg = (char *)"Path Not Found";
		return -1;

Is there any reason why the get_single_cost function get passed an
absolute value. Even more is there any reason for the following clause
conditions in the function get_single_cost?

GraphDefinition.cpp, line 493
if(start_edge_info->m_dCost >= 0.0 && start_edge_info->m_dCost *
(m_dEndPart - m_dStartpart) <= total_cost)

GraphDefinition.cpp, line 506
if(start_edge_info->m_dReverseCost >= 0.0 &&
start_edge_info->m_dReverseCost * (m_dStartpart - m_dEndPart) <=

Shouldn't we have the following clause instead ?
if(start_edge_info->m_dCost >= 0.0)
if(start_edge_info->m_dReverseCost >= 0.0)

The issue is : it is possible to have the a route that starts and ends
on the same segments and that the cost associated with the used
portion of the segment is superior than 1000 (especially if you route
on long segments and your cost is in meters).

I have changed the line 493 ad 506 in my version of trsp so that it
doesn't test against the total cost and it seems to work fine. Is what
I report here a bug, or I am missing something in the way TRSP works?


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20140211/19a93798/attachment.html>

More information about the Pgrouting-users mailing list