[pgrouting-dev] Re: Implementation of core Time Dependent
Dijkstra function
Jay Mahadeokar
jai.mahadeokar at gmail.com
Wed May 25 19:28:45 EDT 2011
Sorry, forgot to give the URL to the git-hub repository.
I have pushed into the main pgRouting repository into the gsoc-tdsp branch.
On Thu, May 26, 2011 at 4:57 AM, Jay Mahadeokar <jai.mahadeokar at gmail.com>wrote:
> Hi,
>
> I have coded a initial draft of the core tdsp algorithm. I have implemented
> a binary heap for doing delete_min() and decrease_key() to guide the
> dijkstra search.
>
> Also, used many data structures like weight_map - for storing time
> dependent edge traversal times
> edge_wrapper - for mapping edge ids with source and target vertex.
> For graph, I have used boost adjecency list - since it helps in fast lookup
> of out-edges in any node during dijkstra search.
> The distance map and predecessor map are types of std::map.
>
> I have tested on a small dummy graph. The graph is currently read from a
> file. Format:
> *Graph Input convension:*
> Line1 contains 3 integers: V E R -V is no of vertices, E - edges and R -
> the discrete range of values.
> Next V lines have following format:
> Start with integer e denoting number of edges going out from that vertex.
> And next e values in same
> line tell the target vertex of edge.
>
> Next we have E*R lines each conaining 3 integers eid , start_time,
> travel_time. These are used to generate
> weight map.
>
> Last line contains source id.
> The distance_map and predecessor_map are printed.
>
> You can find the code in /extra/tdsp/ folder. Test graph is in
> /extra/tdsp/test_data folder.
>
> To test, you can go to tdsp folder and do:
> g++ -Wno-deprecated tdsp_core.cpp
> ./a.out < ./test_data/graph1.dat
>
> *TODO:*
> There will be many ways to optimize this code. I will list the possible
> improvements soon.
> Organise the code into header files etc.
> Test for larger input graphs. Create test cases that cover all scenarios.
>
> Thoughts / suggestions?
>
>
> On Wed, May 25, 2011 at 9:28 AM, Jay Mahadeokar <jai.mahadeokar at gmail.com>wrote:
>
>>
>>
>> On Wed, May 25, 2011 at 8:47 AM, Stephen Woodbridge <
>> woodbri at swoodbridge.com> wrote:
>>
>>> On 5/24/2011 7:06 PM, Jay Mahadeokar wrote:
>>>
>>>>
>>>>
>>>> On Mon, May 23, 2011 at 8:03 PM, Stephen Woodbridge
>>>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>>>>
>>>> I'm not a C++ programmer, but from what I have read on the boost
>>>> list, it seems that the path to writing generic templates is to
>>>> write the code first in regular C++ so it works and then refactor it
>>>> to be more generic. So step 1 is to do as you proposed.
>>>>
>>>> Also since this project is to implement a "time dependent dijkstra
>>>> algorithm" in pgRouting, the generic templates seems to be out of
>>>> scope. It would be fine to do if you had the time and skill, but I
>>>> think your approach makes sense, use the tools that make your job
>>>> easier and allow you to achieve success.
>>>>
>>>> Any contrary opinions to this?
>>>>
>>>> -Steve
>>>>
>>>>
>>>> On 5/23/2011 10:20 AM, Jay Mahadeokar wrote:
>>>>
>>>> Hi,
>>>>
>>>> As initially discussed, I was trying to reuse the boost's
>>>> dijkstra code
>>>> to write the core time dependent dijkstra algorithm.
>>>> Since Boost makes extensive use of generic programming, and I
>>>> have no
>>>> prior experience with such deep generic programming concepts, I
>>>> was
>>>> wondering if we really need all these features that boost
>>>> provides.
>>>>
>>>> Another option would be to write the time-dependent dijkstra on
>>>> our own.
>>>>
>>>> This will be a light-weight code without extensive use of generic
>>>> programming like boost.
>>>> So, i was thinking of using following:
>>>>
>>>> *1. *Boost::AdjecencyList - for storing graph.
>>>> *2. *Std::Map - for storing distanceMap, predecessorMap.
>>>>
>>>> *3. *For weightMap:
>>>>
>>>> typedef struct weight_map_element
>>>> {
>>>> pair<int,double> edge;
>>>> double travel_time;
>>>> }
>>>> weight_map_element_t;
>>>>
>>>> class weight_map
>>>> {
>>>>
>>>> vector<weight_map_element_t> weight_map_set;
>>>>
>>>> public:
>>>> void insert(weight_map_element_t element);
>>>> double get_travel_time(int edge_id, double start_time);
>>>>
>>>> };
>>>>
>>>>
>>>> *4. *std::priority_queue for the priority queue that will be
>>>> used for
>>>> dijkstra search.
>>>>
>>>>
>>>> Well,
>>>> The std::prority_queue does not support the decrease_key operation which
>>>> will be needed for the dijkstra search. I dont think stl provides a heap
>>>> data structure with decrease_key, delete_min and insert operations.
>>>>
>>>> The make_heap, and sort_heap would be too costly to maintain for
>>>> dijkstra.
>>>>
>>>> Do you have any idea of open-source library that provides the heap
>>>> datastructure with above functionality?
>>>>
>>>> I am thinking of implementing binary heap myself to support the required
>>>> functionality.
>>>> Thoughts?
>>>>
>>>
>>> Jay,
>>>
>>> What about looking at the code in Booost Graph that does this. There is
>>> probably some generic template code, but maybe you can just reuse the
>>> algorithms and recode your own specific to this problem implementation.
>>>
>>>
>>> Ashraf,
>>>
>>> You implemented your own Dijkstra algorithm in OpenGraphRouter, can you
>>> point Jay to your code there so that he can assess reusing some of that fore
>>> this project. I think the following might do the trick
>>>
>>> http://sourceforge.net/projects/opengraphrouter/
>>>
>>> Look here at ShortestPathDikjstra.cpp, it looks like Ashraf is using a
>>> Boost Mutable Queue:
>>>
>>> http://opengraphrouter.svn.sourceforge.net/viewvc/opengraphrouter/tags/Newstructure/tags/gsoc2009/src/?pathrev=111
>>>
>>>
>>>
>>
>> Thanks Steve for the suggestion. I actually implemented a BinaryHeap class
>> for exact requirements, and it seems to be solving the purpose.
>>
>> The basic functions in class are:
>>
>>
>> class binary_heap
>> {
>> vector<Vertex> heap;
>>
>> void heapify(int index);
>>
>> public:
>>
>> void insert(Vertex v); //inserts v into heap and rebalances it so
>> that heap property is maintained.
>> double decrease_key(int index, double delta); // Decreases key of
>> vertex with id = index, by delta.
>> Vertex delete_min(); //deletes the min key vertex and rebalances
>> heap.
>>
>> };
>>
>> Note that in binary heap all above operations need O(log n) time.
>>
>> I will complete the initial draft of the algorithm soon and update it on
>> github in next few days.
>> We can see what else is needed then.
>>
>> -Steve
>>>
>>> Will this be sufficient for our implementation? If yes, I will
>>>> come up
>>>> with the detailed internal function prototypes soon.
>>>>
>>>>
>>>> On Wed, May 18, 2011 at 8:09 PM, Stephen Woodbridge
>>>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>
>>>> <mailto:woodbri at swoodbridge.com
>>>> <mailto:woodbri at swoodbridge.com>>> wrote:
>>>>
>>>> On 5/18/2011 8:08 AM, Jay Mahadeokar wrote:
>>>>
>>>> Hi,
>>>>
>>>> I think what we need is a function on following lines:
>>>>
>>>> Given a query_start_time, it should query the
>>>> TimeDepCosts
>>>> table, and
>>>> return the set of entries which have their start_time
>>>> within
>>>> query_start_time + delta. This delta might be x hours,
>>>> depending
>>>> on the
>>>> upper bound of the expected journey time.
>>>>
>>>> We need following things handled in our model:
>>>>
>>>> If query_start_time is 11PM Sunday and delta is 10 hours,
>>>> we
>>>> will need
>>>> to query entries with start time between 11PM Sunday and
>>>> 9AM
>>>> Monday. So,
>>>> basically the function needs to be periodic in terms of
>>>> time_of_day and
>>>> day_of_week.
>>>>
>>>> As Steve suggested, we can maintain conventions for
>>>> day_of_week
>>>> like:
>>>>
>>>> -3 - holidays
>>>> -2 - weekend days
>>>> -1 - week days
>>>> 0 - all days
>>>> 1-7 Mon - Sun.
>>>>
>>>> If we just assume entries for -3,-2,-1,0 and ignore each
>>>> entry
>>>> for Sun -
>>>> Sat, that would reduce the space required assuming that
>>>> the
>>>> entries for
>>>> weekdays is same. If times for different weekdays is
>>>> different
>>>> then we
>>>> would have separate entries for each day.
>>>>
>>>> So, the query should properly examine the
>>>> query_day_of_week and
>>>> select
>>>> the proper entries. Ex: For above query, if it is
>>>> sunday, then after
>>>> 12AM, next entries will be queried with time_of_day as
>>>> -1, but
>>>> if it was
>>>> Saturday, next entries will be queried with time_of_day
>>>> as -2.
>>>>
>>>> We can have a boolean parameter like *isHoliday* in query
>>>> itself, which
>>>> will tell if a given day (may be weekday) is holiday or
>>>> not.Then
>>>> again
>>>> the query will have to be modified accordingly (query
>>>> for -3).
>>>> This will
>>>> take care of query for local holiday etc and we do not
>>>> have to worry
>>>> about calenders. The user will have to worry about
>>>> that.. :-)
>>>>
>>>>
>>>> This (isHoliday) might work for a single day, but will not
>>>> work if
>>>> the query crosses into the next day(s). Holidays are an input
>>>> convenience to describe recurring events. So say we have a
>>>> convenient way to input that data and store it into tables as
>>>> we
>>>> have described, then the query for costs would need to
>>>> decide is a
>>>> given day is a holiday or not and then select the correct
>>>> entries to
>>>> return based on that. For ease of implementation, we could
>>>> just
>>>> start with a stub function the returns false and later
>>>> implement a
>>>> table lookup based on the date or day of year that determines
>>>> if
>>>> isHoliday=t/f for any given start_time+offset.
>>>>
>>>> Then when querying schedules, for example, we would select
>>>> holiday
>>>> schedules if they exist and its a holiday otherwise search
>>>> the
>>>> regular tables.
>>>>
>>>>
>>>> There can be time_from and time_to entries as well. But,
>>>> if we
>>>> just have
>>>> entries like:
>>>>
>>>> day_of_week: -1, time_of_day: 00:01, 55mph
>>>> day_of_week: -1, time_of_day: 07:00, 30mph
>>>> day_of_week: -1, time_of_day: 10:01, 55mph
>>>> day_of_week: -1, time_of_day: 16:31, 30mph
>>>>
>>>> we can assume that the entry with time_of_day 00:01 is
>>>> valid upto
>>>> 07:00. And if query_start_time is 02:00 and delta is 10
>>>> hours,
>>>> we can
>>>> query entries which have time_of_day < query_start_time
>>>> + delta
>>>> (taking
>>>> care of change of day).
>>>>
>>>> Is this assumption reasonable?
>>>>
>>>>
>>>> This sounds reasonable if the response is in units of time
>>>> (offset)
>>>> from query_start_time. Assuming we use a resolution of
>>>> seconds, then
>>>> the response would be in seconds from start time.
>>>>
>>>> *weightMap Abstraction*
>>>>
>>>>
>>>> I think the design would be more modular if we keep the
>>>> weightMap
>>>> independent of the underlying time conventions. Since as
>>>> Daniel
>>>> pointed
>>>> out, this algorithm can also be used for non-road
>>>> networks.
>>>>
>>>> So, whatever the underlying time conventions, we can
>>>> assume that
>>>> in the
>>>> end the query should return pairs like:
>>>>
>>>> < <edgeId, offset_time> , travel_time/speed >
>>>>
>>>> We will assume that query_start_time is 0, i.e we offset
>>>> every
>>>> thing by
>>>> query_start_time.
>>>> The offset_time will be as follows:
>>>>
>>>> As in above example,
>>>> If start_tme is 02:00 and day_of_week is -1, and delta
>>>> as 10 hours.
>>>>
>>>> Then, edge entries for edgeId 1 will be:
>>>> < <1, 05:00 > , 30 mph>
>>>> < <1, 08:01 > , 55 mph>
>>>> < <1, 14:31 > , 30 mph>
>>>>
>>>> Basically, the offset_time will abstract out any
>>>> internal details of
>>>> weekdays, change of days etc and it will just contain
>>>> the offset
>>>> from
>>>> start_time.
>>>>
>>>>
>>>> I suggested seconds above, but if someone is modeling events
>>>> in say
>>>> glacier flow, geological times or the big bang, they might
>>>> need
>>>> other units of time. I would say that because we are talking
>>>> about
>>>> time based schedules and need to deal with days, hours
>>>> minutes we
>>>> should probably not worry about these other timeframes as
>>>> the solver
>>>> will be offset based it will work with any units and then
>>>> only the
>>>> wrappers for extracting the costs from the schedules would
>>>> need to
>>>> change to deal with other timeframes. So lets not get hung up
>>>> on
>>>> this, I think this is a sound plan.
>>>>
>>>> -Steve
>>>>
>>>> This will greatly simplify the core time dependent
>>>> dijkstra
>>>> implementation.
>>>>
>>>> Thoughts?
>>>>
>>>> On Wed, May 18, 2011 at 10:46 AM, Stephen Woodbridge
>>>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>
>>>> <mailto:woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com
>>>> >>
>>>> <mailto:woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>
>>>>
>>>> <mailto:woodbri at swoodbridge.com
>>>> <mailto:woodbri at swoodbridge.com>>>> wrote:
>>>>
>>>> Hi Daniel,
>>>>
>>>> These are good points.
>>>>
>>>> I agree that turn restrictions should be thought
>>>> about but only
>>>> implemented if there is time. I think we should take
>>>> the
>>>> discussion
>>>> of turn restriction into a separate thread. I'm
>>>> interested
>>>> in what
>>>> you think is a limitation that can't be modeled in
>>>> Dijkstra
>>>> or A*.
>>>>
>>>> Regarding the time modeling, my point was just that
>>>> we
>>>> needed more
>>>> thought there and a richer model developed. The
>>>> crontab
>>>> model is a
>>>> good idea. I'm not opposed to modeling monthly or
>>>> yearly
>>>> events, but
>>>> they rarely exist other than holidays which I tried
>>>> to
>>>> capture. I
>>>> suppose you could model something like the Boston
>>>> Marathon
>>>> and model
>>>> all the road closures and restrictions, but it seems
>>>> to be a
>>>> lot of
>>>> work for a one day event, but I can see city
>>>> government's
>>>> deploying
>>>> the resources to model something like this.
>>>>
>>>> Regarding timezones: Times need to be entered with
>>>> zones for
>>>> models
>>>> that cross zones but all the data should be
>>>> converted to UTC
>>>> internally so it runs in a consistent time model.
>>>> Timezones
>>>> are for
>>>> input and output, but the solver should be ignorant
>>>> of them,
>>>> in my
>>>> opinion.
>>>>
>>>> I have carried my GPS from the Eastern to central
>>>> time zone,
>>>> and it
>>>> knew the local time when I powered it up. So my
>>>> guess is that it
>>>> would auto correct when crossing the time zone.
>>>>
>>>> -Steve
>>>>
>>>>
>>>> On 5/17/2011 10:42 PM, Daniel Kastl wrote:
>>>>
>>>> Hi Jay and Steve,
>>>>
>>>> This looks really nice, but let me give some
>>>> comments
>>>> regarding
>>>> how to
>>>> model time, because this is really tricky in my
>>>> opinion.
>>>> Especially when
>>>> thinking about an abstract network that isn't a
>>>> road
>>>> network.
>>>>
>>>>
>>>>
>>>> Would it be possible to support turn
>>>> restrictions in
>>>> the static
>>>> Dijkstra also? I'm thinking just use all the
>>>> same
>>>> structures but
>>>> ignore the the time components to keep things
>>>> simple. So if
>>>> the the
>>>> turn restrictions table is present we use
>>>> it, otherwise
>>>> assume no
>>>> restrictions. If doing static shortest path
>>>> with turn
>>>> restrictions
>>>> then ignore the time components otherwise we
>>>> use
>>>> them. And
>>>> it is up
>>>> to the user to make sure the turn
>>>> restriction table
>>>> is valid
>>>> for the
>>>> analysis being requested.
>>>>
>>>>
>>>> Currently in pgRouting Dijkstra and A* don't
>>>> support turn
>>>> restrictions
>>>> modelling. What I actually like on Shooting Star
>>>> is, that it
>>>> routes from
>>>> edge to edge instead of node to node. So it
>>>> allows to model
>>>> relations
>>>> between edges rather than nodes, which I think
>>>> is more
>>>> close to how
>>>> humans would think of this.
>>>> Dijkstra can only visit one node one times (as
>>>> Shooting star
>>>> only visits
>>>> an edge once). Well, there can be turn
>>>> restriction cases
>>>> where a
>>>> node is
>>>> passed twice and which can't be done correctly
>>>> with
>>>> Dijkstra as
>>>> far as I
>>>> know.
>>>>
>>>> In the beginning I wouldn't think about the turn
>>>> restrictions
>>>> too much.
>>>> Let's take it as an extra when we see we still
>>>> have
>>>> enough time.
>>>> Of course if you have a good idea to implement
>>>> it all at
>>>> once
>>>> with only
>>>> little extra work, then that's fine.
>>>>
>>>>
>>>> For time definitions in your tables I think
>>>> you need
>>>> to probably
>>>> define some common structure for handling a
>>>> time entry.
>>>>
>>>>
>>>> Another problem might be time zones. Plain day
>>>> field + time
>>>> field might
>>>> not be able to allow driving from one time zone
>>>> to
>>>> another (or just
>>>> think about a flight network). I never went from
>>>> one
>>>> timezone to
>>>> another
>>>> by car or train, but Steve and Anton, you might
>>>> have this
>>>> experience.
>>>> How does car navigation software handle this
>>>> when you
>>>> cross the
>>>> timezone
>>>> border? ;-)
>>>>
>>>> So taking "timestamp with timezone" for those
>>>> fields
>>>> might be a good
>>>> idea to be able to support such a functionality.
>>>>
>>>>
>>>> For example time_from and time_to might need
>>>> to be
>>>> defined as a
>>>> structure that includes day_of_week. day_of
>>>> week
>>>> might take
>>>> values like:
>>>>
>>>> -3 - holidays
>>>> -2 - weekend days
>>>> -1 - week days
>>>> 0 - all days
>>>> 1..7 - Sun,...,Sat
>>>>
>>>>
>>>> I think the problem here is how to model
>>>> recurring time
>>>> dependent costs,
>>>> right?
>>>> If you think about weekdays, then you can't for
>>>> example
>>>> model
>>>> monthly or
>>>> yearly events.
>>>>
>>>> I'm not really sure this is useful information
>>>> here, but
>>>> I once saw
>>>> about how the "iCal" format models recurring
>>>> calendar
>>>> events:
>>>>
>>>> http://ext.ensible.com/deploy/dev/examples/calendar/recurrence-widget.html
>>>>
>>>> Maybe we can learn something from there. The
>>>> example
>>>> needed to be
>>>> extended with some duration probably. But
>>>> looking about
>>>> calendar
>>>> formats
>>>> might be a good idea to model holidays etc.
>>>>
>>>> Or another (stupid) example would be cron job
>>>> syntax.
>>>> Something
>>>> I always
>>>> need to google for as I can't remember it ;-)
>>>>
>>>> All this time dependent stuff, events and
>>>> schedules is
>>>> also an
>>>> issue in
>>>> Darp solver.
>>>> And it probably is important also for the
>>>> multi-modal
>>>> routing,
>>>> so if we
>>>> can find some clever way how to model this and
>>>> can share
>>>> it between
>>>> algorihtms, that would be great.
>>>>
>>>> Daniel
>>>>
>>>> _______________________________________________
>>> pgrouting-dev mailing list
>>> pgrouting-dev at lists.osgeo.org
>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>>
>>
>>
>>
>> --
>> Regards,
>> -Jay Mahadeokar
>>
>>
>
>
> --
> Regards,
> -Jay Mahadeokar
>
>
--
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110526/5f845633/attachment-0001.html
More information about the pgrouting-dev
mailing list