[Soc] TDSP implementation for pgRouting Weekly Report

Jay Mahadeokar jai.mahadeokar at gmail.com
Fri Jul 15 08:25:02 EDT 2011 

Hi,

Weekly Report #7
Date - 15th July 2011

Current Progress
------------------------------------------------------------------------------------------------------------------------------------------
Last week I analysed the tasks done and things that need to be done.
Discussed the same with my mentor.
Also polished the code and documentation already done.

Next weeks goals
------------------------------------------------------------------------------------------------------------------------------------------
Come up with more relevant data and test cases that will test the algorithm
implementation thoroughly.

Regards,

On Fri, Jul 8, 2011 at 8:00 PM, Jay Mahadeokar <jai.mahadeokar at gmail.com>wrote:

> Hi,
>
> Weekly Report #6
> Date - 8th July 2011
>
> According to project plan
>
> ----------------------------------------------------------------------------------------------------------------------------------------
> July 7th
> Implement the basic tdsp query and test it using test data.
>
> Current Progress:
>
> ----------------------------------------------------------------------------------------------------------------------------------------
>
> I have coded the functions to retrieve data from time_dep_costs table and
> it is presented to the core tdsp algorithm along with the data from ways
> table. The query seems to be working nicely for now.
>
> I have documented the design details [1] and written an example tutorial
> [2] to try out the time_dependent_shortest_path algorithm. I guess this is
> enough to show the functionality, although, the data and examples along with
> the wrapper functions need to be worked on in next few weeks.
>
> Any feedback/corrections are welcome.
>
>
> [1] https://github.com/pgRouting/pgrouting/wiki/TDSP-Details
> [2] https://github.com/pgRouting/pgrouting/wiki/TDSP-Tutorial-and-Example
>
>
>
> On Fri, Jul 1, 2011 at 2:28 PM, Jay Mahadeokar <jai.mahadeokar at gmail.com>wrote:
>
>> Hi,
>>
>> Weekly Report #5
>> Date - 1st July 2011
>>
>> According to project plan [1]
>>
>> ----------------------------------------------------------------------------------------------------------------------------------
>>  July 5th
>> Implement queries needed for edge data and time dependent data from
>> database.
>> Integrate the core algorithm and all components with CMAKE scripts.
>>
>> Current progress
>>
>> ----------------------------------------------------------------------------------------------------------------------------------
>> The core time dependent function was ready, and the postgresql query with
>> static time data was working last week,
>>
>> I wrote c functions that will extract the attributes of the time dependent
>> cost table, and then accordingly extract the corresponding tuples into array
>> of weightMap elements. These are then presented to the core tdsp function
>> along with edges array. The tuples are correctly extracted as of now. But,
>> there is some problem when the core function is called. I will try and
>> resolve the issues next week.
>>
>> [1]
>> https://github.com/pgRouting/pgrouting/wiki/TDSP-Tentative-Project-Plan
>>
>> On Fri, Jun 24, 2011 at 6:47 AM, Jay Mahadeokar <jai.mahadeokar at gmail.com
>> > wrote:
>>
>>> Hi,
>>>
>>> Weekly Report #5:
>>> Date - 24th June 2011
>>>
>>>
>>> According to project plan [2]
>>>
>>> -----------------------------------------------------------------------------------------------------------------------------------------
>>>
>>> June 25th
>>> Implement modules needed for retrieving the time-dependent costs.
>>> July 5th
>>> Implement queries needed for edge data and time dependent data from
>>> database.
>>> Integrate the core algorithm and all components with CMAKE scripts.
>>>
>>> Current Progress
>>>
>>> -----------------------------------------------------------------------------------------------------------------------------------------
>>> I have corrected the bug which was resulting in wrong results for
>>> non-integer data in core tdsp algorithm. Apparently there was a problem in
>>> the binary_heap implementation, but now it seems to be working fine.
>>>
>>>  I have juggled the ordering of the tasks a bit. I implemented the
>>> queries for retrieving the edge data from database, and also wrote the
>>> postgres C procedure that extracts the data from ways table, generates the
>>> boost graph and presents it to the time dependent algorithm. The weight map
>>> is generated such that cost is same for all times, which is the case for
>>> static data and that is also fed to the core algorithm. The query returns
>>> set of path results and the results are exactly matching with the pgRouting
>>> shortest_path() query.  Please find the updated code in gsoc-tdsp branch of
>>> pgRouting github repository [1].
>>>
>>> Next weeks goals:
>>>
>>> -----------------------------------------------------------------------------------------------------------------------------------------
>>> The next step will now be to implement modules for retrieving the data
>>> from time_dep_costs table and generate the time dependent weight map which
>>> will be fed to the core algo instead of the static one.
>>>
>>> [1] https://github.com/pgRouting/pgrouting/tree/gsoc-tdsp
>>>
>>> [2]
>>> https://github.com/pgRouting/pgrouting/wiki/TDSP-Tentative-Project-Plan
>>>
>>> On Sat, Jun 18, 2011 at 7:48 AM, Jay Mahadeokar <
>>> jai.mahadeokar at gmail.com> wrote:
>>>
>>>> Hi,
>>>>
>>>> Weekly Report #4:
>>>> Date - 18th June 2011
>>>>
>>>>
>>>> According to project plan [2]
>>>>
>>>> -----------------------------------------------------------------------------------------------------------------------------------------
>>>>  Finish the design of project, and the core-time dependent shortest path
>>>> implementation and test the code with dummy data till 15 June.
>>>> Implement modules needed for retrieving the time-dependent costs till
>>>> June 25th.
>>>>
>>>
>>>>
>>>>
>>>> ------------------------------------------------------------------------------------------------------------------------------------------
>>>> Current Progress:
>>>>
>>>> Implementation of core-time dependent dijkstra has been done.
>>>> I have run across a bug when dealing with non-integer time-dependent
>>>> data, I am working on it.
>>>> I discussed ways of generating the time-dependent data in pgrouting dev
>>>> list [1].
>>>> Accordingly  have written plpgsql function that generates test data [3].
>>>> Many modifications and test instances can be generated as discussed in
>>>> [1].
>>>>
>>>>
>>>> ------------------------------------------------------------------------------------------------------------------------------------
>>>> Next week goals:
>>>> Fix the bug in dealing with non-integer data.
>>>> Start working on writing function that will retrieve time-dependent data
>>>> from database.
>>>> Also start working main tdsp-plsql function(the actual query that will
>>>> be exposed).
>>>>
>>>> [1]
>>>> http://lists.osgeo.org/pipermail/pgrouting-dev/2011-June/000300.html
>>>>
>>>> [2]
>>>> https://github.com/pgRouting/pgrouting/wiki/TDSP-Tentative-Project-Plan
>>>>  [3]
>>>> https://github.com/pgRouting/pgrouting/blob/gsoc-tdsp/extra/tdsp/sql/data_generate_tdsp.sql
>>>>
>>>>
>>>>
>>>> On Fri, Jun 10, 2011 at 10:58 PM, Jay Mahadeokar <
>>>> jai.mahadeokar at gmail.com> wrote:
>>>>
>>>>> Hi,
>>>>>
>>>>> Weekly Report #3:  (Also available at [1])
>>>>> Date - 10th June 2011
>>>>>
>>>>> According to project plan [2]:
>>>>>
>>>>>
>>>>> -----------------------------------------------------------------------------------------------------------------------------------------
>>>>> Finish the design of project, and the core-time dependent shortest path
>>>>> implementation and test the code with dummy data till 15 June.
>>>>>
>>>>>
>>>>> Current Progress:
>>>>>
>>>>> ------------------------------------------------------------------------------------------------------------------------------------------
>>>>>  I had coded and tested the core-tdsp algorithm such that it returns
>>>>> the distance-map and predecessor-map for given source.
>>>>> This week I wrote a wrapper function which does the following task:
>>>>> - Takes edges, weight_map_elements, source and target vertices as
>>>>> parameters.
>>>>> - Generates boost adjacency graph, weight_map and passes it to the
>>>>> tdsp_core function.
>>>>> - tdsp_core returns the distance_map and predecessor_map corresponding
>>>>> to source.
>>>>> - The wrapper function now generates the path from source to
>>>>> destination, and returns path_elements as result.
>>>>>
>>>>>
>>>>> I tested this for different source-destination pairs and it seems to be
>>>>> working for now. Bugs need to be discovered with more
>>>>> rigorous testing and fixed in coming weeks.
>>>>>
>>>>>
>>>>>
>>>>> ------------------------------------------------------------------------------------------------------------------------------------
>>>>> Next week goals:
>>>>> Finalize the prototype for the postgreSQL query for tdsp.
>>>>> How to formulate the query for retrieving data from the
>>>>> timeDependentCost table (used to generate the weight_map) is still under
>>>>> debate
>>>>> on pgRouting mailing list. We are considering various options like
>>>>> letting the user provide the query, or form the query ourselves
>>>>> and the pros and cons of both approaches.
>>>>>
>>>>> We hope to find a viable solution for the same asap and start working
>>>>> towards implementing the same.
>>>>>
>>>>> [1]
>>>>> https://github.com/jay-mahadeokar/GSoc-2011-Project-Docs/blob/master/weekly-reports/10-Jun-2011
>>>>> [2]
>>>>> https://github.com/pgRouting/pgrouting/wiki/TDSP-Tentative-Project-Plan
>>>>>
>>>>> Regards,
>>>>>
>>>>>
>>>>> On Fri, Jun 3, 2011 at 10:40 PM, Jay Mahadeokar <
>>>>> jai.mahadeokar at gmail.com> wrote:
>>>>>
>>>>>> Hi,
>>>>>>
>>>>>> Here is my weekly report #2. Also available at [1].
>>>>>> Date - 3rd June 2011
>>>>>>
>>>>>> According to tentative project plan [3]:
>>>>>>
>>>>>> -----------------------------------------------------------------------------------------------------------------------------------------
>>>>>> Finish the design of project, and the core-time dependent shortest
>>>>>> path implementation and test the code with dummy data till 15 June.
>>>>>>
>>>>>>
>>>>>> Current Progress:
>>>>>>
>>>>>> ------------------------------------------------------------------------------------------------------------------------------------------
>>>>>> I had implemented initial draft of the core time-dependent algorithm
>>>>>> in 1st week. I fixed a few bugs that were there in the initial draft.
>>>>>>
>>>>>> 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.
>>>>>> Also, 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 gsoc-tdsp branch: [2]. Please review, any
>>>>>> comments are welcome.
>>>>>>
>>>>>> Also, the actual time-dependent functionality i.e multiple time
>>>>>> windows needs to be tested for real world large graphs. To do this, we are
>>>>>> planning to generate time dependent data ourselves corresponding to the
>>>>>> static data available in pgRouting-workshop database, since such data is not
>>>>>> freely available as far as our knowledge.
>>>>>>
>>>>>> Some of the options for this data generation (according to discussions
>>>>>> in pgrouting-dev list)are:
>>>>>>
>>>>>> - Generate random data (That would take most extreme test cases into
>>>>>> account)
>>>>>> - If we think about "rush hour" around a major city, the highways
>>>>>> (based on road class) flowing into the city in the morning would get reduced
>>>>>> average speeds you could apply curve like average speed*percent based on 6am
>>>>>> (90%), 7am(75%), 8am(45%), 9am(50%), 10am(85%) and do something similar in
>>>>>> the evening rush. It might be too hard to figure on direction of flow in/out
>>>>>> bound so apply the curve to all traffic. The assumption is that the highways
>>>>>> are congested which will force traffic onto side streets. We can also reduce
>>>>>> the lower class speeds by say a constant 80% during rush hour.
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> ------------------------------------------------------------------------------------------------------------------------------------
>>>>>> Next week goals:
>>>>>>
>>>>>> * Generate the time-dependent data corresponding to the data in
>>>>>> pgRouting-workshop as planned above.
>>>>>> * Start working on writing postgreSQL C function that will call the
>>>>>> core-time dependent function.
>>>>>> * Keep testing the core function, find bugs if any, and fix them.
>>>>>>
>>>>>> [1]
>>>>>> https://github.com/pgRouting/pgrouting/wiki/Time-dependent---Dynamic-Shortest-Path
>>>>>> [2] https://github.com/pgRouting/pgrouting/tree/gsoc-tdsp
>>>>>> [3]
>>>>>> https://github.com/pgRouting/pgrouting/wiki/TDSP-Tentative-Project-Plan
>>>>>> --
>>>>>> Regards,
>>>>>> -Jay Mahadeokar
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> Regards,
>>>>> -Jay Mahadeokar
>>>>> II Year, MTech,
>>>>> CSE, IIT Kanpur.
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Regards,
>>>> -Jay Mahadeokar
>>>>
>>>>
>>>
>>>
>>> --
>>> Regards,
>>> -Jay Mahadeokar
>>>
>>>
>>
>>
>> --
>> Regards,
>> -Jay Mahadeokar
>>
>>
>
>
> --
> Regards,
> -Jay Mahadeokar
>
>


-- 
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/soc/attachments/20110715/437e59f9/attachment-0001.html

More information about the SoC mailing list