[pgrouting-dev] Re: Implementation of core Time Dependent
Dijkstra function
Jay Mahadeokar
jai.mahadeokar at gmail.com
Wed May 25 19:27:04 EDT 2011
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110526/66ab58dc/attachment-0001.html
More information about the pgrouting-dev
mailing list