[pgrouting-dev] Building TRSP branch
Jay Mahadeokar
jai.mahadeokar at gmail.com
Tue Jun 12 10:46:36 PDT 2012
Hi Daniel, Steve,
On Tue, Jun 12, 2012 at 8:49 PM, Daniel Kastl <daniel at georepublic.de> wrote:
> Jay already wrote an "All-Pair-Shortest-Path" function which should
> exactly do this.
> Of course it's in a separate branch named "apsp" ;-)
> https://github.com/pgRouting/pgrouting/tree/gsoc-tdsp/core/src
>
>
>
Also Kishore wrote an implementation for his mulitmodal routing as far as I
> remember:
> https://github.com/pgRouting/pgrouting/tree/apsp-johnson/core/src
>
> Jay, Kishore, is it the same?
>
> Daniel
>
>
>
>
> On Tue, Jun 12, 2012 at 5:14 PM, Stephen Woodbridge <
> woodbri at swoodbridge.com> wrote:
>
>> On 6/12/2012 10:54 AM, Steve Horn wrote:
>>
>>> We have a function that performs anywhere between 10 and 800 shortest
>>> paths at a time, and we are trying to speed that up.
>>>
>>
>> What are these routes used for afterwards? TSP?
>> When I built a TSP solver in routing engine I wrote, I ran Dijkstra once
>> for each "city" and extracted ALL the costs to the other "cities" from this
>> "city". This means if you have 10 nodes you only have to run 10 solutions,
>> not 10*10 solutions.
>>
>> You can do this with a modified version of the driving distance code that
>> allows you to extract the solved Dijkstra tree so you can extract all the
>> needed routes from the start node to all the other "cities".
>>
>> The other potential performance boost would be to write a solver where
>> you pass it the graph edges and a list of start and end nodes. Then you can
>> build the graph once and solve it for each pair of start, stop nodes. This
>> would eliminate the multiple graph builds assuming that are all in the same
>> graph region to start with. I would return results like:
>>
>
> route#, seq#, node#, edge#, cost
>>
>> where route# = 1..number_of_input_pairs
>> seq# is just 1..n for the edges in that route's result
>> and the rest are the same as the current solution sets.
>>
>>
All Pairs Shortest Paths algorithm in the tdsp branch gives the shortest
path values between all the pairs of nodes supplied to the query. The nodes
can be selected using bounding box. If there is no path in given bounding
box, it will return infinite distance. More detailed documentation is
present here: https://github.com/pgRouting/pgrouting/wiki/APSP
This can very efficient if the number of shortest path queries is
proportional to the number of nodes in bounding box. Else, if the shortest
path queries have to be performed only on a small subset of nodes in
bounding box, the approach given by Steve will be more efficient according
to me (It is basically multiple source shortest path problem).
> -Steve
>>
>>
>>> 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 <mailto:woodbri at swoodbridge.**com<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<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/<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>
>>> >
>>> <mailto: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<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<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>
>>> >
>>> <mailto: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<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>
>>> >
>>> <mailto: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>
>>> **> >
>>>
>>>
>>> ______________________________ _________________
>>> pgrouting-dev mailing list
>>> pgrouting-dev at lists.osgeo.org
>>> <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>>> >
>>> <mailto: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>
>>
>
>
>
> --
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl at georepublic.de
> Web: http://georepublic.de
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
--
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20120612/992e5ae4/attachment-0001.html>
More information about the pgrouting-dev
mailing list