Hello,<br><br>My weekly status report is as follows: <br>Project home page: <a href="https://github.com/pgRouting/pgrouting/wiki/Time-dependent---Dynamic-Shortest-Path">https://github.com/pgRouting/pgrouting/wiki/Time-dependent---Dynamic-Shortest-Path</a><br>
Report available here: <a href="https://github.com/jay-mahadeokar/GSoc-2011-Project-Docs/blob/master/weekly-reports/27-May-2011">https://github.com/jay-mahadeokar/GSoc-2011-Project-Docs/blob/master/weekly-reports/27-May-2011</a><br>
<br>Weekly Report #1  (Coding Phase)  <br><br>According to project plan:<br><br>25th May - 5th June:<br><br>* Finalize the overall architecture of the project.<br>* Finalize the database-design\ other storage format which will be used for dynamically <br>
  storing\updating the data for time-dependent edge weights.<br>* Finalize the class-diagram which will be used for the implementation.<br>* Finalize the prototypes for the SQL-queries and the SQL-shared library functions that must be <br>
  implemented.<br>* Decide the test cases and data that will be needed for rigorous testing of the modules.<br>* Start coding small trivial modules/functions that will be needed for the project.<br><br>6th June - 15th June:<br>
<br>* Implement the basic time-dependent dijkstra algorithm using Boost Graph Library and Boost Priority <br>  Queues Library assuming the time_dependent_cost<br>* function as black box.<br>* Test the basic function with dummy data.<br>
<br><br>Current Progress:<br><br>* We have mostly finalized the database design, input format and the class design.<br>The design details can be seen here: <a href="https://github.com/pgRouting/pgrouting/wiki/TDSP-Details">https://github.com/pgRouting/pgrouting/wiki/TDSP-Details</a><br>
* According to new plan, we are not using Boost Priority Queues for heap operations during dijkstra search.<br><br>Instead, I have implemented a binary heap that will provide the functionality.<br>I have also coded the data structures that would be required for the core - time dependent dijkstra implementation.<br>
The initial working draft of algorithm is also ready. <br>Please find the source at: <a href="https://github.com/pgRouting/pgrouting/blob/gsoc-tdsp/extra/tdsp/tdsp_core.cpp">https://github.com/pgRouting/pgrouting/blob/gsoc-tdsp/extra/tdsp/tdsp_core.cpp</a><br>
It needs to be tested for different test cases.<br>Also, there could be ways which could optimise the implementation (space complexity / time complexity)<br>Any such ideas are welcome.<br><br>Blocking Issues:<br><br>Acquiring real world time-dependent data is a big hurdle, since as far as we know till date, it is not freely available.<br>
We are looking at other options so that algorithm can be tested on actual data.<br><br>Next week goals:<br>Continue to work on the core algorithm, and test it for different dummy test cases which for now will need to be generated.<br>
Find out bugs and work them out.<br><br>Any comments / suggestions are welcome.<br clear="all"><br>-- <br>Regards,<br>-Jay Mahadeokar<br><br>