[pgrouting-users] [Still an ISSUE] Re: suspected bug in TSP distance matrix pgRouting RC1 released

[sanak]

Hi Dave,

Thanks for your comment.

I just added a comment to the pull request(
https://github.com/pgRouting/pgrouting/pull/160 ).
(Because, tsp core algorithm analysis is too difficult for me...)

Thanks!



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

>  On 19/07/13 15:00, sanak wrote:
> Well spotted !
>
> yes it does matter,  I had just assumed because I got an answer it was all
> working, it seems that its not, so there still seems to be an issue :-(
>
> The answers should be indentical
> Dave
>
> 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
>
>
> _______________________________________________
> 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/3c7ddb50/attachment.html>