[pgrouting-users] suspected bug in TSP distance matrix pgRouting RC1 released[SOLUTION]

[Dave Potts]

On 19/07/13 15:08, Dave Potts wrote:
I have found the problem, in the function int findEulerianPath(TSP *tsp) 
in the file src/tsp/src/tsplib.c


the code  says something like
int d,i,j,k,l,a

The varible  d is used to compare against a variable of type DTYPE, with 
the result that there seems to be an underflow/overflow issue

so the code needs to be changed to

     int *mst, *arc;
     DTYPE d;
     int i, j, k, l, a;
     int n, *iorder, *jorder;

having done,  I now get the expected result.

Dave.
> On 19/07/13 13:02, sanak wrote:
> Hi Sanak
>
> Thanks for your help
>
> I had the float version in my source base I changed it to a double, I 
> have done a make clean, install restarted the service, still have the 
> same problem :-(
>
> Dave
>> Hi Dave, Stephen,
>>
>> I encountered the same 
>> issue(https://github.com/pgRouting/pgrouting/issues/159 ),
>> so, I sent the pull 
>> request(https://github.com/pgRouting/pgrouting/pull/160 ).
>>
>> > Stephen
>> Could you check my pull request?
>>
>> Thanks,
>>
>>
>> 2013/7/19 Dave Potts <dave.potts at pinan.co.uk 
>> <mailto:dave.potts at pinan.co.uk>>
>>
>>     I have been trying to do some work which requires the tsp, some
>>     of my values have values of 0.1 in the dataset, I keep getting
>>     odd results.
>>
>>     So I tried a well known example from the  pgr _tsp distance page
>>     and it work as expected.
>>
>>     I then repeated the same example but reduced all of the distance
>>     by a factor off 10 and got an error.  Unless I have make a
>>     mistake in my understanding of the manual page, I think we might
>>     a problem where
>>
>>     -- version used
>>     select pgr_version();
>>                        pgr_version
>>     -------------------------------------------------
>>      (2.0.0-dev,v2.0.0-rc1,0,bf13fd7,develop,1.48.0)
>>     -- Use a example get a result set
>>     SELECT seq, id FROM
>>     pgr_tsp('{{0,1,3,3},{1,0,2,2},{3,2,0,2},{3,2,2,0}}'::float8[],1);
>>      seq | id
>>     -----+----
>>        0 |  1
>>        1 |  2
>>        2 |  3
>>        3 |  0
>>     (4 rows)
>>     -- repeat for reduce everything by  scale factor of 10  ie 1.0
>>     becomes 0.1 etc
>>
>>     SELECT seq, id FROM
>>     pgr_tsp('{{0,0.1,0.3,0.3},{0.1,0,0.2,0.2},{0.3,0.2,0,0.2},{0.3,0.2,0.2,0}}'::float8[],1);
>>
>>     ERROR:  Error TSP fail to findEulerianPath, check your distance
>>     matrix is valid.
>>
>>     As far as I understand it my matrix has 0's on the leading
>>     diangonal  and [a,b] == [b,a]
>>
>>     Dave.
>>     _______________________________________________
>>     Pgrouting-users mailing list
>>     Pgrouting-users at lists.osgeo.org
>>     <mailto:Pgrouting-users at lists.osgeo.org>
>>     http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>>
>>
>>
>> -- 
>> Ko Nagase (sanak)
>> Georepublic Japan
>> mail: geosanak at gmail.com <mailto:geosanak at gmail.com>
>> nagase at georepublic.co.jp <mailto:nagase at georepublic.co.jp>
>>
>>
>> _______________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>
>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20130719/87de856c/attachment-0001.html>