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.
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.
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).
Hope the upcoming weeks are similarly productive! 😉