[pgrouting-users] tsp problem

Jaime_Casanova · March 22, 2011, 8:09pm

Hi,

I installed pgrouting with tsp on a centos 5 machine with postgres
8.4.5 and postgis 1.3.6.
When i tried to run this query:
"""
SELECT *
FROM tsp_astar_directed('view_viasnodo','38151,38151,35604,35586,20948,39935,35457,40636,40242,35485,19143,40079,40335,40058,19058',38147,12000,false,false);
"""

i get this message "ERROR: relation "tsp_test" does not exist at
character 328" which is because the function tsp_astar_directed() in
routing_tsp_wrappers.sql has an UNION ALL that takes values from that
table... i workaround that problem creating a dummy tsp_test table...

but then when i try the same select i get "segmentation fault", this
is the backtrace:
"""
(gdb) bt
#0 0x00b02f7b in tsp_seed (pop=0x9430ee0, adam=0x9431090) at
/root/pgrouting-1.05/extra/tsp/src/tsp_solver.cpp:84
#1 0x00337b66 in gaul_population_fill (pop=0x9430ee0, num=88) at ga_core.c:823
#2 0x0034683f in ga_evolution (pop=0x9430ee0, max_generations=88) at
ga_optim.c:2415
#3 0x00b0315b in find_tsp_solution (num=22, dist=0xb04240,
p_ids=0xbfecb560, source=38147, fit=0xbfecb600, err_msg=0x0)
at /root/pgrouting-1.05/extra/tsp/src/tsp_solver.cpp:296
#4 0x00b02b7c in solve_tsp (fcinfo=0xbfecb6c4) at
/root/pgrouting-1.05/extra/tsp/src/tsp.c:345
#5 tsp (fcinfo=0xbfecb6c4) at /root/pgrouting-1.05/extra/tsp/src/tsp.c:401
#6 0x08191002 in ExecMakeTableFunctionResult ()
#7 0x0819dbd4 in ?? ()
#8 0x081924bf in ExecScan ()
#9 0x0819db59 in ExecFunctionScan ()
#10 0x0818ad8f in ExecProcNode ()
#11 0x081888ab in standard_ExecutorRun ()
#12 0x0823917e in ?? ()
#13 0x08239f44 in PortalRunFetch ()
#14 0x081a56b0 in ?? ()
#15 0x00280253 in ?? () from /usr/lib/pgsql/plpgsql.so
#16 0x0027f1b1 in ?? () from /usr/lib/pgsql/plpgsql.so
#17 0x0027ecaf in ?? () from /usr/lib/pgsql/plpgsql.so
#18 0x002816ff in plpgsql_exec_function () from /usr/lib/pgsql/plpgsql.so
#19 0x00276028 in plpgsql_call_handler () from /usr/lib/pgsql/plpgsql.so
#20 0x08191002 in ExecMakeTableFunctionResult ()
#21 0x0819dbd4 in ?? ()
#22 0x08192584 in ExecScan ()
#23 0x0819db59 in ExecFunctionScan ()
#24 0x0818ad8f in ExecProcNode ()
#25 0x081888ab in standard_ExecutorRun ()
#26 0x0823917e in ?? ()
#27 0x0823a20b in PortalRun ()
#28 0x08235912 in ?? ()
#29 0x082367e1 in PostgresMain ()
#30 0x0820a0ea in ?? ()
#31 0x0820b112 in PostmasterMain ()
#32 0x081b5be0 in main ()
"""

which points at this:
"""
boolean tsp_seed(population *pop, entity *adam)
{
int i,s,tmp;
int *data;

data = (int *)adam->chromosome[0];

  for (i=0; i<pop->len_chromosomes; i++)
  {
    data[i] = i;
  }

  for (i=0; i<pop->len_chromosomes; i++)
  {
    if(ids[data[i]] == source_id)
      s = i;
  }

  tmp = data[0];
  data[0] = data[s]; // this line is the one with the problem
  data[s] = tmp;

return TRUE;
}
"""

any ideas?

--
Jaime Casanova www.2ndQuadrant.com
Professional PostgreSQL: Soporte y capacitación de PostgreSQL

Jaime_Casanova · March 4, 2013, 3:38pm

On Tue, Mar 22, 2011 at 3:09 PM, Jaime Casanova <jaime@2ndquadrant.com> wrote:

Hi,

