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

pgRouting pgrouting-users
1

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.

2

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@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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

–

Ko Nagase (sanak)
Georepublic Japan
mail: geosanak@gmail.com
nagase@georepublic.co.jp

3

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 :frowning:

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@pinan.co.uk <mailto:dave.potts@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@lists.osgeo.org
    <mailto:Pgrouting-users@lists.osgeo.org>
    http://lists.osgeo.org/mailman/listinfo/pgrouting-users

--
Ko Nagase (sanak)
Georepublic Japan
mail: geosanak@gmail.com <mailto:geosanak@gmail.com>
nagase@georepublic.co.jp <mailto:nagase@georepublic.co.jp>

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

4

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 :frowning:

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@pinan.co.uk <mailto:dave.potts@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@lists.osgeo.org
    <mailto:Pgrouting-users@lists.osgeo.org>
    http://lists.osgeo.org/mailman/listinfo/pgrouting-users

--
Ko Nagase (sanak)
Georepublic Japan
mail: geosanak@gmail.com <mailto:geosanak@gmail.com>
nagase@georepublic.co.jp <mailto:nagase@georepublic.co.jp>

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

5

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.

···

2013/7/19 Dave Potts <dave.potts@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 :frowning:

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,

_______________________________________________
Pgrouting-users mailing list
[Pgrouting-users@lists.osgeo.org](mailto:Pgrouting-users@lists.osgeo.org)
[http://lists.osgeo.org/mailman/listinfo/pgrouting-users](http://lists.osgeo.org/mailman/listinfo/pgrouting-users)


_______________________________________________
Pgrouting-users mailing list
[Pgrouting-users@lists.osgeo.org](mailto:Pgrouting-users@lists.osgeo.org)
[http://lists.osgeo.org/mailman/listinfo/pgrouting-users](http://lists.osgeo.org/mailman/listinfo/pgrouting-users)

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

–

Ko Nagase (sanak)
Georepublic Japan
mail: geosanak@gmail.com
nagase@georepublic.co.jp

2013/7/19 Dave Potts <dave.potts@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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

–

Ko Nagase (sanak)
Georepublic Japan
mail: geosanak@gmail.com
nagase@georepublic.co.jp

6

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 :frowning:

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@pinan.co.uk <mailto:dave.potts@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 :frowning:

    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@pinan.co.uk
    <mailto:dave.potts@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@lists.osgeo.org
        <mailto:Pgrouting-users@lists.osgeo.org>
        http://lists.osgeo.org/mailman/listinfo/pgrouting-users

    -- Ko Nagase (sanak)
    Georepublic Japan
    mail: geosanak@gmail.com <mailto:geosanak@gmail.com>
    nagase@georepublic.co.jp <mailto:nagase@georepublic.co.jp>

    _______________________________________________
    Pgrouting-users mailing list
    Pgrouting-users@lists.osgeo.org <mailto:Pgrouting-users@lists.osgeo.org>
    http://lists.osgeo.org/mailman/listinfo/pgrouting-users

    _______________________________________________
    Pgrouting-users mailing list
    Pgrouting-users@lists.osgeo.org <mailto:Pgrouting-users@lists.osgeo.org>
    http://lists.osgeo.org/mailman/listinfo/pgrouting-users

    _______________________________________________
    Pgrouting-users mailing list
    Pgrouting-users@lists.osgeo.org
    <mailto:Pgrouting-users@lists.osgeo.org>
    http://lists.osgeo.org/mailman/listinfo/pgrouting-users

--
Ko Nagase (sanak)
Georepublic Japan
mail: geosanak@gmail.com <mailto:geosanak@gmail.com>
nagase@georepublic.co.jp <mailto:nagase@georepublic.co.jp>

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

7

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@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 :frowning:

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,

_______________________________________________
Pgrouting-users mailing list
[Pgrouting-users@lists.osgeo.org](mailto:Pgrouting-users@lists.osgeo.org)
[http://lists.osgeo.org/mailman/listinfo/pgrouting-users](http://lists.osgeo.org/mailman/listinfo/pgrouting-users)

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

–

Ko Nagase (sanak)
Georepublic Japan
mail: geosanak@gmail.com
nagase@georepublic.co.jp

2013/7/19 Dave Potts <dave.potts@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 :frowning:

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,

_______________________________________________
Pgrouting-users mailing list
[Pgrouting-users@lists.osgeo.org](mailto:Pgrouting-users@lists.osgeo.org)
[http://lists.osgeo.org/mailman/listinfo/pgrouting-users](http://lists.osgeo.org/mailman/listinfo/pgrouting-users)


_______________________________________________
Pgrouting-users mailing list
[Pgrouting-users@lists.osgeo.org](mailto:Pgrouting-users@lists.osgeo.org)
[http://lists.osgeo.org/mailman/listinfo/pgrouting-users](http://lists.osgeo.org/mailman/listinfo/pgrouting-users)

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

–

Ko Nagase (sanak)
Georepublic Japan
mail: geosanak@gmail.com
nagase@georepublic.co.jp

2013/7/19 Dave Potts <dave.potts@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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

–

Ko Nagase (sanak)
Georepublic Japan
mail: geosanak@gmail.com
nagase@georepublic.co.jp