GSOC2012 Razequl Islam R13

Initial plans for the project

Implementation for bi directional dijkstra and bi directional A* in pgrouting with some nice to have features like custom heap, turn restriction, highway hierarchy etc.

Plans as modified with mentors

My mentors asked me to implement test application that will enable user to run the codes without the postgis database in addition to my initial plans. We also decided to implement to provide option to select start and ending position anywhere in an edge in addition to standard node to node routing.

Actual accomplishments

I have implemented bi directional dijkstra and bi directional A* in pgrouting. I have also developed the test application that enables user to test the code without database. I have developed custom minheap and used that with bi directional A*.

Where the source code is

My source code can be found in https://github.com/zibon/pgrouting/
Please download the latest revision. My works are in bdsp and bdastar directories under extra directory.

How to build and install it

You must have the prerequisits for running pgrouting installed. For more information go to:http://www.pgrouting.org/documentation.html
Download the source from the above location. Then go to the pgrouting directory and run the following commands:

• cmake CMakeLists.txt
• make
• make install

This should install the pgrouting with bi directional dijkstra and bi directional A*. Then run the following sqls in the database you want to use them:

• /extra/bdsp/sql/routing_bdsp.sql
• /extra/bdastar/sql/routing_bdastar.sql

These will install the stored procedures in your database and enable you to call functions bidir_dijkstra_shortest_path() and bidir_astar_shortest_path().

There is also a sample table dumped as ways.sql in the sql directory. Use this table if necessary. Sample query:

SELECT * FROM bidir_dijkstra_shortest_path('
    SELECT gid as id,
    source::integer,
    target::integer,
    length::double precision as cost,
    length::double precision as reverse_cost
    FROM ways',
    5700, 6733, true, true);  

The correct output for this query is in the ans1.txt file under the tester directory.

SELECT * FROM bidir_astar_shortest_path('
    SELECT gid as id,
    source::integer,
    target::integer,
    length::double precision as cost,
    length::double precision as reverse_cost,
    x1, y1, x2, y2
    FROM ways',
    6585, 8247, true, true);  

The correct output for this query is in the ans2.txt file under the tester directory.

How to compile and run the tester

Go to the Tester directory

/pgrouting/extra/bdsp/tester
or
/pgrouting/extra/bdastar/tester

Then run make
and then

./BDDTester if you ar in /bdsp/tester
or
./BDATester if you are in /bdastar/tester.

The tester will generate the paths in files bdd1-bdd6.txt or bda1-bda6.txt respectively. There are also ans1-ans6.txt files in the folder that contains the actual shortest paths. The generated shortest paths will be compared with these paths and the result of the comparison will be written in the output.txt file.

Known issues

Please make your query including reverse_cost and putting the flags for both directed = true and have_reverse_cost = true. Setting directed = false or has_reverse_cost = false sometimes give wrong result.

Future ideas for this code if someone had time to work on it more

The issues mentioned in 7 may be fixed. The nice to have features like turn restriction, highway hierarchy may be implemented.

What worked well and not so well for you during GSoC

I started very well but got slowed down in the middle and unfortunately had problem with my laptop.

If you did this again, what would you like to see done differently

I have weakness in Linux environment, I would like to overcome this.