[pgrouting-dev] Building TRSP branch

Steve_Horn · June 11, 2012, 7:41pm

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 as a baseline)

Here is where I’m at:

git clone 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”?

Thanks!
-Steve

Stephen_Woodbridge1 · June 11, 2012, 8:08pm

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 as
a baseline)

Here is where I'm at:
# git clone 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

Steve_Horn · June 11, 2012, 11:58pm

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.

I’m more familiar with apt get and adding repositories. Does yum work similarly? Just curious and trying to learn. Thanks!

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 as
a baseline)

Here is where I’m at:

git clone 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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Steve Horn

Stephen_Woodbridge1 · June 12, 2012, 12:26am

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>
        as
        a baseline)

        Here is where I'm at:
        # git clone 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@lists.osgeo.org
    http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

--
Steve Horn

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

dkastl · June 12, 2012, 8:59am

Hi Steve,

There is a project called ELGIS, which provides “Geo software” packages for Centos, Redhat and Fedora.
http://wiki.osgeo.org/wiki/Enterprise_Linux_GIS

They also have pgRouting packages, but not with TRSP.
But you can look at the package .spec file, which describes what is required (packages and patches) to compile and build the packages: https://projects.argeo.org/elgis/svn/factory/trunk/rpmbuild/elgis/pgrouting/

I thought it could be helpful.

Daniel

On Tue, Jun 12, 2012 at 2:26 AM, Stephen Woodbridge <woodbri@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>
as
a baseline)

Here is where I’m at:

git clone 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@lists.osgeo.org
http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

–
Steve Horn

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

Steve_Horn · June 12, 2012, 1:17pm

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 )

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/

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?

Thanks for your efforts on this!

On Mon, Jun 11, 2012 at 8:26 PM, Stephen Woodbridge <woodbri@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>
as
a baseline)

Here is where I’m at:

git clone 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@lists.osgeo.org
http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

–
Steve Horn

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Steve Horn

Stephen_Woodbridge1 · June 12, 2012, 2:33pm

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 )

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/

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@swoodbridge.com <mailto:woodbri@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>>
                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>>
                # 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@lists.osgeo.org <mailto:pgrouting-dev@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@lists.osgeo.org <mailto:pgrouting-dev@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@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

--
Steve Horn

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

Steve_Horn · June 12, 2012, 2:54pm

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@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 )

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/

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@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@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>>
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>>

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@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@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@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@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@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

–
Steve Horn

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Steve Horn

Stephen_Woodbridge1 · June 12, 2012, 3:14pm

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.

-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@swoodbridge.com <mailto:woodbri@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@swoodbridge.com <mailto:woodbri@swoodbridge.com>
        <mailto:woodbri@swoodbridge. com
        <mailto:woodbri@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>>>
                        # 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@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>
        <mailto:pgrouting-dev@lists. osgeo.org
        <mailto:pgrouting-dev@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@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>
        <mailto:pgrouting-dev@lists. osgeo.org
        <mailto:pgrouting-dev@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@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>
        <mailto:pgrouting-dev@lists. osgeo.org
        <mailto:pgrouting-dev@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@lists.osgeo.org <mailto:pgrouting-dev@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@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

--
Steve Horn

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

dkastl · June 12, 2012, 3:19pm

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@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.

-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@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@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@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)

<mailto:woodbri@swoodbridge. com

mailto:[woodbri@swoodbridge.com](mailto:woodbri@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@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

<mailto:pgrouting-dev@lists. osgeo.org

mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@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@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

<mailto:pgrouting-dev@lists. osgeo.org

mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@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@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

<mailto:pgrouting-dev@lists. osgeo.org

mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@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@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@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@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

–
Steve Horn

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

Steve_Horn · June 12, 2012, 4:59pm

The routes are actually not important, only the distances.

The actual implementation is something like this:

Get a driving_distance polygon using pgRouting functions.
Join to another geometry table where ST_Intersects which contains important geographic areas for our application domain.
For each of those geometric shapes that ST_Intersects with the drive time polygon, calculate drive time from drive time centroid to the centroid of each of the geographic areas from our domain table.

Side note:
I’m forcing myself to debug into the astar_boost_wrapper.cpp file to figure out the cause of the problems I’m seeing with the astar function. The only problem I’m having is there is no DBG() defined in the file, so I’m trying to figure out the best way to print debug statements back to pgadmin where I"m running my query. Any pointers there (no pun intended!)?

On Tue, Jun 12, 2012 at 11:14 AM, Stephen Woodbridge <woodbri@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:

I thought of this but really didn’t know where to start.
It sounds like Daniel has a lead on an existing branch of code with this possibility. Going to take a dive now!

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.

-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@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@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@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)

<mailto:woodbri@swoodbridge. com

mailto:[woodbri@swoodbridge.com](mailto:woodbri@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@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

<mailto:pgrouting-dev@lists. osgeo.org

mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@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@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

<mailto:pgrouting-dev@lists. osgeo.org

mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@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@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

<mailto:pgrouting-dev@lists. osgeo.org

mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@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@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@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@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

–
Steve Horn

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Steve Horn

Jay_Mahadeokar · June 12, 2012, 5:46pm

Hi Daniel, Steve,

On Tue, Jun 12, 2012 at 8:49 PM, Daniel Kastl <daniel@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@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@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@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@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)

<mailto:woodbri@swoodbridge. com

mailto:[woodbri@swoodbridge.com](mailto:woodbri@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@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

<mailto:pgrouting-dev@lists. osgeo.org

mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@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@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

<mailto:pgrouting-dev@lists. osgeo.org

mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@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@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

<mailto:pgrouting-dev@lists. osgeo.org

mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@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@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@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@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

–
Steve Horn

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar