• Report 14
• Report 13
• Report 12
• Report 11
• Report 10
• Report 9
• Report 8
• Report 7
• Report 6
• Report 5
• Report 4
• Report 3
• Report 2
• Report 1

• Name: Khondoker Md. Razequl Islam
• Country: Bangladesh
• School and degree: University of Dhaka & Bachelor of Science
• Major: Computer Science & Engineering
• Email: [email protected]

• https://github.com/pgRouting/pgrouting/wiki/Bidirectional-Shortest-Path

• Report 1, 25-05-2012
• Report 2, 01-06-2012
• Report 3, 09-06-2012
• Report 4, 15-06-2012
• Report 5, 22-06-2012
• Report 6, 29-06-2012
• Report 7, 06-07-2012
• Report 8, 13-07-2012
• Report 9, 20-07-2012
• Report 10, 27-07-2012
• Report 11, 03-08-2012
• Report 12, 10-08-2012
• Report 13, 17-08-2012

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.

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.

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

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.

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.

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.

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.

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

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

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

For the twelfth week I had the following plans :

• will add some test cases.
• add the percentage edge for start and stop like TRSP, add tests for this

I have already done the following tasks:

• completed some test cases
• started adding the percentage edge for start and stop

• complete adding the percentage edge for start and stop
• start documentation

For the eleventh week I had the following plans :

• will complete the tester application for bi directional A* search.
• start commenting in the existing code.

I have already done the following tasks:

• added comment on bidirectional dijkstra.
• tested bdastar and found some bug and now fixing them.

• will add some test cases.
• add the percentage edge for start and stop like TRSP, add tests for this

For the tenth week I had the following plans :

• Will complete tester application.
• More comparative performance evaluation on bidirdijsktra and bidirastar

I have already done the following tasks:

• completed the tester application for bidirectional dijkstra.

• will complete the tester application for bi directional A* search.
• start commenting in the existing code.

For the ninth week I had the following plans :

• Comparative performance evaluation.
• Commit implemented bi-directional A* search to my pgrouting fork.
• Add comment to the existing bi-directional Dijkstra codes as my mentor said and update the codes.

I have already done the following tasks:

• Committed the implemented bi-directional A* search
• Start evaluating performance. will do more evaluation next week.
• Start coding the tester application.

• Will complete tester application.
• More comparative performance evaluation on bidirdijsktra and bidirastar.

For the Eighth week I had the following plans :

• Comparative performance evaluation.
• Commit implemented bi-directional A* search to my pgrouting fork.
• Add comment to the existing bi-directional Dijkstra codes as my mentor said and update the codes.

I haven't done much progress this week. I was busy with some academic work.

• Will continue work with previous week plan.

For the seventh week I had the following plans :

• Finish up the implementation of A* search and test it on the sample networks I have.

I have already done the following tasks:

• Finished up the implementation of A* search and tested it on the sample networks.

• Comparative performance evaluation.
• Commit implemented bi-directional A* search to my pgrouting fork.
• Add comment to the existing bi-directional Dijkstra codes as my mentor said and update the codes.

For the sixth week I had the following plans :

• start implementation of bidirectional A* search.
• Investigate and fix the regarding undirected graph in the wrapper class of bidirectional dijkstra.
• If possible then test performence of bidirectional dijkstra on a larger sample.

I have already done the following tasks:

• Started the implementation of bidirectional A* search. I hope to finish it by next week.
• Downloaded another road network from OSM. But it is also too small for testing.

• Finish up the implementation of A* search and test it on the sample networks I have.

For the fifth week I had the following plans :

• Start coding bi directional A*. implement necessary data structures and the algorithm.
• check the performance.

I have already done the following tasks:

• Incorporated bidirectional dijkstra with the pgrouting fork.
• Tested performance on a small sample but need to test on a large sample.
• Design the data structure of bidirectional A* search.

