Hi Daniel, Steve,<br><br><div class="gmail_quote">On Tue, Jun 12, 2012 at 8:49 PM, Daniel Kastl <span dir="ltr"><<a href="mailto:daniel@georepublic.de" target="_blank">daniel@georepublic.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Jay already wrote an "All-Pair-Shortest-Path" function which should exactly do this.<div>Of course it's in a separate branch named "apsp" ;-)</div><div><a href="https://github.com/pgRouting/pgrouting/tree/gsoc-tdsp/core/src" target="_blank">https://github.com/pgRouting/pgrouting/tree/gsoc-tdsp/core/src</a></div>
<div><br> </div></blockquote><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div></div><div>Also Kishore wrote an implementation for his mulitmodal routing as far as I remember:</div>
<div><a href="https://github.com/pgRouting/pgrouting/tree/apsp-johnson/core/src" target="_blank">https://github.com/pgRouting/pgrouting/tree/apsp-johnson/core/src</a></div>
<div><br></div><div>Jay, Kishore, is it the same?</div><span class="HOEnZb"><font color="#888888"><div><br></div><div>Daniel</div><div><br></div><div><br></div></font></span><div><div><div class="h5"><br><br><div class="gmail_quote">
On Tue, Jun 12, 2012 at 5:14 PM, 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>On 6/12/2012 10:54 AM, Steve Horn wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
We have a function that performs anywhere between 10 and 800 shortest<br>
paths at a time, and we are trying to speed that up.<br>
</blockquote>
<br></div>
What are these routes used for afterwards? TSP?<br>
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.<br>
<br>
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".<br>
<br>
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:<br>
</blockquote></div></div></div></div></blockquote><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><div><div class="h5"><div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
route#, seq#, node#, edge#, cost<br>
<br>
where route# = 1..number_of_input_pairs<br>
seq# is just 1..n for the edges in that route's result<br>
and the rest are the same as the current solution sets.<br>
<br></blockquote></div></div></div></div></blockquote><div><br>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: <a href="https://github.com/pgRouting/pgrouting/wiki/APSP">https://github.com/pgRouting/pgrouting/wiki/APSP</a><br>
<br>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). <br>
<br> </div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><div><div class="h5"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
-Steve<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div>
<br>
Solving 86 shortest_paths:<br>
Dijkstra (pgRouting shortest_path()): 27328 milliseconds<br>
TRSP (pgRouting turn_restrict_shortest_path())<u></u>: 22405 milliseconds<br>
<br>
So it is somewhat faster, but I'm not getting the boost I was hoping for.<br>
<br>
As far as I know, both of the heuristic based algorithms are broken in<br>
pgRouting (shooting star has the one-way bug, and a-star has a memory<br>
management issue).<br>
<br>
A-Star will completely hose PostgreSQL if I run A-Star in combination<br>
with any other pgRouting function in the same process ID (procpid from<br>
pg_stat_activity).<br>
Here is an output of PostgreSQL log when I run a-star:<br>
<br>
terminate called after throwing an instance of 'std::bad_alloc'<br>
what(): std::bad_alloc<br>
LOG: server process (PID 23497) was terminated by signal 6: Aborted<br>
LOG: terminating any other active server processes<br>
WARNING: terminating connection because of crash of another server process<br>
DETAIL: The postmaster has commanded this server process to roll back<br>
the current transaction and exit, because another server process exited<br>
abnormally and possibly corrupted shared memory.<br>
HINT: In a moment you should be able to reconnect to the database and<br>
repeat your command.<br>
LOG: all server processes terminated; reinitializing<br>
LOG: database system was interrupted; last known up at 2012-06-12<br>
10:57:51 EDT<br>
LOG: database system was not properly shut down; automatic recovery in<br>
progress<br>
LOG: redo starts at E2/94CC82B0<br>
LOG: record with zero length at E2/94CF7F90<br>
LOG: redo done at E2/94CF7F40<br>
LOG: database system is ready to accept connections<br>
LOG: autovacuum launcher started<br>
<br>
<br>
On Tue, Jun 12, 2012 at 10:33 AM, Stephen Woodbridge<br></div></div><div><div>
<<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/12/2012 9:17 AM, Steve Horn wrote:<br>
<br>
Was not able to find these libraries via package manager, but I<br>
did get<br>
pgRouting and dependencies installed manually.<br>
<br>
The "cannot find -lgmp" referred to a dependency of CGAL that<br>
needed to<br>
be installed ( <a href="http://gmplib.org/manual/" target="_blank">http://gmplib.org/manual/</a> Installing-GMP.html#<br>
Installing-GMP<br>
<<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:<br>
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" target="_blank">http://somethingididnotknow</a>. <a href="http://wordpress.com/2012/02/17/fix-" target="_blank">wordpress.com/2012/02/17/fix-</a><br>
the-error-while-loading- shared-libraries-libboost_<br>
thread-so-1-48-0-cannot-open- shared-object-file-no-such-<br>
file-or-directory-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<br>
I am<br>
impressed at the surface. Does it use an A Star algorithm at the<br>
core?<br>
<br>
<br>
I'm afraid I have not looked in detail at the exact algorithm but I<br>
believe it uses a combination of Dijkstra that is node based and<br>
then uses, edge based exploration to navigate around the turn<br>
restrictions.<br>
<br>
A Star requires a heuristic so you pass the end points of the edges<br>
which we do not pass in TRSP, so we are not doing that. That might<br>
be an interesting future enhancement that could speed TRSP up even<br>
faster. My rough timing tests showed that performance was a little<br>
slower than Dijkstra without any restrictions, but about 5x faster<br>
than our broken Shooting Star.<br>
<br>
Roni, If you have a chance it would be good if you could provide a<br>
little more background information on how TRSP solves.<br>
<br>
Thanks,<br>
-Steve W<br>
<br>
Thanks for your efforts on this!<br>
<br>
On Mon, Jun 11, 2012 at 8:26 PM, Stephen Woodbridge<br>
<<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>><br></div></div>
<mailto:<a href="mailto:woodbri@swoodbridge" target="_blank">woodbri@swoodbridge</a>. com<div><div><br>
<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<br>
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<br>
that.<br>
<br>
<br>
I'm more familiar with apt get and adding repositories.<br>
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<br>
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/" 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><br>
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/" 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<br>
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<br>
/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:<br>
/home/shorn/pgrouting<br>
<br>
# make<br>
Linking CXX shared library<br>
../../../lib/librouting_tsp.so<br>
*/usr/bin/ld: cannot find -lgmp //THIS APPEARS<br>
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<br>
find -lgmp"?<br>
<br>
<br>
For TSP you need to instal GUAL and for DD you need<br>
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>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><br></div></div>
<mailto:<a href="mailto:pgrouting-dev@lists" target="_blank">pgrouting-dev@lists</a>. <a href="http://osgeo.org" target="_blank">osgeo.org</a><div><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>>><br>
<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/" 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>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><br></div>
<mailto:<a href="mailto:pgrouting-dev@lists" target="_blank">pgrouting-dev@lists</a>. <a href="http://osgeo.org" target="_blank">osgeo.org</a><div><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>>><br>
<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>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><br></div>
<mailto:<a href="mailto:pgrouting-dev@lists" target="_blank">pgrouting-dev@lists</a>. <a href="http://osgeo.org" target="_blank">osgeo.org</a><div><div><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>>><br>
<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>
--<br>
Steve Horn<br>
<br>
<br>
<br>
______________________________ _________________<br>
pgrouting-dev mailing list<br>
<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>><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>
<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>><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></div></blockquote><div><div>
<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></div></div><div class="im">-- <br><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse">Georepublic UG & Georepublic Japan<br>
eMail: <a href="mailto:daniel.kastl@georepublic.de" style="color:rgb(66,99,171)" target="_blank">daniel.kastl@georepublic.de</a><br>
Web: <a href="http://georepublic.de/" style="color:rgb(66,99,171)" target="_blank">http://georepublic.de</a></span><br>
</div></div>
<br>_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br></blockquote></div><br><br clear="all"><br>-- <br>Regards,<br>-Jay Mahadeokar<br><br>