<br><br><div class="gmail_quote">On Wed, May 25, 2011 at 4:36 AM, Jay Mahadeokar <span dir="ltr"><<a href="mailto:jai.mahadeokar@gmail.com">jai.mahadeokar@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<br><br><div class="gmail_quote"><div><div></div><div class="h5">On Mon, May 23, 2011 at 8:03 PM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
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.<br>
<br>
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.<br>
<br>
Any contrary opinions to this?<br>
<br>
-Steve<div><br>
<br>
On 5/23/2011 10:20 AM, Jay Mahadeokar wrote:<br>
</div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Hi,<br>
<br><div><div></div><div>
As initially discussed, I was trying to reuse the boost's dijkstra code<br>
to write the core time dependent dijkstra algorithm.<br>
Since Boost makes extensive use of generic programming, and I have no<br>
prior experience with such deep generic programming concepts, I was<br>
wondering if we really need all these features that boost provides.<br>
<br>
Another option would be to write the time-dependent dijkstra on our own.<br>
<br>
This will be a light-weight code without extensive use of generic<br>
programming like boost.<br>
So, i was thinking of using following:<br>
<br>
*1. *Boost::AdjecencyList - for storing graph.<br>
*2. *Std::Map - for storing distanceMap, predecessorMap.<br>
<br>
*3. *For weightMap:<br>
<br>
typedef struct weight_map_element<br>
{<br>
pair<int,double> edge;<br>
double travel_time;<br>
}<br>
weight_map_element_t;<br>
<br>
class weight_map<br>
{<br>
<br>
vector<weight_map_element_t> weight_map_set;<br>
<br>
public:<br>
void insert(weight_map_element_t element);<br>
double get_travel_time(int edge_id, double start_time);<br>
<br>
};<br>
<br>
<br>
*4. *std::priority_queue for the priority queue that will be used for<br>
dijkstra search.<br>
<br></div></div></blockquote></blockquote></div></div><div><br>Well,<br>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.<br>
<br>The make_heap, and sort_heap would be too costly to maintain for dijkstra.<br></div></div></blockquote><div><br>Forgot to mention that - make_heap() and sort_heap() are provided by stl algorithms.But as mentioned, it would be very costly and inefficient to use sort_heap() each time.<br>
</div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class="gmail_quote"><div><br>Do you have any idea of open-source library that provides the heap datastructure with above functionality?<br>
<br>I am thinking of implementing binary heap myself to support the required functionality. <br>
Thoughts?<br><br><br> </div><div><div></div><div class="h5"><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div><div>
<br>
Will this be sufficient for our implementation? If yes, I will come up<br>
with the detailed internal function prototypes soon.<br>
<br>
<br>
On Wed, May 18, 2011 at 8:09 PM, Stephen Woodbridge<br></div></div><div><div></div><div>
<<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a> <mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>>> wrote:<br>
<br>
On 5/18/2011 8:08 AM, Jay Mahadeokar wrote:<br>
<br>
Hi,<br>
<br>
I think what we need is a function on following lines:<br>
<br>
Given a query_start_time, it should query the TimeDepCosts<br>
table, and<br>
return the set of entries which have their start_time within<br>
query_start_time + delta. This delta might be x hours, depending<br>
on the<br>
upper bound of the expected journey time.<br>
<br>
We need following things handled in our model:<br>
<br>
If query_start_time is 11PM Sunday and delta is 10 hours, we<br>
will need<br>
to query entries with start time between 11PM Sunday and 9AM<br>
Monday. So,<br>
basically the function needs to be periodic in terms of<br>
time_of_day and<br>
day_of_week.<br>
<br>
As Steve suggested, we can maintain conventions for day_of_week<br>
like:<br>
<br>
-3 - holidays<br>
-2 - weekend days<br>
-1 - week days<br>
0 - all days<br>
1-7 Mon - Sun.<br>
<br>
If we just assume entries for -3,-2,-1,0 and ignore each entry<br>
for Sun -<br>
Sat, that would reduce the space required assuming that the<br>
entries for<br>
weekdays is same. If times for different weekdays is different<br>
then we<br>
would have separate entries for each day.<br>
<br>
So, the query should properly examine the query_day_of_week and<br>
select<br>
the proper entries. Ex: For above query, if it is sunday, then after<br>
12AM, next entries will be queried with time_of_day as -1, but<br>
if it was<br>
Saturday, next entries will be queried with time_of_day as -2.<br>
<br>
We can have a boolean parameter like *isHoliday* in query<br>
itself, which<br>
will tell if a given day (may be weekday) is holiday or not.Then<br>
again<br>
the query will have to be modified accordingly (query for -3).<br>
This will<br>
take care of query for local holiday etc and we do not have to worry<br>
about calenders. The user will have to worry about that.. :-)<br>
<br>
<br>
This (isHoliday) might work for a single day, but will not work if<br>
the query crosses into the next day(s). Holidays are an input<br>
convenience to describe recurring events. So say we have a<br>
convenient way to input that data and store it into tables as we<br>
have described, then the query for costs would need to decide is a<br>
given day is a holiday or not and then select the correct entries to<br>
return based on that. For ease of implementation, we could just<br>
start with a stub function the returns false and later implement a<br>
table lookup based on the date or day of year that determines if<br>
isHoliday=t/f for any given start_time+offset.<br>
<br>
Then when querying schedules, for example, we would select holiday<br>
schedules if they exist and its a holiday otherwise search the<br>
regular tables.<br>
<br>
<br>
There can be time_from and time_to entries as well. But, if we<br>
just have<br>
entries like:<br>
<br>
day_of_week: -1, time_of_day: 00:01, 55mph<br>
day_of_week: -1, time_of_day: 07:00, 30mph<br>
day_of_week: -1, time_of_day: 10:01, 55mph<br>
day_of_week: -1, time_of_day: 16:31, 30mph<br>
<br>
we can assume that the entry with time_of_day 00:01 is valid upto<br>
07:00. And if query_start_time is 02:00 and delta is 10 hours,<br>
we can<br>
query entries which have time_of_day < query_start_time + delta<br>
(taking<br>
care of change of day).<br>
<br>
Is this assumption reasonable?<br>
<br>
<br>
This sounds reasonable if the response is in units of time (offset)<br>
from query_start_time. Assuming we use a resolution of seconds, then<br>
the response would be in seconds from start time.<br>
<br>
*weightMap Abstraction*<br>
<br>
<br>
I think the design would be more modular if we keep the weightMap<br>
independent of the underlying time conventions. Since as Daniel<br>
pointed<br>
out, this algorithm can also be used for non-road networks.<br>
<br>
So, whatever the underlying time conventions, we can assume that<br>
in the<br>
end the query should return pairs like:<br>
<br>
< <edgeId, offset_time> , travel_time/speed ><br>
<br>
We will assume that query_start_time is 0, i.e we offset every<br>
thing by<br>
query_start_time.<br>
The offset_time will be as follows:<br>
<br>
As in above example,<br>
If start_tme is 02:00 and day_of_week is -1, and delta as 10 hours.<br>
<br>
Then, edge entries for edgeId 1 will be:<br>
< <1, 05:00 > , 30 mph><br>
< <1, 08:01 > , 55 mph><br>
< <1, 14:31 > , 30 mph><br>
<br>
Basically, the offset_time will abstract out any internal details of<br>
weekdays, change of days etc and it will just contain the offset<br>
from<br>
start_time.<br>
<br>
<br>
I suggested seconds above, but if someone is modeling events in say<br>
glacier flow, geological times or the big bang, they might need<br>
other units of time. I would say that because we are talking about<br>
time based schedules and need to deal with days, hours minutes we<br>
should probably not worry about these other timeframes as the solver<br>
will be offset based it will work with any units and then only the<br>
wrappers for extracting the costs from the schedules would need to<br>
change to deal with other timeframes. So lets not get hung up on<br>
this, I think this is a sound plan.<br>
<br>
-Steve<br>
<br>
This will greatly simplify the core time dependent dijkstra<br>
implementation.<br>
<br>
Thoughts?<br>
<br>
On Wed, May 18, 2011 at 10:46 AM, Stephen Woodbridge<br>
<<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a> <mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>><br></div></div>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a><div><div></div><div><br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>>>> wrote:<br>
<br>
Hi Daniel,<br>
<br>
These are good points.<br>
<br>
I agree that turn restrictions should be thought about but only<br>
implemented if there is time. I think we should take the<br>
discussion<br>
of turn restriction into a separate thread. I'm interested<br>
in what<br>
you think is a limitation that can't be modeled in Dijkstra<br>
or A*.<br>
<br>
Regarding the time modeling, my point was just that we<br>
needed more<br>
thought there and a richer model developed. The crontab<br>
model is a<br>
good idea. I'm not opposed to modeling monthly or yearly<br>
events, but<br>
they rarely exist other than holidays which I tried to<br>
capture. I<br>
suppose you could model something like the Boston Marathon<br>
and model<br>
all the road closures and restrictions, but it seems to be a<br>
lot of<br>
work for a one day event, but I can see city government's<br>
deploying<br>
the resources to model something like this.<br>
<br>
Regarding timezones: Times need to be entered with zones for<br>
models<br>
that cross zones but all the data should be converted to UTC<br>
internally so it runs in a consistent time model. Timezones<br>
are for<br>
input and output, but the solver should be ignorant of them,<br>
in my<br>
opinion.<br>
<br>
I have carried my GPS from the Eastern to central time zone,<br>
and it<br>
knew the local time when I powered it up. So my guess is that it<br>
would auto correct when crossing the time zone.<br>
<br>
-Steve<br>
<br>
<br>
On 5/17/2011 10:42 PM, Daniel Kastl wrote:<br>
<br>
Hi Jay and Steve,<br>
<br>
This looks really nice, but let me give some comments<br>
regarding<br>
how to<br>
model time, because this is really tricky in my opinion.<br>
Especially when<br>
thinking about an abstract network that isn't a road<br>
network.<br>
<br>
<br>
<br>
Would it be possible to support turn restrictions in<br>
the static<br>
Dijkstra also? I'm thinking just use all the same<br>
structures but<br>
ignore the the time components to keep things<br>
simple. So if<br>
the the<br>
turn restrictions table is present we use it, otherwise<br>
assume no<br>
restrictions. If doing static shortest path with turn<br>
restrictions<br>
then ignore the time components otherwise we use<br>
them. And<br>
it is up<br>
to the user to make sure the turn restriction table<br>
is valid<br>
for the<br>
analysis being requested.<br>
<br>
<br>
Currently in pgRouting Dijkstra and A* don't support turn<br>
restrictions<br>
modelling. What I actually like on Shooting Star is, that it<br>
routes from<br>
edge to edge instead of node to node. So it allows to model<br>
relations<br>
between edges rather than nodes, which I think is more<br>
close to how<br>
humans would think of this.<br>
Dijkstra can only visit one node one times (as Shooting star<br>
only visits<br>
an edge once). Well, there can be turn restriction cases<br>
where a<br>
node is<br>
passed twice and which can't be done correctly with<br>
Dijkstra as<br>
far as I<br>
know.<br>
<br>
In the beginning I wouldn't think about the turn<br>
restrictions<br>
too much.<br>
Let's take it as an extra when we see we still have<br>
enough time.<br>
Of course if you have a good idea to implement it all at<br>
once<br>
with only<br>
little extra work, then that's fine.<br>
<br>
<br>
For time definitions in your tables I think you need<br>
to probably<br>
define some common structure for handling a time entry.<br>
<br>
<br>
Another problem might be time zones. Plain day field + time<br>
field might<br>
not be able to allow driving from one time zone to<br>
another (or just<br>
think about a flight network). I never went from one<br>
timezone to<br>
another<br>
by car or train, but Steve and Anton, you might have this<br>
experience.<br>
How does car navigation software handle this when you<br>
cross the<br>
timezone<br>
border? ;-)<br>
<br>
So taking "timestamp with timezone" for those fields<br>
might be a good<br>
idea to be able to support such a functionality.<br>
<br>
<br>
For example time_from and time_to might need to be<br>
defined as a<br>
structure that includes day_of_week. day_of week<br>
might take<br>
values like:<br>
<br>
-3 - holidays<br>
-2 - weekend days<br>
-1 - week days<br>
0 - all days<br>
1..7 - Sun,...,Sat<br>
<br>
<br>
I think the problem here is how to model recurring time<br>
dependent costs,<br>
right?<br>
If you think about weekdays, then you can't for example<br>
model<br>
monthly or<br>
yearly events.<br>
<br>
I'm not really sure this is useful information here, but<br>
I once saw<br>
about how the "iCal" format models recurring calendar<br>
events:<br>
<a href="http://ext.ensible.com/deploy/dev/examples/calendar/recurrence-widget.html" target="_blank">http://ext.ensible.com/deploy/dev/examples/calendar/recurrence-widget.html</a><br>
<br>
Maybe we can learn something from there. The example<br>
needed to be<br>
extended with some duration probably. But looking about<br>
calendar<br>
formats<br>
might be a good idea to model holidays etc.<br>
<br>
Or another (stupid) example would be cron job syntax.<br>
Something<br>
I always<br>
need to google for as I can't remember it ;-)<br>
<br>
All this time dependent stuff, events and schedules is<br>
also an<br>
issue in<br>
Darp solver.<br>
And it probably is important also for the multi-modal<br>
routing,<br>
so if we<br>
can find some clever way how to model this and can share<br>
it between<br>
algorihtms, that would be great.<br>
<br>
Daniel<br>
<br>
<br>
--<br>
Georepublic UG & Georepublic Japan<br>
eMail: <a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a><br>
<mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a>><br>
<mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a><br>
<mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a>>><br>
<mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a><br>
<mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a>><br>
<mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a><br>
<mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a>>>><br>
Web: <a href="http://georepublic.de" target="_blank">http://georepublic.de</a> <<a href="http://georepublic.de/" target="_blank">http://georepublic.de/</a>><br>
<br>
<br>
<br>
<br>
_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a>><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a>>><br>
<br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br>
<br>
_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a>><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a>>><br>
<br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br>
<br>
<br>
<br>
--<br>
Regards,<br>
-Jay Mahadeokar<br>
<br>
<br>
<br>
_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a> <mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a>><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br>
<br>
_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a> <mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a>><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br>
<br>
<br>
<br>
--<br>
Regards,<br>
-Jay Mahadeokar<br>
<br>
<br>
<br>
_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
</div></div></blockquote><div><div></div><div>
<br>
_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
</div></div></blockquote></div></div></div><br><br clear="all"><br>-- <br>Regards,<br><font color="#888888">-Jay Mahadeokar<br><br>
</font></blockquote></div><br><br clear="all"><br>-- <br>Regards,<br>-Jay Mahadeokar<br><br>