Skip to content

GSoC 2012 Razequl Islam

Jump to bottom Edit New page
cvvergara edited this page Mar 17, 2017 · 3 revisions

Report List

Biography

  • Name: Khondoker Md. Razequl Islam
  • Country: Bangladesh
  • School and degree: University of Dhaka & Bachelor of Science
  • Major: Computer Science & Engineering
  • Email: ziboncsedu@gmail.com

GSoC project

My Status Reports

Report 13

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.

Report 12

Plans

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

Tasks Done

I have already done the following tasks:

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

Next Week Plan

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

Report 11

Plans

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.

Tasks Done

I have already done the following tasks:

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

Next Week Plan

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

Report 10

Plans

For the tenth week I had the following plans :

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

Tasks Done

I have already done the following tasks:

  • completed the tester application for bidirectional dijkstra.

Next Week Plan

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

Report 9

Plans

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.

Tasks Done

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.

Next Week Plan

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

Report 8

Plans

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.

Tasks Done

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

Next Week Plan

  • Will continue work with previous week plan.

Report 7

Plans

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.

Tasks Done

I have already done the following tasks:

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

Next Week Plan

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

Report 6

Plans

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.

Tasks Done

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.

Next Week Plan

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

Report 5

Plans

For the fifth week I had the following plans :

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

Tasks Done

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.

Next Week Plan

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

Report 4

Plans

For the fourth week I had the following plans :

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

Tasks Done

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.

Next Week Plan

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

Report 3

Plans

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.

Tasks Done

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)

Next Week Plan

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

Issues

  • having some problems to commit in the github.

Report 2

Plans

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.

Tasks Done

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.

Next Week Plan

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

Issues

  • learn how to test run and debug using postgresql.

Report 1

Plans

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.

Tasks Done

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.

Bi directional Dijkstra

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;
     }`

Next Week Plan

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

Issues

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

Contact: https://discourse.osgeo.org/c/pgrouting/pgrouting-dev

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally