[pgrouting-dev] Re: Implementation of core Time Dependent
Dijkstra function
Jay Mahadeokar
jai.mahadeokar at gmail.com
Mon May 30 19:43:02 EDT 2011
Hi,
Just a quick update -
I have fixed a few bugs that were there in the initial draft.
I have also 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:
https://github.com/pgRouting/pgrouting/tree/gsoc-tdsp
Please review and comment.
I believe there are many parts which need optimisation, like binary_heap
reduce_key() function, as well as weight_map.get_travel_time() function.
Also, the actual time-dependent functionality i.e multiple time windows
needs to be tested for large graphs, but there is no way to verify if the
result returned is true. Any suggestions on this?
Regards,
On Thu, May 26, 2011 at 4:58 AM, Jay Mahadeokar <jai.mahadeokar at gmail.com>wrote:
> 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
>
>
--
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110531/71a36019/attachment-0001.html
More information about the pgrouting-dev
mailing list