Flags set as environment variables are overridden in the build process, but should not.

The current methodology for defining turn restrictions basically limits you to one restriction per record using the rule column. If you want to add multiple restrictions for a given edge you have to duplication the edge for each additional restriction and then add a single restriction to each new edge. This also requires that you then order by gid to group the restrictions together when you fetch the edges.

A better methodology is needed for describing this restrictions. For example, rule could be:

rule 1 rule 2 rule N
-------------- -------------- ...

edge[,edge][;edge[,edge]]*

this would allow any of the following rows

4
14,4
4;12
14,4;12
etc

TSP SQL wrapper should check the number of points and their existance. Also TSP C wrapper should checl the number of points.

Currently pgRouting SQL functions are installed in

/usr/share/postlbs/

Change the installation directory to

/usr/share/pgrouting/

with a normal number it's fast 4860887 152ms
with a larger number it becomes slow 34860887 19435ms
with an even larger number it crashes the database 134860887 after 28 seconds it crashed the database

I could reproduce it both under linux/postgres9 and windows/postgres8.4
under windows the timings are different 300 ms ,1500 ms ,250 ms the first two gave a result and the third also caused the database to crash

The SQL of the network used for testing is below. For the first two tests the number 134860887 is changed

DROP TABLE IF EXISTS network;
CREATE TABLE network (id integer PRIMARY KEY, source integer, target integer, cost float);
INSERT INTO network(id,source,target,cost) VALUES
(134034453,4401484,4401467,1491.35562366006),
(134034463,4401489,4401485,12.1046145920234),
(134034458,4401487,4401477,177.374061187772),
(134095663,4401465,4401476,2014.71852797927),
(134034459,4401485,4401487,201.968135582698),
(134095834,4401478,4401465,293.089423713387),
(134034461,4401488,4401489,418.687894948968),
(629678698,4415069,134860887,3776.78929640359),
(134034456,4401477,4401481,491.242305990214),
(134095832,4401482,4401487,76.1157555542275),
(134034465,4401490,4401489,1956.98967514724),
(134034454,4401483,4401486,1356.25190452873),
(134034462,4401487,4401478,17.2205341642897),
(134095833,4401477,4401478,2014.66722340654),
(134034455,4401485,4401483,53.5613132396201),
(134034467,4401488,4417647,2597.20106449741),
(134034452,4401483,4401467,350.071683838508),
(134034446,4401481,4401476,568.270689073724),
(134072383,4416226,4401482,322.141177736713),
(134034447,4401482,4401481,1522.8331095897),
(134034466,4401486,4401490,610.880612548267),
(134034468,4417647,4401486,507.803184036552),
(134034464,4401490,4401485,149.914370088613);
DROP INDEX IF EXISTS idx_network_source;
DROP INDEX IF EXISTS idx_network_target;
CREATE INDEX idx_network_source ON network(source);
CREATE INDEX idx_network_target ON network(target);
SELECT * FROM shortest_path('SELECT id, source, target, cost FROM network', 4401489, 4401483, false, false)

Installation of PostgreSQL 9.1 with PostGis 1.5 works like a charm.
No errors - no compile errors!

In this tutorial
http://www.pgrouting.org/docs/1.x/install_ubuntu.html
The error happens in the last 2 console lines!

As soon I start to build my Database I get an error:
psql:routing_dd.sql:28: ERROR: could not load library "/usr/lib/postgresql/9.1/lib/librouting_dd.so": /usr/lib/postgresql/9.1/lib/librouting_dd.so: undefined symbol: __gmpq_equal

Fact is, I already checkt with recent patches and bugs and found this one.
27e5ccd

But my version had already the patch included!

Thanks!
Martin

As far as I can see, is_same.hpp no longer resides in boost/graph/detail. core/src/edge_visitors.hpp still uses it.

http://www.boost.org/doc/libs/1_50_0/libs/type_traits/doc/html/boost_typetraits/reference/is_same.html

Hello,

I'm trying to work with pg routing on postgis 2.0 and postgres 9.1.3, in windows 7 64 bits.
I'm loaded the binaries from here:

https://github.com/sanak/pgrouting/downloads

The pgrouting was succed installed but when i run the assign_vertex function i get this error:

ERROR: find_srid() - couldnt find the corresponding SRID - is the geometry registered in the GEOMETRY_COLUMNS table? Is there an uppercase/lowercase missmatch?
CONTEXT: PL/pgSQL function "assign_vertex_id" line 17 at assignment

Anybody can help to fix that?If someone have an idea i can try....

My basic problem is that after installing Postgresql 9.1 with postgis (up and running) i try to install pgrouting 1.05.

I have installed all libs required.
After enetering final command:
"cmake -DWITH_TSP=ON -DWITH_DD=ON" I'm getting an error:

@ubuntu:~/pgrouting-1.05$ cmake -DWITH_TSP=ON
/-- The CXX compiler identification is unknown
CMake Error: your CXX compiler: "CMAKE_CXX_COMPILER-NOTFOUND" was not found. Please set CMAKE_CXX_COMPILER to a valid compiler path or name.
CMake Warning (dev) at CMakeLists.txt:12 (add_subdirectory):
The source directory

/home/gajos/pgrouting-1.05/cmake

does not contain a CMakeLists.txt file.

CMake does not support this case but it used to work accidentally and is
being allowed for compatibility.

Policy CMP0014 is not set: Input directories must have CMakeLists.txt. Run
"cmake --help-policy CMP0014" for policy details. Use the cmake_policy
command to set the policy and suppress this warning.
This warning is for project developers. Use -Wno-dev to suppress it.

-- PostgreSQL not found.
FATALERROR Please check your PostgreSQL installation.
Boost headers were found here: /usr/include
Output directory for libraries is set to /usr/lib/postgresql/9.1/lib
Installation directory for libraries is set to /usr/lib/postgresql/9.1/lib and for SQL files is set to /usr/share/postlbs
Installation directory for libraries is set to /usr/lib/postgresql/9.1/lib
CMake Error: The following variables are used in this project, but they are set to NOTFOUND.
Please set them or make sure they are set and tested correctly in the CMake files:
POSTGRESQL_INCLUDE_DIR (ADVANCED)
used as include directory in directory /home/gajos/pgrouting-1.05
used as include directory in directory /home/gajos/pgrouting-1.05/core
used as include directory in directory /home/gajos/pgrouting-1.05/extra/tsp
used as include directory in directory /home/gajos/pgrouting-1.05/extra/tsp/src
used as include directory in directory /home/gajos/pgrouting-1.05/extra/tsp/sql
used as include directory in directory /home/gajos/pgrouting-1.05/extra/driving_distance
used as include directory in directory /home/gajos/pgrouting-1.05/extra/driving_distance/src
used as include directory in directory /home/gajos/pgrouting-1.05/extra/driving_distance/sql
used as include directory in directory /home/gajos/pgrouting-1.05/core/src
used as include directory in directory /home/gajos/pgrouting-1.05/core/sql

-- Configuring incomplete, errors occurred!

Postgres is running and directory contains CMakeLists.txt:

/CMAKE_MINIMUM_REQUIRED(VERSION 2.3)
PROJECT(PGROUTING)

-----------------------------------------------------------------------------

PGROUTING version number.

SET(PGROUTING_VERSION_MAJOR "1")
SET(PGROUTING_VERSION_MINOR "0")
SET(PGROUTING_VERSION_PATCH "5")

SET(PGROUTING_VERSION_STRING "${PGROUTING_VERSION_MAJOR}.${PGROUTING_VERSION_MINOR}.${PGROUTING_VERSION_PATCH}")

add_subdirectory(cmake)
SET(CMAKE_MODULE_PATH "${CMAKE_SOURCE_DIR}/cmake")

include (MacroLibrary)

macro_optional_find_package(PostgreSQL)
IF(NOT POSTGRESQL_FOUND)
MESSAGE(FATAL ERROR " Please check your PostgreSQL installation.")
ENDIF(NOT POSTGRESQL_FOUND)

FIND_PACKAGE(Boost)
IF(Boost_INCLUDE_DIRS)
MESSAGE("Boost headers were found here: ${Boost_INCLUDE_DIR}")
ELSE(Boost_INCLUDE_DIRS)
MESSAGE(FATAL ERROR " Please check your Boost installation ")
ENDIF(Boost_INCLUDE_DIRS)

EXEC_PROGRAM(pg_config
ARGS --pkglibdir
OUTPUT_VARIABLE LIB_DIR)

IF(LIB_DIR)
MESSAGE("Output directory for libraries is set to ${LIB_DIR}")
ELSE(LIB_DIR)
SET(LIB_DIR ${PGROUTING_BINARY_DIR}/lib)
MESSAGE("pg_config not found, output directory for libraries is set to ${PGROUTING_BINARY_DIR}/lib")
ENDIF(LIB_DIR)

if(PGROUTING_CORE_INCLUDE_DIR)
set(PGROUTING_CORE_FOUND TRUE)

else(PGROUTING_CORE_INCLUDE_DIR)
FIND_PATH(PGROUTING_CORE_INCLUDE_DIR dijkstra.h
PATHS
${CMAKE_CURRENT_SOURCE_DIR}/core/src
)

if(PGROUTING_CORE_INCLUDE_DIR)
set(PGROUTING_CORE_FOUND TRUE)
message(STATUS "Found PGROUTING_CORE core: ${PGROUTING_CORE_INCLUDE_DIR}")
INCLUDE_DIRECTORIES(${PGROUTING_CORE_INCLUDE_DIR})
else(PGROUTING_CORE_INCLUDE_DIR)
set(PGROUTING_CORE_FOUND FALSE)
message(STATUS "PGROUTING_CORE core not found.")
endif(PGROUTING_CORE_INCLUDE_DIR)

mark_as_advanced(PGROUTING_CORE_INCLUDE_DIR)

endif(PGROUTING_CORE_INCLUDE_DIR)

OPTION(WITH_TSP "Build TSP library" OFF)
OPTION(WITH_DD "Build Driving distance library" OFF)

IF(UNIX)
SET(LIBRARY_INSTALL_PATH ${LIB_DIR})
SET(SQL_INSTALL_PATH /usr/share/postlbs)
MESSAGE("Installation directory for libraries is set to ${LIBRARY_INSTALL_PATH} and for SQL files is set to ${SQL_INSTALL_PATH}")
ELSE(UNIX)
SET(LIBRARY_INSTALL_PATH ${PGROUTING_BINARY_DIR}/lib)
SET(SQL_INSTALL_PATH ${PGROUTING_BINARY_DIR}/lib)
ENDIF(UNIX)

SET(PGROUTING_INCLUDE_DIRECTORIES ${PGROUTING_SOURCE_DIR}/core ${PGROUTING_SOURCE_DIR}/core/src ${PGROUTING_SOURCE_DIR}/extra ${PGROUTING_SOURCE_DIR}/extra/tsp ${PGROUTING_SOURCE_DIR}/extra/tsp/src ${PGROUTING_SOURCE_DIR}/extra/driving_distance ${PGROUTING_SOURCE_DIR}/extra/driving_distance/src
)

