We have a function that performs anywhere between 10 and 800 shortest paths at a time, and we are trying to speed that up.<div><br></div><div>Solving 86 shortest_paths:</div><div>Dijkstra (pgRouting shortest_path()): 27328 milliseconds</div>
<div>TRSP (pgRouting turn_restrict_shortest_path()): 22405 milliseconds</div><div><br></div><div>So it is somewhat faster, but I'm not getting the boost I was hoping for.</div><div><br></div><div>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).</div>
<div><br></div><div>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).</div><div>Here is an output of PostgreSQL log when I run a-star:</div>
<div><br></div><div><div>terminate called after throwing an instance of 'std::bad_alloc'</div><div> what(): std::bad_alloc</div><div>LOG: server process (PID 23497) was terminated by signal 6: Aborted</div><div>
LOG: terminating any other active server processes</div><div>WARNING: terminating connection because of crash of another server process</div><div>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.</div>
<div>HINT: In a moment you should be able to reconnect to the database and repeat your command.</div><div>LOG: all server processes terminated; reinitializing</div><div>LOG: database system was interrupted; last known up at 2012-06-12 10:57:51 EDT</div>
<div>LOG: database system was not properly shut down; automatic recovery in progress</div><div>LOG: redo starts at E2/94CC82B0</div><div>LOG: record with zero length at E2/94CF7F90</div><div>LOG: redo done at E2/94CF7F40</div>
<div>LOG: database system is ready to accept connections</div><div>LOG: autovacuum launcher started</div></div><div><br></div><div><br><div class="gmail_quote">On Tue, Jun 12, 2012 at 10:33 AM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">On 6/12/2012 9:17 AM, Steve Horn wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Was not able to find these libraries via package manager, but I did get<br>
pgRouting and dependencies installed manually.<br>
<br>
The "cannot find -lgmp" referred to a dependency of CGAL that needed to<br>
be installed ( <a href="http://gmplib.org/manual/Installing-GMP.html#Installing-GMP" target="_blank">http://gmplib.org/manual/<u></u>Installing-GMP.html#<u></u>Installing-GMP</a> )<br>
<br>
Also of note is that CGAL needs a specific version of the Boost<br>
libraries to work (1.41).<br>
After successful pgRouting make/make install then I ran the<br>
driving_distance function to test and got this:<br>
<br>
“Error while loading shared libraries: libboost_thread.so.1.41.0: cannot<br>
open shared object file: No such file or directory"<br>
<br>
Used the information in this blog to correct that error:<br>
<a href="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/" target="_blank">http://somethingididnotknow.<u></u>wordpress.com/2012/02/17/fix-<u></u>the-error-while-loading-<u></u>shared-libraries-libboost_<u></u>thread-so-1-48-0-cannot-open-<u></u>shared-object-file-no-such-<u></u>file-or-directory-error/</a><br>
<br>
<br>
Hope this helps someone in the future.<br>
<br>
Steve: Haven't done a deep dive into the TRSP functionality -but I am<br>
impressed at the surface. Does it use an A Star algorithm at the core?<br>
</blockquote>
<br></div>
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.<br>
<br>
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.<br>
<br>
Roni, If you have a chance it would be good if you could provide a little more background information on how TRSP solves.<br>
<br>
Thanks,<br>
-Steve W<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
Thanks for your efforts on this!<br>
<br>
On Mon, Jun 11, 2012 at 8:26 PM, Stephen Woodbridge<br></div><div><div class="h5">
<<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a> <mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>> wrote:<br>
<br>
On 6/11/2012 7:58 PM, Steve Horn wrote:<br>
<br>
Trying to manually build and install the gmp dependency for<br>
cgal..but<br>
I'm curious how you can install it through yum. The searches you<br>
provided do not turn up anything.<br>
<br>
<br>
You probably need to google "centos cgal" and then add an<br>
appropriate repository to yum. I forget the exact way to do that.<br>
<br>
<br>
I'm more familiar with apt get and adding repositories. Does yum<br>
work<br>
similarly? Just curious and trying to learn. Thanks!<br>
<br>
<br>
Yes, yum is the CentOS equivalent to apt-get. They both work in<br>
similar ways. There were some good yum howto or tutorials that I<br>
learned from when I needed to use it that I found via google.<br>
<br>
-Steve<br>
<br>
On Monday, June 11, 2012, Stephen Woodbridge wrote:<br>
<br>
On 6/11/2012 3:41 PM, Steve Horn wrote:<br>
<br>
Hello again :)<br>
<br>
Trying to build and install the trsp branch on my CentOS<br>
linux box.<br>
(Using<br>
<a href="https://github.com/pgRouting/" target="_blank">https://github.com/pgRouting/</a> pgrouting/wiki/Developer---<br>
Getting-Started<br>
<<a href="https://github.com/pgRouting/" target="_blank">https://github.com/pgRouting/</a> pgrouting/wiki/Developer---<br>
Getting-Started<br>
<<a href="https://github.com/pgRouting/pgrouting/wiki/Developer---Getting-Started" target="_blank">https://github.com/pgRouting/<u></u>pgrouting/wiki/Developer---<u></u>Getting-Started</a>>><br>
as<br>
a baseline)<br>
<br>
Here is where I'm at:<br>
# git clone <a href="https://github.com/pgRouting/" target="_blank">https://github.com/pgRouting/</a> pgrouting.git<br>
<<a href="https://github.com/pgRouting/" target="_blank">https://github.com/pgRouting/</a> pgrouting.git<br>
<<a href="https://github.com/pgRouting/pgrouting.git" target="_blank">https://github.com/pgRouting/<u></u>pgrouting.git</a>>><br>
# cd pgrouting<br>
<br>
//Hack around installing GAUL<br>
<br>
# cmake -DWITH_TSP=ON -DWITH_DD=ON .<br>
-- POSTGRESQL_EXECUTABLE is POSTGRESQL_EXECUTABLE-NOTFOUND<br>
-- Found PostgreSQL: /usr/include/postgresql/<br>
include/server,<br>
/usr/pgsql-9.1/lib/libpq.so<br>
Boost headers were found here: /usr/include<br>
Output directory for libraries is set to /usr/pgsql-9.1/lib<br>
Installation directory for libraries is set to<br>
/usr/pgsql-9.1/lib and<br>
for SQL files is set to /usr/share/pgrouting<br>
Installation directory for libraries is set to<br>
/usr/pgsql-9.1/lib<br>
-- Configuring done<br>
-- Generating done<br>
-- Build files have been written to: /home/shorn/pgrouting<br>
<br>
# make<br>
Linking CXX shared library ../../../lib/librouting_tsp.so<br>
*/usr/bin/ld: cannot find -lgmp //THIS APPEARS TO BE<br>
THE PROBLEM?*<br>
collect2: ld returned 1 exit status<br>
make[2]: *** [lib/librouting_tsp.so] Error 1<br>
make[1]: *** [extra/tsp/src/CMakeFiles/<br>
routing_tsp.dir/all] Error 2<br>
<br>
make: *** [all] Error 2<br>
<br>
Can anyone help me understand the error "Cannot find -lgmp"?<br>
<br>
<br>
For TSP you need to instal GUAL and for DD you need the CGAL<br>
libraries.<br>
<br>
Try:<br>
<br>
yum search libcgal<br>
yum search cgal<br>
<br>
You probably need the dev package also.<br>
<br>
After you:<br>
<br>
cd pgrouting<br>
git checkout trsp ## switch to trsp branch<br>
git pull<br>
cmake -DWITH_TRSP=ON -DWITH_TSP=ON -DWITH_DD=ON .<br>
<br>
-Steve<br>
<br>
______________________________ _________________<br>
pgrouting-dev mailing list<br></div></div>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a> <mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><div class="im">
<br>
<a href="http://lists.osgeo.org/" target="_blank">http://lists.osgeo.org/</a> mailman/listinfo/pgrouting-dev<br>
<<a href="http://lists.osgeo.org/" target="_blank">http://lists.osgeo.org/</a> mailman/listinfo/pgrouting-dev<br>
<<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><u></u>> ><br>
<br>
<br>
<br>
--<br>
Steve Horn<br>
<br>
<br>
<br>
______________________________ _________________<br>
pgrouting-dev mailing list<br></div>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a> <mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><div class="im">
<br>
<a href="http://lists.osgeo.org/" target="_blank">http://lists.osgeo.org/</a> mailman/listinfo/pgrouting-dev<br>
<<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><u></u>><br>
<br>
<br>
______________________________ _________________<br>
pgrouting-dev mailing list<br></div>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a> <mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><div class="im">
<br>
<a href="http://lists.osgeo.org/" target="_blank">http://lists.osgeo.org/</a> mailman/listinfo/pgrouting-dev<br>
<<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><u></u>><br>
<br>
<br>
<br>
<br>
--<br>
Steve Horn<br>
<br>
<br>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</div></blockquote><div class="HOEnZb"><div class="h5">
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br>Steve Horn<br><br>
</div>