GSOC2012 Razequl Islam R1

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.