INCLUDE_DIRECTORIES(. ${PGROUTING_INCLUDE_DIRECTORIES} ${POSTGRESQL_INCLUDE_DIR} ${Boost_INCLUDE_DIRS})
IF(WIN32)
INCLUDE_DIRECTORIES(${INCLUDE_DIRECTORIES} ${POSTGRESQL_INCLUDE_DIR}/port/win32)
ENDIF(WIN32)

we need link libpostgres.a on win32 env

IF(WIN32)
LINK_DIRECTORIES(${LIB_DIR})
LINK_LIBRARIES(postgres)
ENDIF(WIN32)

SET(CMAKE_C_FLAGS "-O2 -g -frounding-math")
SET(CMAKE_CXX_FLAGS "-O2 -g -frounding-math")

Recurse into the subdirectories. This does not actually

cause another cmake executable to run. The same process will walk through

the project's entire directory structure.

SUBDIRS(core)

IF(WITH_TSP)
macro_optional_find_package(GAUL)
IF(NOT GAUL_FOUND)
message(FATAL ERROR " Please check your gaul installation, or set correct path to GAUL_INCLUDE_DIR and GAUL_LIBRARIES.")
ENDIF(NOT GAUL_FOUND)
INCLUDE_DIRECTORIES(${INCLUDE_DIRECTORIES} ${GAUL_INCLUDE_DIR})
ADD_SUBDIRECTORY(extra/tsp)
ENDIF(WITH_TSP)

IF(WITH_DD)
macro_optional_find_package(CGAL)
IF(NOT CGAL_FOUND)
message(FATAL ERROR " Please check your CGAL installation, or set correct path to CGAL_INCLUDE_DIR and CGAL_LIBRARIES.")
ENDIF(NOT CGAL_FOUND)
INCLUDE_DIRECTORIES(${INCLUDE_DIRECTORIES} ${CGAL_INCLUDE_DIR})
ADD_SUBDIRECTORY(extra/driving_distance)
ENDIF(WITH_DD)/

I encountered a bug with the Shortest Path Shooting Star algorithm during the FOSS4G tutorial sessions when using pgRouting with OSM data and GeoExt.

After loading the sample dataset for the routing tutorial, I created costs for the ways in my database with the following SQL:

update ways set class_id=199 where class_id=100;
update ways set to_cost = (199-class_id)*10;

I attempted to add rules to prefer more major roads (those with class_id of low 100's) over more minor roads (those with class_id of the high 100's). I found that I had to make the 'to_cost' attribute of each way much higher for the major roads to make the routing prefer the major roads. That is counter-intuitive to me -- wouldn't a higher cost introduce more penalty, and thus avoid the ways with higher costs?

With the weights set, and using the Denver.osm sample data, when I route from "-105.01770817195222 39.74944518305231" (~ exit 211 on I-25)[gid=13402] to "-105.01491867458083 39.72865495921035" (~ exit 209B on I-25)[gid=13564] using "SPS" method, the route seems to jump off the highway (a preferred way), onto residential streets, then back onto the highway. Both "SPA" and "SPD" follow the highway as expected. I can confirm that it is not a problem of routing the Northbound direction onto the Southbound direction.

Is this a problem with the way of calculating the "to_cost"?

Check geometry type for "LINESTRING"/"MULTILINESTRING" as ST_startpoint might not work anymore with PostGIS 2.0:

Changed: 2.0.0 no longer works with single geometry multilinestrings. In older versions of PostGIS -- a single line multilinestring would work happily with this function and return the start point. In 2.0.0 it just returns NULL like any other multilinestring. The older behavior was an undocumented feature, but people who assumed they had their data stored as LINESTRING may experience these returning NULL in 2.0 now.

Rectangle bounding boxes take a lot of additional network links into account. An ellipse shaped bounding box should be more efficient.

As told here http://pgrouting.postlbs.org/discussion/topic/308#message1160 shortest_path_shooting_star algorithm doesn't respect one-way restriction of the first and last edge:

look at this image: http://img132.imageshack.us/img132/8185/error2ia.jpg

edge_id|vertex_id|cost|street 4311;790;1001000138.79372;790;"RE G. (VIA)" 4150;501;61.479488767088;501;"PACCHIOTTI G. (VIA)" 6114;856;1001000142.27532;856;"LIONETTO (STR. DEL)"

Query is

SELECT ".TABLE.".*, AsText??(".TABLE.".the_geom) AS wkt FROM ".TABLE.", shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost,

x1, y1, x2, y2, rule, to_cost FROM ".TABLE."', ".$startEdgegid?.", ".$endEdgegid?.", true, true) as rt

WHERE ".TABLE.".gid=rt.edge_id;

Similar to PostGIS a couple of functions for version information should be useful, ie.

pgr=#\df postgis_
postgis_full_version postgis_gist_sel postgis_lib_version
postgis_scripts_installed postgis_version postgis_geos_version
postgis_jts_version postgis_proj_version postgis_scripts_released
postgis_gist_joinsel postgis_lib_build_date postgis_scripts_build_date
postgis_uses_stats

The current implementation of Astar core function accepts a table generating SQL statement as first parameter and the table has four columns x1, y1, x2, y2. Then the heuristic is computed as (|x1 - x2| + |y1 - y2|) / 2. Tying down the heuristic reduces reusability of the Astar function.

The solution can be to pass the string containing a call to some psql function(Eg: ST_Distance) that can be evaluated inside the operator definition of AStarHeuristic's subclass. This means that astar_boost_wrapper.c will contain some SPI code.

Example call of Proposed Astar core function:

SELECT * FROM shortest_path_astar('
                SELECT gid as id,
                         source::integer,
                         target::integer,
                         length::double precision as cost,
                        FROM ways',
                605, 359, false, false,
                'SELECT ST_Distance(src.the_point, tgt.the_point) 
                        FROM nodes src, nodes tgt
                        WHERE src.id = ?0 AND tgt.id = ?1'
);

As reported by this user there seems to be a memory allocation problem in DD.
http://lists.osgeo.org/pipermail/pgrouting-users/2011-August/000771.html

I installed pgrouting 1.05 with tsp on a centos 5.5 machine with postgres 8.4.7 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 (that obviously doesn't really exist)... i workaround that problem creating a dummy tsp_test table...

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; ilen_chromosomes; i++)
  {
    data[i] = i;
  }

  for (i=0; ilen_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;
}

Good Morning :)

I want to try use euclidean distance heuristic in A* in pgrouting, may u give me tutorial how to change the heuristic and recompile it? :)

If I do not include the start node in the list of stops in TSP function, I'll get an error:
"The connection to the server was lost. Attempting reset: Failed."

For example:

SELECT * FROM tsp_dijkstra('ways','552,169,784,1567,314',272);

I get this error:
$ psql -U postgres -f /usr/share/pgrouting/routing_dd.sql routing
psql:/usr/share/pgrouting/routing_dd.sql:28: ERROR: could not load library "/usr/lib/postgresql/9.1/lib/librouting_dd.so": /usr/lib/postgresql/9.1/lib/librouting_dd.so: undefined symbol: __gmpq_equal

I have installed as follow:
sudo apt-get install postgresql, postgis, postgresql-contrib, postgresql-server-dev-all, cmake, libcgal-dev

wget http://downloads.sourceforge.net/gaul/gaul-devel-0.1849-0.tar.gz
tar -xzf gaul-devel-0.1849-0.tar.gz
cd gaul-devel-0.1849-0/
./configure --disable-slang
make
sudo make install
sudo ldconfig

git clone git://github.com/pgRouting/pgrouting.git pgrouting
cd pgrouting/
cmake -DWITH_TSP=ON -DWITH_DD=ON .
make
sudo make install

Everything compiled without errors.
The packages on 12.04 are postgresql 9.1.3 , libcgal 3.9

BTW, some path have changed, the new paths are:
psql -U postgres -f /usr/share/postgresql/9.1/contrib/postgis-1.5/postgis.sql routing
psql -U postgres -f /usr/share/postgresql/9.1/contrib/postgis-1.5/spatial_ref_sys.sql routing
psql -U postgres -f /usr/share/pgrouting/routing_core.sql routing
psql -U postgres -f /usr/share/pgrouting/routing_core_wrappers.sql routing
psql -U postgres -f /usr/share/pgrouting/routing_topology.sql routing

you may consider change the documentation here http://www.pgrouting.org/docs/1.x/install_ubuntu.html

hi friends my english language is poor.i want to use assign_vertex_id() with SCHEMA name. for example i need use: select assign_vertex_id('baharestan.roads', 0.001, 'the_geom', 'gid'); but it has this error:

NOTICE: CREATE TABLE will create implicit sequence "vertices_tmp_id_seq" for serial column "vertices_tmp.id" CONTEXT: SQL statement "CREATE TABLE vertices_tmp (id serial)" PL/pgSQL function "assign_vertex_id" line 21 at EXECUTE statement ERROR: relation "baharestan.roads" does not exist CONTEXT: SQL statement "SELECT count(*) as countids FROM "baharestan.roads"" PL/pgSQL function "assign_vertex_id" line 28 at FOR over EXECUTE statement

thanks a lot

TSP function should return a set of rows assuming that the source_id for the start is also the end (in order to create a loop).

I get a cmake error with CONFIGURE_FILE - for all the *.sql install commands. I think it's because SQL_INSTALL_PATH is not getting set correctly, thus its sanity check that the destination exists fails.

It looks like the problem is:

IF(UNIX)
SET(LIBRARY_OUTPUT_PATH ${LIB_DIR})
SET(SQL_INSTALL_PATH /usr/share/postlbs)
ELSE(UNIX)
SET(LIBRARY_OUTPUT_PATH ${PGROUTING_BINARY_DIR}/lib)
SET(SQL_INSTALL_PATH ${PGROUTING_BINARY_DIR}/lib)
ENDIF(UNIX)

OSX appears to fall under the "UNIX" category (makes sense), and so it hardwires the SQL_INSTALL_PATH instead of using the configured PGROUTING_BINARY_DIR. /usr/share/postlbs does not exist on my system, and I don't want it to, I want the sql in the configured Postgres dir. If I comment out the UNIX block, leaving the set commands in the second block (else), cmake succeeds in configuring the build.

Please update the FSF's postal address in COPYING and various other files. See http://www.gnu.org/licenses/old-licenses/gpl-2.0.txt

Hi:
I could not find any code for bidirectional astar search on the web hence wrote http://sourceforge.net/projects/tway/,
I feel users with network of 100k+ nodes may benefit from it. I tested it on the dimacs data-sets.

I have uploaded a patch for pgrouting 1.05 there, I have not been able to compile/test the patch though. It will be great if someone tries it out.

Regards,
SRC

PS: someday I will learn to use git and upload a fork there ..