I installed pgrouting with tsp on a centos 5 machine with postgres
8.4.5 and postgis 1.3.6.
When i tried to run this query:
"""
SELECT *
FROM tsp_astar_directed('view_viasnodo','38151,38151,35604,35586,20948,39935,35457,40636,40242,35485,19143,40079,40335,40058,19058',38147,12000,false,false);
"""

i get this message "ERROR: relation "tsp_test" does not exist at
character 328" which is because the function tsp_astar_directed() in
routing_tsp_wrappers.sql has an UNION ALL that takes values from that
table... i workaround that problem creating a dummy tsp_test table...

but then when i try the same select i get "segmentation fault", this
is the backtrace:

I posted this on 2011 but it seems i posted in the users list. I also
created issue # 27 (https://github.com/pgRouting/pgrouting/issues/27)
on github.
On that issue someone suggested to replace al ocurrences of "tsp_test"
with " ' || quote_ident(geom_table) || ' ", which i did (recently) but
now i get this other crash (which i reported in a comment on that same
issue).

"""
Core was generated by `postgres: postgres db [local] SELECT '.
Program terminated with signal 11, Segmentation fault.
#0 0x00007f301738965d in find_tsp_solution (num=, dist=,
p_ids=0x7fff89d10b40, source=,
fit=0x7fff89d10be8, err_msg=) at
/usr/src/debug/pgrouting-1.05/extra/tsp/src/tsp_solver.cpp:299
299 if(score < ga_get_entity_from_rank(pop,0)->fitness)
"""

as you can see this is failing at tsp_solver line 299 which is an "if
" statement and the only thing i can see as a possible problem is the
function ga_get_entity_from_rank() which comes from GAUL.

ideas?

--
Jaime Casanova www.2ndQuadrant.com
Professional PostgreSQL: Soporte 24x7 y capacitación
Phone: +593 4 5107566 Cell: +593 987171157

Stephen_Woodbridge1 · March 4, 2013, 4:23pm

Hi Jaime,

I'm not sure there is anyone that knows much about the original tsp integration still on the list.

I am starting a project targeted to release a pgrouting 2.0. We have wishlist items in this plan to replace Gaul and cgal libraries if we have time to integrate a suitable replacement.

If you are able to dig into this and create a pull request, I will be going through a lot of the open pull requests at some point in this process, but if we replace gaul that will be moot for 2.0. That said I expect there will be people that need the fix for the current releases.

-Steve W

On 3/4/2013 10:38 AM, Jaime Casanova wrote:

On Tue, Mar 22, 2011 at 3:09 PM, Jaime Casanova <jaime@2ndquadrant.com> wrote:

Hi,

I installed pgrouting with tsp on a centos 5 machine with postgres
8.4.5 and postgis 1.3.6.
When i tried to run this query:
"""
SELECT *
FROM tsp_astar_directed('view_viasnodo','38151,38151,35604,35586,20948,39935,35457,40636,40242,35485,19143,40079,40335,40058,19058',38147,12000,false,false);
"""

i get this message "ERROR: relation "tsp_test" does not exist at
character 328" which is because the function tsp_astar_directed() in
routing_tsp_wrappers.sql has an UNION ALL that takes values from that
table... i workaround that problem creating a dummy tsp_test table...

but then when i try the same select i get "segmentation fault", this
is the backtrace:

I posted this on 2011 but it seems i posted in the users list. I also
created issue # 27 (https://github.com/pgRouting/pgrouting/issues/27)
on github.
On that issue someone suggested to replace al ocurrences of "tsp_test"
with " ' || quote_ident(geom_table) || ' ", which i did (recently) but
now i get this other crash (which i reported in a comment on that same
issue).

"""
Core was generated by `postgres: postgres db [local] SELECT '.
Program terminated with signal 11, Segmentation fault.
#0 0x00007f301738965d in find_tsp_solution (num=, dist=,
p_ids=0x7fff89d10b40, source=,
fit=0x7fff89d10be8, err_msg=) at
/usr/src/debug/pgrouting-1.05/extra/tsp/src/tsp_solver.cpp:299
299 if(score < ga_get_entity_from_rank(pop,0)->fitness)
"""

as you can see this is failing at tsp_solver line 299 which is an "if
" statement and the only thing i can see as a possible problem is the
function ga_get_entity_from_rank() which comes from GAUL.

ideas?

--
Jaime Casanova www.2ndQuadrant.com
Professional PostgreSQL: Soporte 24x7 y capacitación
Phone: +593 4 5107566 Cell: +593 987171157
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

Dave_Potts · March 4, 2013, 7:48pm

On 04/03/13 16:23, Stephen Woodbridge wrote:
Hi Steve,

Whats going to be included in pgrouting 2.0
What is in the wish list,
Which platforms will be supported ?

Dave.

Hi Jaime,

I'm not sure there is anyone that knows much about the original tsp integration still on the list.

I am starting a project targeted to release a pgrouting 2.0. We have wishlist items in this plan to replace Gaul and cgal libraries if we have time to integrate a suitable replacement.

If you are able to dig into this and create a pull request, I will be going through a lot of the open pull requests at some point in this process, but if we replace gaul that will be moot for 2.0. That said I expect there will be people that need the fix for the current releases.

-Steve W

On 3/4/2013 10:38 AM, Jaime Casanova wrote:

On Tue, Mar 22, 2011 at 3:09 PM, Jaime Casanova <jaime@2ndquadrant.com> wrote:

Hi,

I installed pgrouting with tsp on a centos 5 machine with postgres
8.4.5 and postgis 1.3.6.
When i tried to run this query:
"""
SELECT *
FROM tsp_astar_directed('view_viasnodo','38151,38151,35604,35586,20948,39935,35457,40636,40242,35485,19143,40079,40335,40058,19058',38147,12000,false,false);
"""

i get this message "ERROR: relation "tsp_test" does not exist at
character 328" which is because the function tsp_astar_directed() in
routing_tsp_wrappers.sql has an UNION ALL that takes values from that
table... i workaround that problem creating a dummy tsp_test table...

but then when i try the same select i get "segmentation fault", this
is the backtrace:

I posted this on 2011 but it seems i posted in the users list. I also
created issue # 27 (https://github.com/pgRouting/pgrouting/issues/27)
on github.
On that issue someone suggested to replace al ocurrences of "tsp_test"
with " ' || quote_ident(geom_table) || ' ", which i did (recently) but
now i get this other crash (which i reported in a comment on that same
issue).

"""
Core was generated by `postgres: postgres db [local] SELECT '.
Program terminated with signal 11, Segmentation fault.
#0 0x00007f301738965d in find_tsp_solution (num=, dist=,
p_ids=0x7fff89d10b40, source=,
fit=0x7fff89d10be8, err_msg=) at
/usr/src/debug/pgrouting-1.05/extra/tsp/src/tsp_solver.cpp:299
299 if(score < ga_get_entity_from_rank(pop,0)->fitness)
"""

as you can see this is failing at tsp_solver line 299 which is an "if
" statement and the only thing i can see as a possible problem is the
function ga_get_entity_from_rank() which comes from GAUL.

ideas?

--
Jaime Casanova www.2ndQuadrant.com
Professional PostgreSQL: Soporte 24x7 y capacitación
Phone: +593 4 5107566 Cell: +593 987171157
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

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

Stephen_Woodbridge1 · March 4, 2013, 8:36pm

On 3/4/2013 2:48 PM, Dave Potts wrote:

On 04/03/13 16:23, Stephen Woodbridge wrote:
Hi Steve,

Whats going to be included in pgrouting 2.0
What is in the wish list,
Which platforms will be supported ?

I'm working on putting together a plan. Once I have it in some order I will post a link to it.

Some of the ideas are:

* postgis 2.0
* postgresql 9.1+ or 9.2+ using extensions
* Windows and linux builds
* Reorganizing the source tree
* planning for unit tests and regression test
* unbundling some of the code to allow access intermediate results like tsp, driving_distance, dijkstra result graph
* pulling some of the branches into the code code base
* review pull requests and bugs
* reworking some of the wrapper functions to make them more consistent and interchangable

At the moment I have way more ideas and committed work than funding so we will see how far I can get.

I just started today on this and I'm trying to get my hands around to size and scope of the problem. I will release more information next week on this, once I have some semblance of a plan worked out.

I will also be setting my system up to create windows builds.

So lots of ideas ... reality has not set in yet!

-Steve

Dave.

Hi Jaime,

I'm not sure there is anyone that knows much about the original tsp
integration still on the list.

I am starting a project targeted to release a pgrouting 2.0. We have
wishlist items in this plan to replace Gaul and cgal libraries if we
have time to integrate a suitable replacement.

