[Soc] TDSP implementation for pgRouting Weekly Report

Fri Aug 5 17:52:39 EDT 2011

Hi,

Weekly Report #10
Date - 5th Aug 2011

Current Progress.
-------------------------------------------------------------------------------------------------------------------------------------------------------
After much brain-storming in the community, we decided that the proposed
cyclic data optimization was a little bit premature, and we would just focus
on completion of the basic algorithm as proposed in the GSoc proposal during
the GSoc timeline.

So, the major function will be pgr_time_dependent_shortest_path.
For cyclic data, we will have function like: pgr_tdsp_cyclic. The weight_map
class has been modified for that, but the default constructor keeps the
behaviour non-cyclic for now. We will keep brainstorming until the
requirements and idea of cyclic data are properly identified and defined and
then provide support for the optimization.

In the mean time I also cleaned up the code and continued testing.

Next week goals.
------------------------------------------------------------------------------------------------------------------------------------------------------
Try and finish up the documentation work needed for tdsp. Including examples
to convert some common data formats to tdsp and potential plsql scripts for
the same.

Since the major portion of GSoc proposal is completed,I also plan to work on
all-pairs shortest path implementation for pgRouting(not part of the GSoc
proposal, I had worked on it earlier), and I will try and finish it up and
document it within GSoc timeline as planned earlier with my mentor if time
permits.

On Sat, Jul 30, 2011 at 8:58 PM, Jay Mahadeokar <jai.mahadeokar at gmail.com>wrote:

> Hi,
>
> Weekly Report #9
> Date - 30th July 2011
>
> Current Progress
>
> -------------------------------------------------------------------------------------------------------------------------------------------------------
> The major implementation part is done now and is working well.
> I did some testing and removed one bug.
>
> Also I looked at ways to optimise the code, and found a way that could
> improve the space complexity by a big way in queries that span large time
> intervals especially for cyclic data.
>
> For design details refer [1].
> Currently, if the time-interval is suppose 24, (24 hours) and the travel
> time expected is around 60 hours, then the tdsp-wrapper query retrieves
> total 60 intervals and the data is repeated for the 24 hour intervals.
>
> This is unnecessary space wastage. So, I edited the weight_map class to
> accommodate a variables is_cyclic and the cycle_interval, which will keep
> track of the cyclic nature of the data. So, actually only the 24 hour data
> will be fed to weight map and then it will be reused in cycles.
>
> Because of the good design, I guess this has scaled up really nice and
> there is no need to modify actual core tdsp. Just the weight_map's
> get_travel_time() function and the wrapper plsql function needed to be
> altered.
>
> I also discussed the intricacies of integrating this with the various
> possible data formats and the core algorithm in the community and for now
> the idea seems to be clear.
>
> The tdsp query must have an additional parameter - is_cyclic which should
> be used to set the is_cyclic flag of the weight_map.
>
> Now, if data is cyclic, then the plsql function that retrieves the data
> should be written in such a way that if interval is suppose 0 - 24, and
> start time is 21, then  21->0 and 20->23. After that the cyclic flag will
> indicate us to loop again.  The plsql function will be generally written by
> app developer and he should take care of this. (I have already implemented
> this in my code.)
>
> If data is cyclic, he should pass the flag appropriately. If is_cyclic is
> false, we can assume that if intervals are exhausted, we will keep using
> time corresponding to last interval.
>
> For more details of the discussion please refer [2]
>
> Next week target
>
> ---------------------------------------------------------------------------------------------------------------------------------------------------------------------
> Complete the above optimisation and modify the original tdsp query as
> discussed above.
>
> [1] https://github.com/pgRouting/pgrouting/wiki/TDSP-Details
>  [2] http://lists.osgeo.org/pipermail/pgrouting-dev/2011-July/000386.html
>
>
> On Fri, Jul 22, 2011 at 8:44 PM, Jay Mahadeokar <jai.mahadeokar at gmail.com>wrote:
>
>> Hi,
>>
>> Weekly Report #8
>> Date - 22nd July 2011
>>
>> Current Progress
>>
>> --------------------------------------------------------------------------------------------------------------------------------------------
>> Last week we discussed what data wrappers will be needed for retrieving
>> time dependent data into format expected by the tdsp function. The tdsp
>> function expects time dependent data with start time as 0 and everything
>> offset from start time. So, for different data formats wrapper functionality
>> will be needed which will convert the data into above format taking care of
>> cyclic nature of data etc [1].
>>
>> We finally decided that wrapper functions in form of plsql arguments will
>> be best way to implement the above functionality. So, I have learned and
>> written corresponding plsql function for the time dependent data format
>> which was used for testing the core tdsp function. The code is updated in
>> the gsoc-tdsp branch [2].
>>
>> I have also modified the tdsp.h, tdsp.c and weight_map.hpp files so that
>> the end_times are also taken care of, which I had missed in earlier code.
>>
>> Next Weeks Goals
>>
>> ---------------------------------------------------------------------------------------------------------------------------------------------
>> Discuss the most common data formats that may be used with the community
>> and write plsql wrapper functions for them.
>> Keep testing the core algorithm with more varied data.
>> Start looking at the documentation that must be done.
>>
>> [1] http://lists.osgeo.org/pipermail/pgrouting-dev/2011-July/000371.html
>> [2]
>> https://github.com/pgRouting/pgrouting/blob/gsoc-tdsp/extra/tdsp/sql/tdsp_data_wrappers.sql
>>
>>
>> On Fri, Jul 15, 2011 at 5:55 PM, Jay Mahadeokar <jai.mahadeokar at gmail.com
>> > wrote:
>>
>>> 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
>>>
>>>
>>
>>
>> --
>> Regards,
>> -Jay Mahadeokar
>>
>>
>
>
> --
> Regards,
> -Jay Mahadeokar
>
>

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