Similar to "ST_" namespace it might be a good idea to add some pgRouting namespace as well, for example "PGR_":

• Makes functions easy to identify that came with pgRouting
• Allows to modify functions and store them with the same name but different namespace
• Can be easily replaced with "ST_" when merging with PostGIS

How about implementing k-shortest path algorithm?

I searched about the problem a bit and found this website: http://code.google.com/p/k-shortest-paths/

It uses Boost and C++ and it's GPLv2.

Hi,

I think I may have found a bug on the Shooting Star algorithm. At some point, it skips one edge/vertex and gets directly to the next one, creating a "new" edge.

The data I am working with:
INSERT INTO routing (id, source, target, cost, reverse_cost, x1, x2, y1, y2, rule, to_cost, the_geom) VALUES (1, 1, 2, 8, 8, 1, 3, 1, 1, '', 0, NULL);
INSERT INTO routing (id, source, target, cost, reverse_cost, x1, x2, y1, y2, rule, to_cost, the_geom) VALUES (2, 2, 4, 1000, 6, 3, 3, 1, 3, '', 0, NULL);
INSERT INTO routing (id, source, target, cost, reverse_cost, x1, x2, y1, y2, rule, to_cost, the_geom) VALUES (3, 2, 5, 4, 4, 3, 5, 1, 2, '', 0, NULL);
INSERT INTO routing (id, source, target, cost, reverse_cost, x1, x2, y1, y2, rule, to_cost, the_geom) VALUES (4, 6, 5, 3, 3, 5, 5, 4, 2, '', 0, NULL);
INSERT INTO routing (id, source, target, cost, reverse_cost, x1, x2, y1, y2, rule, to_cost, the_geom) VALUES (5, 4, 6, 10, 1000, 3, 5, 3, 4, '', 0, NULL);
INSERT INTO routing (id, source, target, cost, reverse_cost, x1, x2, y1, y2, rule, to_cost, the_geom) VALUES (6, 7, 6, 1000, 3, 4, 5, 4, 4, '', 0, NULL);
INSERT INTO routing (id, source, target, cost, reverse_cost, x1, x2, y1, y2, rule, to_cost, the_geom) VALUES (7, 7, 4, 4, 1000, 4, 3, 4, 3, '', 0, NULL);
INSERT INTO routing (id, source, target, cost, reverse_cost, x1, x2, y1, y2, rule, to_cost, the_geom) VALUES (8, 3, 4, 1000, 8, 1, 3, 3, 3, '', 0, NULL);

The SQL I am using is:

SELECT * from shortest_path_shooting_star(
'select id as id,
source::integer,
target::integer,
x1 ::double precision,
y1 ::double precision,
x2 ::double precision,
y2 ::double precision,
rule,
cost ::double precision,
to_cost ::double precision,
reverse_cost ::double precision
from routing',
1,
8,
true,
true);

And the result it shows is:
vertex_id;edge_id;cost
1;1;8
2;3;4
6;4;3
7;5;10
4;8;1000

The result should have been something like:
1;1;8
2;3;4
5;4;3
6;6;3
7;7;4
4;8;8

I am using the Ubuntu version from the repositories:
SELECT version(); says "PostgreSQL 8.4.7 on x86_64-pc-linux-gnu, compiled by GCC gcc-4.4.real (Ubuntu 4.4.3-4ubuntu5) 4.4.3, 64-bit"
SELECT postgis_full_version(); says "POSTGIS="1.4.0" GEOS="3.1.0-CAPI-1.5.0" PROJ="Rel. 4.7.1, 23 September 2009" USE_STATS"

The pgrouting installed is the one from the subversion:
$ svn info
Ruta: .
URL: http://pgrouting.postlbs.org/svn/pgrouting/trunk
Raíz del repositorio: http://pgrouting.postlbs.org/svn/pgrouting
UUID del repositorio: d21bcd6f-0036-404f-87c1-d983b28855fd
Revisión: 358
Tipo de nodo: directorio
Agendado: normal
Autor del último cambio: daniel
Revisión del último cambio: 358
Fecha de último cambio: 2010-09-18 10:11:40 +0200 (sáb 18 de sep de 2010)

There is a memory leak in the function shortest_path, because the variable path which is allocated using malloc (not palloc) in boost_wrapper is never freed.

create automated tests to ensure all functions work properly when (or before) compiling the binaries

If the network contains two (or more) edges between the same nodes shortest_path returns everytime the first one without cost accounting.

  ________10________ 
[1]                 [2]
 |                   |
 |________20_________| 

Here is the test case with wrong result.

