[pgrouting-users] Bug in TRSP?

pgRouting pgrouting-users
1

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

		deleteall();

		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) <= total_cost)

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?

Regards,

*Fabien*
2

Hi Ashraf,

Can you look at this and respond when you have a chance. Thanks!

Also, I have your enhancements to the TRSP, I started to merge them but got buried in work. I will get to them as soon as I have a free day to tackle it. I'm very excited to get them added to the code base.

Thanks so much.

Best regards,
   -Steve

On 2/11/2014 4:13 PM, Fabien Ancelin wrote:

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

deleteall();

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) <= total_cost)

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?

Regards,

/Fabien/

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users