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

Dave Potts dave.potts at pinan.co.uk
Fri Jul 19 07:19:58 PDT 2013


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 
> <mailto: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
>>>     <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  <mailto:Pgrouting-users at lists.osgeo.org>
>>>     http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>>
>>
>>     _______________________________________________
>>     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
>
>
>     _______________________________________________
>     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

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


More information about the Pgrouting-users mailing list