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

[sanak]

Hi Dave,

Yes, it is also necessary.
https://github.com/sanak/pgrouting4w/commit/fa8c5ff559344653a464f2c3416de0ef8c4ce393

By the way, in my environment(currently use MacOSX),
your 2nd result was as follows, and it is not same as 1st one.
====
pgrouting-workshop=# 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);
 seq | id
-----+----
   0 |  1
   1 |  0
   2 |  3
   3 |  2
(4 rows)
====

In your environment, is there no problem?

Regards,



2013/7/19 Dave Potts <dave.potts at pinan.co.uk>

>  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>
>
>> 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
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>
>
>
>  --
>  Ko Nagase (sanak)
> Georepublic Japan
> mail: geosanak at gmail.com
>         nagase at georepublic.co.jp
>
>
> _______________________________________________
> Pgrouting-users mailing listPgrouting-users at lists.osgeo.orghttp://lists.osgeo.org/mailman/listinfo/pgrouting-users
>
>
>
>
> _______________________________________________
> Pgrouting-users mailing listPgrouting-users at lists.osgeo.orghttp://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
>
>


-- 
Ko Nagase (sanak)
Georepublic Japan
mail: geosanak at gmail.com
        nagase at georepublic.co.jp
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20130719/00511d9f/attachment.html>