SELECT * FROM shortest_path('
  SELECT unnest(array[1,2]) as id, 
    unnest(array[10,10]) as source,
    unnest(array[20,20]) as target,
    unnest(array[2,1])::float8 as cost
  ',10,20,false,false);

Workaround is in using "ORDER BY cost" but it is not a good solution.

software version: rev355 + shootingstar_sp_smart() sql function
testing platform: mac os leopard + xcode

symptom: by moving starting and end points around their respective edge (ie the generated fake point/segments remain on the same edge), changes the calculated path from time to time in a unlogical manner (reproductible case), sometimes produces no result at all.

diagnostic: with "no result" case data, the crash occurs in file: shootingstar_search.hpp function:

void gray_target(Edge e, Edge pe, Graph& g, int e_max_id)
at line 354:

m_Q.update(e);
...more specifically in mutable_queue.hpp at line 106:

c[current_pos] = x;
...resulting into an out-of-bounds error msg (* sorry, don't have memorized the exact message *). It occured when an edge_descriptor (u;v) was updated while its sibling (v;u) was already poped out of the queue. Debugging further revealed that both original and reverted edge_descriptors were assigned the same index in the index_array in mutable_queue.hpp

void push(const IndexedType& x) {
c.push_back(x);
/set index-array/
index_array[ get(id, x) ] = c.size()-1;

function. (This 'index' value is also referred by graph[e].index).

solution: give a unique index value to each added edge to the graph by replacing, at lines 237 and 275 in file shooting_star_boost_wrapper.cpp, variable j by an incremental counter:

graph_add_edge<graph_t, edge_descriptor>(graph,
/j/edge_index++, //lapinos03 patch
edges_array[j].id, edges_array[j].source,
edges_array[j].target, edges_array[j].cost,
edges_array[j].s_x, edges_array[j].s_y,
edges_array[j].t_x, edges_array[j].t_y,
adjacent_edges);
final word: well, took me 2 days of intense head-ache but looks to work fine and stable now ;-)

As the subject says. Included from core/src/edge_visitors.hpp. Though it doesn't seem to actually need it - I commented out the is_same.hpp include and core compiles without error.

The point_to_id function has the schema element hard-coded, which makes it unusable without re-writing and replacing the function where public is not the default schema for gis tables.

ie, I had to replace the function with :

BEGIN

_srid := Find_SRID('gis','vertices_tmp','the_geom');

SELECT

Might be useful to have an option / alternative where the assign_vertex_id function looks up the schema of the current table at the same time as it checks the srid, and passes that to the point_to_id function as the appropriate schema.

Get the troubles user have in this question:
http://gis.stackexchange.com/questions/13542/newbie-postgis-geometry-and-multilinestring-clarification

From the mailing list:

/opt/src/pgrouting-1.05# cmake -DBoost_INCLUDE_DIR=/opt/src/boost_1_45_0 -DWITH_DD=ON -DCGAL_INCLUDE_DIR=/opt/emap -DCGAL_LIBRARIES=/opt/emap -DPOSTGRESQL_INCLUDE_DIR=/opt/emap -DPOSTGRESQL_LIBRARIES=/opt/emap -DSQL_INSTALL_PATH=/opt/emap  .
-- The C compiler identification is GNU
-- The CXX compiler identification is GNU
-- Check for working C compiler: /usr/bin/gcc
-- Check for working C compiler: /usr/bin/gcc -- works
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working CXX compiler: /usr/bin/c++
-- Check for working CXX compiler: /usr/bin/c++ -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
Boost headers were found here: /opt/src/boost_1_45_0
Output directory for libraries is set to /opt/emap/lib/postgresql
-- Found PGROUTING_CORE core: /opt/src/pgrouting-1.05/core/src
Installation directory for libraries is set to /opt/emap/lib/postgresql and for SQL files is set to /usr/share/postlbs
-- Configuring done
WARNING: Target "routing_dd" requests linking to directory "/opt/emap".  Targets may link only to libraries.  CMake is dropping the item.
-- Generating done
-- Build files have been written to: /opt/src/pgrouting-1.05

IF (NOT SQL_INSTALL_PATH)
SET(SQL_INSTALL_PATH /usr/share/pgrouting)
ENDIF(NOT SQL_INSTALL_PATH)

And then when you run want to override it you do something like:

SQL_INSTALL_PATH=/opt/emap/pgrouting cmake

or maybe

SQL_INSTALL_PATH=/opt/emap/pgrouting

Postgres modules on OSX should be loadable modules, or bundles, not dynamic libraries. There is a difference on OSX. -bundle is the flag used instead of -dynamiclib, and bundles don't need the install_name or version flags. pgxs also adds -multiply_defined suppress. The standard file extension for a bundle on OSX is the same as a library on linux - .so - but version numbers (if used) are still put before the suffix.

So, the basic link command for OSX would be:

c++ -bundle -multiply_defined suppress -o librouting.so
(plus the object files and extra configured flags)

There is a need to change in TSP wrappers table name from "tsp_test" to " ' || quote_ident(geom_table) || ' ".

I'm having issues with Dsp on a fairly large graph.
If I run several rounds of dsp with different sources and targets in the same session, the postgresql process memory keeps growing, until the OOM killer gets rid of it.
If I just close the session everytime, memory stays at a reasonable level.
I tried looking at the source code, but maybe I need some guidance in where to look at.
I can provide some sort of dataset, if it helps.

TIA

It seems that at least assign_vertex_id function doesn't work in other schema than "public", see http://lists.osgeo.org/pipermail/pgrouting-users/2011-January/000572.html

According to the documentation :

• cost: double precision value of the edge traversal cost. (a negative cost
  will prevent the edge from being inserted in the graph).

Yet when I have a negative cost (-1) to forbid using an edge it seems to crash (I don't know what really happens :

testdb=# SELECT * FROM shortest_path('SELECT edge_id AS id, source_id::int4 as source, target_id::int4 as target, cost::double precision AS cost FROM streets_topology',18342, 49625, false, false);
server closed the connection unexpectedly

This probably means the server terminated abnormally
before or while processing the request.

The connection to the server was lost. Attempting reset: Failed.
If I set the cost to a high value, or 'Infinity' it works correctly.

I suppose that the algorithm considers that the edge exists and has a negative cost (which is a problem with Dijkstra).

It returns the following error:

cd /tmp/buildd/pgrouting-1.05/obj-x86_64-linux-gnu/core/src && /usr/lib/ccache/g++   -Drouting_EXPORTS -O2 -g -frounding-math -fPIC -I/usr/include/postgresql/8.4/server -I/tmp/buildd/pgrouting-1.05/core/src -I/tmp/buildd/pgrouting-1.05/. -I/tmp/buildd/pgrouting-1.05/core -I/tmp/buildd/pgrouting-1.05/extra -I/tmp/buildd/pgrouting-1.05/extra/tsp -I/tmp/buildd/pgrouting-1.05/extra/tsp/src -I/tmp/buildd/pgrouting-1.05/extra/driving_distance -I/tmp/buildd/pgrouting-1.05/extra/driving_distance/src   -o CMakeFiles/routing.dir/shooting_star_boost_wrapper.o -c /tmp/buildd/pgrouting-1.05/core/src/shooting_star_boost_wrapper.cpp
In file included from /usr/include/c++/4.4/backward/hash_set:60,
                 from /usr/include/boost/pending/container_traits.hpp:23,
                 from /usr/include/boost/graph/detail/adjacency_list.hpp:31,
                 from /usr/include/boost/graph/adjacency_list.hpp:324,
                 from /tmp/buildd/pgrouting-1.05/core/src/shooting_star_boost_wrapper.cpp:25:
/usr/include/c++/4.4/backward/backward_warning.h:28: warning: #warning This file includes at least one deprecated or antiquated header which may be removed without further notice at a future date. Please use a non-deprecated interface with equivalent functionality instead. For a listing of replacement headers and interfaces, consult the file backward_warning.h. To disable this warning use -Wno-deprecated.
/tmp/buildd/pgrouting-1.05/core/src/shooting_star_boost_wrapper.cpp:26: fatal error: boost/vector_property_map.hpp: No such file or directory
compilation terminated.
make[3]: *** [core/src/CMakeFiles/routing.dir/shooting_star_boost_wrapper.o] Error 1
make[3]: Leaving directory `/tmp/buildd/pgrouting-1.05/obj-x86_64-linux-gnu'
make[2]: *** [core/src/CMakeFiles/routing.dir/all] Error 2
make[2]: Leaving directory `/tmp/buildd/pgrouting-1.05/obj-x86_64-linux-gnu'
make[1]: *** [all] Error 2
make[1]: Leaving directory `/tmp/buildd/pgrouting-1.05/obj-x86_64-linux-gnu'
make: *** [debian/stamp-makefile-build] Error 2
dpkg-buildpackage: error: debian/rules build gave error exit status 2
E: Failed autobuilding of package

Hi!

My colleague try to build pgRouting under Windows and have some problems: http://lists.osgeo.org/pipermail/pgrouting-dev/2011-October/000422.html Please give any hints about this.

Current implementation of TSP calculates the path prom start point to an end point which is one of points to visit. For VRP we need TSP version which will return back to the start point.

1. Driving Distance calculation page (http://www.pgrouting.org/docs/1.x/dd.html) tells that output field "cost" is
   "the cost associated to the current edge. It is 0 for the row after the last edge. Thus, the path total cost can be computated using a sum of all rows in the cost column." But it seems to me that cost attribute contains the total cost of travel from the starting node to the vertex_id node, isn't it?

2. Also in this document tells that "vertex_id: the identifier of source vertex of each edge". But when I perform the following query in my database:

   SELECT _.*, gid, osm_id, source, target FROM driving_distance('SELECT gid AS id, source AS source, target AS target, length AS cost FROM network_part', 4260, 2000, false, false) AS _ INNER JOIN network_part ON _.edge_id = network_part.gid WHERE OSM_ID=84675642

   it returns:
   vertex_id | edge_id | cost | gid | osm_id | source | target
   -----------+---------+------------------+--------+----------+--------+--------
   3520 | 539658 | 881.303092499435 | 539658 | 84675642 | 3520 | 3521
   3521 | 539658 | 911.340955617547 | 539658 | 84675642 | 3520 | 3521
   (2 rows)

   As you can see vertex_id is not the same as source of edge.

3. What is edge_id? Here is part of my road network: http://gis-lab.info/share/DR/ifort/dd_graph2.png
   If I perform query described above I get edge_id value the same for both vertex_id=3520 and 3521. I had assumed that vertex_id describes id of last edge but it is not correct. Please provide any information about edge_id field and how it can be used.

test

I have got a cast issue in dijkstra_sp_delta_directed function :

2012-06-19 18:14:34 CEST STATEMENT:  SELECT gid, the_geom FROM dijkstra_sp_delta( 'routes', $1, $2, $3 )
2012-06-19 18:14:39 CEST ERROR:  type of parameter 33 (numeric) does not match that when preparing the plan (integer)
2012-06-19 18:14:39 CEST CONTEXT:  PL/pgSQL function "dijkstra_sp_delta_directed" line 83 at assignment
    PL/pgSQL function "dijkstra_sp_delta" line 19 at FOR over EXECUTE statement

This error occurs when a number with no decimal is used in the function line 83 :

FOR rec IN EXECUTE 'SELECT CASE WHEN '||source_x||'<'||target_x||
       ' THEN '||source_x||' ELSE '||target_x||
       ' END as ll_x, CASE WHEN '||source_x||'>'||target_x||
       ' THEN '||source_x||' ELSE '||target_x||' END as ur_x'
    LOOP
END LOOP;

I think that source_x or target_x is considered as integer instead of numeric when values are concatenated.
Same error occurs line 92.

Versions :
"PostgreSQL 9.1.4 on i686-pc-linux-gnu, compiled by gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3, 32-bit"
Postgis "1.5 USE_GEOS=1 USE_PROJ=1 USE_STATS=1"
PgRouting 1.0.5

I resolve the problem with this modification in dijkstra_sp_delta_directed function :

   # Cast in Float to prevent plan error in PostgreSQL
FOR rec IN EXECUTE 'SELECT CASE WHEN CAST('||source_x||' as float8)< CAST('||target_x||
       ' as float8) THEN CAST('||source_x||' as float8) ELSE CAST('||target_x||
       ' as float8) END as ll_x, CASE WHEN CAST('||source_x||' as float8)>CAST('||target_x||
       '  as float8) THEN CAST('||source_x||' as float8) ELSE CAST('||target_x||' as float8) END as ur_x'
    LOOP
END LOOP;

ll_x := rec.ll_x;
ur_x := rec.ur_x;

    # Cast in Float to prevent plan error in PostgreSQL
FOR rec IN EXECUTE 'SELECT CASE WHEN CAST('||source_y||' as float8)<CAST('||
        target_y||' as float8) THEN CAST('||source_y||' as float8) ELSE CAST('||
        target_y||' as float8) END as ll_y, CASE WHEN CAST('||
        source_y||' as float8)>CAST('||target_y||' as float8) THEN CAST('||
        source_y||' as float8) ELSE CAST('||target_y||' as float8) END as ur_y'
    LOOP
END LOOP;

Hi,
the function assign_vertex_id should ignore NULL geometries to avoid errors:

FOR _r IN EXECUTE 'SELECT ' || quote_ident(gid_cname) || ' AS id,'
    || ' StartPoint('|| quote_ident(geo_cname) ||') AS source,'
        || ' EndPoint('|| quote_ident(geo_cname) ||') as target'
    || ' FROM ' || geom_table || ' WHERE ' || quote_ident(geo_cname) || ' IS NOT NULL '
LOOP

Best regards,
Daniel

the distance argument is the max cost cut-off from the Dijkstra's search, but it is also being used to create the BBOX() for selecting which edges to construct the graph with. This is wrong! Cost is not related to or in the same units as the vertex coordinates.

The simplest fix for this would be to pass two arguments to the driving distance function:

distance === maximum cost cut-off for the search buffer === maximum spatial units to expand the source x,y by.

Samuel Schembri reports on 2012-01-16:

I used pgrouting 1.02 on postgres 8.2.17. At this time, I can't update Postgresql.

There is a different comportment between 'shortest_path_astar' and 'driving_distance' functions when I use reverse_cost column.

Here are graphe conditions :

For each edge without one-way : cost=reverse_cost=length
For each edge with one-way similar to digitalisation way : cost=length reverse_cost=-1 (or 100000)
For each edge with one-way inverse of digitalisation way : cost=-1  (or 100000) reverse_cost=length
All another edges are not in graphe. 

shortest_path_astar:

has_reverse_cost = false :
Edges with 'cost=-1' are forbiden and Pgrouting don't used them. 'Reverse_cost' information is not used.

has_reverse_cost = true:
Edges with 'cost=-1' are used if 'reserve_cost' is more than 0. Cost used by pgrouting is 'reserve_cost' column.
Edges with 'reverse_cost=-1' are used if 'cost' is more than 0. Cost used by pgrouting is 'cost' column.

T his computing is correct.

Driving_distance:

has_reverse_cost = false :
Edges with 'cost=-1' are forbiden and Pgrouting don't used them. 'Reverse_cost' information is not used.

has_reverse_cost = true :
Case one : Edge with 'cost=-1' and 'reverse_cost=length':
Edge can be traveled on digitalisation way ( cost =-1!!). Cost used by pgrouting is 'Reverse_cost' column.

Case two : Edge with cost=length and reverse_cost=-1:
Edge can be traveled on inverse digitalisation way. More, Cost used by pgrouting is 'cost' column.

In this two case, pgrouting don't respect restrictions. This computing is not correct.

Why I would like to used this method. I prefer driving-distance functions because when we must compute a lot of distances with same departure point, this method is more fast than 'shortest_path_astar' method. After, I can get distance with nodes directly.

Example : get distance between shop and 100 customers.

I can create little graphe ,function, and snapshot.

This is zip file with:
http://imaptools.com:8080/dl/pgRouting-bug52.zip

*Bug1.png You can see :

• Shortest_path function result : Green line
• Graph with digitalisation sens
• Id of vertex
• One way of 2 edges : red arrows

To go to vertex(48) since vertex (540), pgrouting is doing good choice because the edge (2: gid 51) has a big cost value . Full distance is 1159 meters.

*Bug2.png You can see :

• Driving distance result: blue labels and variant color : Distance ( meters)
• Edges used by pgrouting : blue line
• One way of 2 edges : red arrows

To go to vertex(48) since vertex(540), pgrouting takes the edge (2) with big cost value and he used reverse_cost value to calculate full distance.

Distance vertex must be egal to 1159.

*Dump with my graphe . (create a tif1104 schema before import)

Query:

 select * 
 from shortest_path('
     select 
      id
      ,source
      ,target
      ,cost
      ,reverse_cost,
      to_cost
      ,rule

     from  
      tif1104.graphe
     where 
      statut is true
      order by id',
     540,
    48,
    false,
    true )

select 
* 
from  
 driving_distance(' 
    select 
     id
     ,source
     ,target
     ,cost
     ,reverse_cost
     ,to_cost
     ,rule
    from 
     tif1104.graphe
    where 
     statut is true
    order by id',
    540,
    2000,
    false,
    true)