Core TDSP Implementation

June 9, 2011


Its 3rd week of the coding phase of GSoc 2011 and my project seems to be well ahead of its schedule 😉  As per initial proposal, aim till June 15 was to code and test the core TDSP algorithm.

Current Progress:
The design details can be seen here.
* According to new plan, we are not using Boost Priority Queues for heap operations during dijkstra search.
Instead, I have implemented a binary heap that will provide the functionality.
I have also coded the data structures that would be required for the core – time dependent dijkstra implementation.
The initial working draft of algorithm is also ready.
Please find the source file here.
I have also organised the code into different header files – binary_heap.h, weight_map.h, edge_wrapper.h.
Added a boost – dijkstra test function which calls boost::dijkstra_shortest_paths() so as to verify the result.
I wrote a graph generator which can generate random graphs according to the parameters specified:
– number of vertices
– maximum outdegree of a vertex (I keep this 6 or 8 , since 6 is degree limit for planar graphs)
– Number of time windows and the range of time windows.
So, to see if the result returned by tdsp-dijkstra function is correct, I generated random graphs with time window 1, which starts from 0, meaning that the same travel time will be there for any given start time. This is basically static dijkstra.
I compared the results returned by tdsp-dijkstra and boost-dijkstra and I am getting same output. Tried for graphs with 20,100,500,1000 nodes with max outdegree 8. (generating graphs with nodes more than that was taking too much time and my CPU was getting overworked!)
Only difference in boost-output and tdsp-output comes when there are more than one shortest paths of same length. The there might be difference of predecessors. I guess that is because of different implementations of priority queue (binary_heap in my case).
I have updated the code in github gsoc-tdsp branch.
I have updated the weekly progress reports at the TDSP home page.
Hope the upcoming weeks are similarly productive!  😉

2 Responses to “Core TDSP Implementation”

  1. Bikram Says:

    Hi jay, thanks for maintaining such a nice blog, can u plz share u r views how IIT-K faculties helping M-Tech students for completing their Thesis-work and publishing papers? How many of your batch has got a chance to publish a paper ? If possible please throw some light over the matter.

    • Jay Mahadeokar Says:

      I have answered this question recently in the IIT and Gate cutoff story post. You would need to scroll down a lot as it would be one of the last few comments!

      Our batch has just started their research work so noone has published paper yet! We have 1 more year to go.. 🙂

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: