[pgrouting-dev] tsp problem

[Jaime Casanova]

On Mon, Mar 4, 2013 at 11:23 AM, Stephen Woodbridge
<woodbri at swoodbridge.com> wrote:
> Hi Jaime,
>
> I'm not sure there is anyone that knows much about the original tsp
> integration still on the list.
>
> I am starting a project targeted to release a pgrouting 2.0. We have
> wishlist items in this plan to replace Gaul and cgal libraries if we have
> time to integrate a suitable replacement.
>
> If you are able to dig into this and create a pull request, I will be going
> through a lot of the open pull requests at some point in this process, but
> if we replace gaul that will be moot for 2.0. That said I expect there will
> be people that need the fix for the current releases.
>

Hi,

the function in https://github.com/pgRouting/gaul-devel we got this
function (which is the one that crashes)
"""
GAULFUNC entity *ga_get_entity_from_rank(population *pop, const
unsigned int rank)
  {
  if ( !pop ) die("Null pointer to population structure passed.");

  if ( rank > (unsigned) pop->size ) return NULL;

  return pop->entity_iarray[rank];
  }
"""


but the code in the file tsp_solver.cpp line 299 as i found it in
https://github.com/pgRouting/pgrouting (which is the one that fails),
calls that function with a rank == 0 so when pop->size == 0 it returns
pop->entity_iarray[rank]; which should be NULL. so it the end this is
basically NULL->fitness which causes the crash
"""
 if(score < ga_get_entity_from_rank(pop,0)->fitness)
        {
          score = ga_get_entity_from_rank(pop,0)->fitness;
          *fit = score;

          for(int l=0; l<cnum; l++)
            {
              p_ids[l] = ids[
                             ((int *)ga_get_entity_from_rank(pop,0)->
                              chromosome[0])[l]];
            }
        }
"""

attached is a simple one-line fix which basically adds an if
(pop->size > 0) before calling ga_get_entity_from_rank(), if you think
that's fine i can make the pull request or you can commit directly ;)

--
Jaime Casanova         www.2ndQuadrant.com
Professional PostgreSQL: Soporte 24x7 y capacitación
Phone: +593 4 5107566         Cell: +593 987171157
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tsp_solver_fix.patch
Type: application/octet-stream
Size: 1176 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20130305/7dc3b898/attachment.obj>