• start implementation of bidirectional A* search.
• Investigate and fix the regarding undirected graph in the wrapper class of bidirectional dijkstra.
• If possible then test performence of bidirectional dijkstra on a larger sample.

For the fourth week I had the following plans :

• Comparative performance evaluation.
• if necessary start implementing heap data structure.

I have already done the following tasks:

• Finished up the implementation of heap data structure.
• solved the problem to commit in the github and added my codes to pgrouting repository.

• Start coding bi directional A*. implement necessary data structures and the algorithm.
• check the performance.

For the third week i had the following plans :

• Finish up the first implementation of bi-directional Dijkstra and evaluate the performance.
• if necessary start implementing heap data structure.

I have already done the following tasks:

• Finished up the implementation of first version of Bi-directional Dijkstra.
• send the source code to developer community via email for their feedback(trying to commit it to github but having some problems)

• Comperative performance evaluation.
• if necessary start implementing heap data structure.

• having some problems to commit in the github.

For the second week i had the following plans :

• Review the data structures and algorithm for bi directional Dijkstra.
• Start coding bi directional Dijkstra and check the performance.
• The initial implementation will use STL for the heap data structure. Later if necessary, own binary heap will be implemented.

I have already done the following tasks:

• Started coding on bi-directional Dijkstra using the proposed data structure last week. For heap data structure i am using two STL priority queue.
• Could not yet evaluate the performance.Hope i can evaluate the performance next week.

• Finish up the first implementation of bi-directional Dijkstra and evaluate the performance.
• if necessary start implementing heap data structure.

• learn how to test run and debug using postgresql.

For the first week I had the following plans:

• System study, get used to pgRouting and development environment
• Design the architecture and data structures to implement bi directional search algorithms.

I already have done the following task:

• Download and install postgresql and pgRouting core with all the dependencies in Ubuntu 12.04 LTS.
• With help from pgRouting workshop created a sample database called routing to run and test pgRouting.
• Successfully built pgRouting and tested it with shortest_path and other queries.
• Download and build the turn restricted shortest path (trsp). Tested it with empty turn restriction table.
• Installed GIT hub, had some practice on it and created a branch for bi directional shortest path.
• Design a rough architecture and data structure for bi directional Dijkstra which is to be submitted to the mentors for review. It is given here in the next section. Thanks to Stephen and Daniel for their cordial help and quick responses.

SQL stored procedure should be like shortest path as follows:

`    CREATE OR REPLACE FUNCTION shortest_path_bdd(sql text, source_id integer,   
         target_id integer, directed boolean, has_reverse_cost boolean)    
         RETURNS SETOF path_result    
         AS '$libdir/librouting'    
         LANGUAGE 'C' IMMUTABLE STRICT;`

Here path_result will be consist of node_id, edge_id and cost.

In wrapper class the internal edge structure will be as follows:

`    struct edge
     {
        int id;
        int source;
        int target;
        double cost;
        double reverse_cost;
     }`

Wrong direction will be denoted either with a negative value or a very high value.

In the core implementation the graph will be represented as an adjacency list. That is there will be a node list, where every node will have the following structure:

`    struct Node
     {
        Int ID,
        vector<int> connected_nodes;
        vector<int> connected_edges;
     }`

The core information will be kept in edge_list where the structure of edge will be as follows:

`    struct Edge
     {
        int EdgeID;
        int EdgeIndex;
        int Direction;
        double Cost;
        double ReverseCost;
        int StartNode;
        int EndNode;
     }`

• Review the data structures and algorithm for bi directional dijkstra.
• Start coding bi directional dijkstra and check the performance.
• The initial implementation will use STL for the heap data structure. Later if necessary, own binary heap will be implemented.

• Yet to run trsp with turn restriction table. But it is not that much crucial now, as we will focus on turn restriction at a later state.
• Need to learn how to run pgRouting on debug mode and get the debug output. Also need to learn how to measure the time taken to run the algorithm.
• I will continue communication with the mentors and resolve the issues.