[pgrouting-dev] Re: Implementation of core Time Dependent Dijkstra
function
Stephen Woodbridge
woodbri at swoodbridge.com
Mon May 30 21:55:15 EDT 2011
On 5/30/2011 7:43 PM, Jay Mahadeokar wrote:
> 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).
Yup, this sounds reasonable.
> 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?
So what I am thinking is something like building an graph like:
A----B----C-----D----E----etc
So A is the source and etc is the target, but there are multiple edges
between each pair of adjacent nodes where each edges is accessed via a
different time window. So you can verify that the appropriate time
window is accessed by the edge it selects. It should be pretty easy to
verify that the correct path was selected because there would be a
unique path of edges based on the time windows.
If this works then you could also expand the graph by adding other
random segments and windows as long as they did not generate another
valid path that was shorter between the expected path nodes.
Do you think something like this will work for testing?
-Steve
> Regards,
>
> On Thu, May 26, 2011 at 4:58 AM, Jay Mahadeokar
> <jai.mahadeokar at gmail.com <mailto: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 <mailto: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 <mailto:jai.mahadeokar at gmail.com>> wrote:
>
>
>
> On Wed, May 25, 2011 at 8:47 AM, Stephen Woodbridge
> <woodbri at swoodbridge.com <mailto: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>
> <mailto: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>>
> <mailto: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>>>
> <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
> <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
> <mailto: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
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
More information about the pgrouting-dev
mailing list