If you are able to dig into this and create a pull request, I will be
going through a lot of the open pull requests at some point in this
process, but if we replace gaul that will be moot for 2.0. That said I
expect there will be people that need the fix for the current releases.

-Steve W

On 3/4/2013 10:38 AM, Jaime Casanova wrote:

On Tue, Mar 22, 2011 at 3:09 PM, Jaime Casanova
<jaime@2ndquadrant.com> wrote:

Hi,

I installed pgrouting with tsp on a centos 5 machine with postgres
8.4.5 and postgis 1.3.6.
When i tried to run this query:
"""
SELECT *
FROM
tsp_astar_directed('view_viasnodo','38151,38151,35604,35586,20948,39935,35457,40636,40242,35485,19143,40079,40335,40058,19058',38147,12000,false,false);

"""

i get this message "ERROR: relation "tsp_test" does not exist at
character 328" which is because the function tsp_astar_directed() in
routing_tsp_wrappers.sql has an UNION ALL that takes values from that
table... i workaround that problem creating a dummy tsp_test table...

but then when i try the same select i get "segmentation fault", this
is the backtrace:

I posted this on 2011 but it seems i posted in the users list. I also
created issue # 27 (https://github.com/pgRouting/pgrouting/issues/27)
on github.
On that issue someone suggested to replace al ocurrences of "tsp_test"
with " ' || quote_ident(geom_table) || ' ", which i did (recently) but
now i get this other crash (which i reported in a comment on that same
issue).

"""
Core was generated by `postgres: postgres db [local] SELECT '.
Program terminated with signal 11, Segmentation fault.
#0 0x00007f301738965d in find_tsp_solution (num=, dist=,
p_ids=0x7fff89d10b40, source=,
fit=0x7fff89d10be8, err_msg=) at
/usr/src/debug/pgrouting-1.05/extra/tsp/src/tsp_solver.cpp:299
299 if(score < ga_get_entity_from_rank(pop,0)->fitness)
"""

as you can see this is failing at tsp_solver line 299 which is an "if
" statement and the only thing i can see as a possible problem is the
function ga_get_entity_from_rank() which comes from GAUL.

ideas?

--
Jaime Casanova www.2ndQuadrant.com
Professional PostgreSQL: Soporte 24x7 y capacitación
Phone: +593 4 5107566 Cell: +593 987171157
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

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

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

Jaime_Casanova · March 5, 2013, 7:01pm

On Mon, Mar 4, 2013 at 11:23 AM, Stephen Woodbridge
<woodbri@swoodbridge.com> wrote:

Hi Jaime,

I'm not sure there is anyone that knows much about the original tsp
integration still on the list.

I am starting a project targeted to release a pgrouting 2.0. We have
wishlist items in this plan to replace Gaul and cgal libraries if we have
time to integrate a suitable replacement.

If you are able to dig into this and create a pull request, I will be going
through a lot of the open pull requests at some point in this process, but
if we replace gaul that will be moot for 2.0. That said I expect there will
be people that need the fix for the current releases.

Hi,

the function in https://github.com/pgRouting/gaul-devel we got this
function (which is the one that crashes)
"""
GAULFUNC entity *ga_get_entity_from_rank(population *pop, const
unsigned int rank)
{
if ( !pop ) die("Null pointer to population structure passed.");

if ( rank > (unsigned) pop->size ) return NULL;

return pop->entity_iarray[rank];
}
"""

but the code in the file tsp_solver.cpp line 299 as i found it in
https://github.com/pgRouting/pgrouting (which is the one that fails),
calls that function with a rank == 0 so when pop->size == 0 it returns
pop->entity_iarray[rank]; which should be NULL. so it the end this is
basically NULL->fitness which causes the crash
"""
if(score < ga_get_entity_from_rank(pop,0)->fitness)
        {
          score = ga_get_entity_from_rank(pop,0)->fitness;
          *fit = score;

          for(int l=0; l<cnum; l++)
            {
              p_ids[l] = ids[
                             ((int *)ga_get_entity_from_rank(pop,0)->
                              chromosome[0])[l]];
            }
        }
"""

attached is a simple one-line fix which basically adds an if
(pop->size > 0) before calling ga_get_entity_from_rank(), if you think
that's fine i can make the pull request or you can commit directly

--
Jaime Casanova www.2ndQuadrant.com
Professional PostgreSQL: Soporte 24x7 y capacitación
Phone: +593 4 5107566 Cell: +593 987171157

tsp_solver_fix.patch (1.15 KB)