[pgrouting-dev] Building TRSP branch
Steve Horn
steve at stevehorn.cc
Tue Jun 12 07:54:58 PDT 2012
We have a function that performs anywhere between 10 and 800 shortest paths
at a time, and we are trying to speed that up.
Solving 86 shortest_paths:
Dijkstra (pgRouting shortest_path()): 27328 milliseconds
TRSP (pgRouting turn_restrict_shortest_path()): 22405 milliseconds
So it is somewhat faster, but I'm not getting the boost I was hoping for.
As far as I know, both of the heuristic based algorithms are broken in
pgRouting (shooting star has the one-way bug, and a-star has a memory
management issue).
A-Star will completely hose PostgreSQL if I run A-Star in combination with
any other pgRouting function in the same process ID (procpid from
pg_stat_activity).
Here is an output of PostgreSQL log when I run a-star:
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
LOG: server process (PID 23497) was terminated by signal 6: Aborted
LOG: terminating any other active server processes
WARNING: terminating connection because of crash of another server process
DETAIL: The postmaster has commanded this server process to roll back the
current transaction and exit, because another server process exited
abnormally and possibly corrupted shared memory.
HINT: In a moment you should be able to reconnect to the database and
repeat your command.
LOG: all server processes terminated; reinitializing
LOG: database system was interrupted; last known up at 2012-06-12 10:57:51
EDT
LOG: database system was not properly shut down; automatic recovery in
progress
LOG: redo starts at E2/94CC82B0
LOG: record with zero length at E2/94CF7F90
LOG: redo done at E2/94CF7F40
LOG: database system is ready to accept connections
LOG: autovacuum launcher started
On Tue, Jun 12, 2012 at 10:33 AM, Stephen Woodbridge <
woodbri at swoodbridge.com> wrote:
> On 6/12/2012 9:17 AM, Steve Horn wrote:
>
>> Was not able to find these libraries via package manager, but I did get
>> pgRouting and dependencies installed manually.
>>
>> The "cannot find -lgmp" referred to a dependency of CGAL that needed to
>> be installed ( http://gmplib.org/manual/**Installing-GMP.html#**
>> Installing-GMP<http://gmplib.org/manual/Installing-GMP.html#Installing-GMP>)
>>
>> Also of note is that CGAL needs a specific version of the Boost
>> libraries to work (1.41).
>> After successful pgRouting make/make install then I ran the
>> driving_distance function to test and got this:
>>
>> “Error while loading shared libraries: libboost_thread.so.1.41.0: cannot
>> open shared object file: No such file or directory"
>>
>> Used the information in this blog to correct that error:
>> http://somethingididnotknow.**wordpress.com/2012/02/17/fix-**
>> the-error-while-loading-**shared-libraries-libboost_**
>> thread-so-1-48-0-cannot-open-**shared-object-file-no-such-**
>> file-or-directory-error/<http://somethingididnotknow.wordpress.com/2012/02/17/fix-the-error-while-loading-shared-libraries-libboost_thread-so-1-48-0-cannot-open-shared-object-file-no-such-file-or-directory-error/>
>>
>>
>> Hope this helps someone in the future.
>>
>> Steve: Haven't done a deep dive into the TRSP functionality -but I am
>> impressed at the surface. Does it use an A Star algorithm at the core?
>>
>
> I'm afraid I have not looked in detail at the exact algorithm but I
> believe it uses a combination of Dijkstra that is node based and then uses,
> edge based exploration to navigate around the turn restrictions.
>
> A Star requires a heuristic so you pass the end points of the edges which
> we do not pass in TRSP, so we are not doing that. That might be an
> interesting future enhancement that could speed TRSP up even faster. My
> rough timing tests showed that performance was a little slower than
> Dijkstra without any restrictions, but about 5x faster than our broken
> Shooting Star.
>
> Roni, If you have a chance it would be good if you could provide a little
> more background information on how TRSP solves.
>
> Thanks,
> -Steve W
>
> Thanks for your efforts on this!
>>
>> On Mon, Jun 11, 2012 at 8:26 PM, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.**com<woodbri at swoodbridge.com>>>
>> wrote:
>>
>> On 6/11/2012 7:58 PM, Steve Horn wrote:
>>
>> Trying to manually build and install the gmp dependency for
>> cgal..but
>> I'm curious how you can install it through yum. The searches you
>> provided do not turn up anything.
>>
>>
>> You probably need to google "centos cgal" and then add an
>> appropriate repository to yum. I forget the exact way to do that.
>>
>>
>> I'm more familiar with apt get and adding repositories. Does yum
>> work
>> similarly? Just curious and trying to learn. Thanks!
>>
>>
>> Yes, yum is the CentOS equivalent to apt-get. They both work in
>> similar ways. There were some good yum howto or tutorials that I
>> learned from when I needed to use it that I found via google.
>>
>> -Steve
>>
>> On Monday, June 11, 2012, Stephen Woodbridge wrote:
>>
>> On 6/11/2012 3:41 PM, Steve Horn wrote:
>>
>> Hello again :)
>>
>> Trying to build and install the trsp branch on my CentOS
>> linux box.
>> (Using
>> https://github.com/pgRouting/ pgrouting/wiki/Developer---
>> Getting-Started
>> <https://github.com/pgRouting/ pgrouting/wiki/Developer---
>> Getting-Started
>> <https://github.com/pgRouting/**pgrouting/wiki/Developer---**
>> Getting-Started<https://github.com/pgRouting/pgrouting/wiki/Developer---Getting-Started>
>> >>
>> as
>> a baseline)
>>
>> Here is where I'm at:
>> # git clone https://github.com/pgRouting/ pgrouting.git
>> <https://github.com/pgRouting/ pgrouting.git
>> <https://github.com/pgRouting/**pgrouting.git<https://github.com/pgRouting/pgrouting.git>
>> >>
>> # cd pgrouting
>>
>> //Hack around installing GAUL
>>
>> # cmake -DWITH_TSP=ON -DWITH_DD=ON .
>> -- POSTGRESQL_EXECUTABLE is POSTGRESQL_EXECUTABLE-NOTFOUND
>> -- Found PostgreSQL: /usr/include/postgresql/
>> include/server,
>> /usr/pgsql-9.1/lib/libpq.so
>> Boost headers were found here: /usr/include
>> Output directory for libraries is set to /usr/pgsql-9.1/lib
>> Installation directory for libraries is set to
>> /usr/pgsql-9.1/lib and
>> for SQL files is set to /usr/share/pgrouting
>> Installation directory for libraries is set to
>> /usr/pgsql-9.1/lib
>> -- Configuring done
>> -- Generating done
>> -- Build files have been written to: /home/shorn/pgrouting
>>
>> # make
>> Linking CXX shared library ../../../lib/librouting_tsp.so
>> */usr/bin/ld: cannot find -lgmp //THIS APPEARS TO BE
>> THE PROBLEM?*
>> collect2: ld returned 1 exit status
>> make[2]: *** [lib/librouting_tsp.so] Error 1
>> make[1]: *** [extra/tsp/src/CMakeFiles/
>> routing_tsp.dir/all] Error 2
>>
>> make: *** [all] Error 2
>>
>> Can anyone help me understand the error "Cannot find
>> -lgmp"?
>>
>>
>> For TSP you need to instal GUAL and for DD you need the CGAL
>> libraries.
>>
>> Try:
>>
>> yum search libcgal
>> yum search cgal
>>
>> You probably need the dev package also.
>>
>> After you:
>>
>> cd pgrouting
>> git checkout trsp ## switch to trsp branch
>> git pull
>> cmake -DWITH_TRSP=ON -DWITH_TSP=ON -DWITH_DD=ON .
>>
>> -Steve
>>
>> ______________________________ _________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.**
>> osgeo.org <pgrouting-dev at lists.osgeo.org>>
>>
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>> **> >
>>
>>
>>
>> --
>> Steve Horn
>>
>>
>>
>> ______________________________ _________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.**
>> osgeo.org <pgrouting-dev at lists.osgeo.org>>
>>
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>> **>
>>
>>
>> ______________________________ _________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>> >
>>
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>> **>
>>
>>
>>
>>
>> --
>> Steve Horn
>>
>>
>>
>> ______________________________**_________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>>
>
> ______________________________**_________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>
--
Steve Horn
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20120612/44a69938/attachment-0001.html>
More information about the pgrouting-dev
mailing list