Hi Jay,<div><br></div><div>Thank you for your work!</div><div>See my answers inline<br><br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><br>
Steve, is there any specific input data format for which I should write plsql wrapper function? I think we should finalise this within this week and get the coding part done. <br><br>We had also earlier discussed about time dependent turn restrictions(not part of the main project plan), but I am not sure if we can fit this in schedule. I hope we can look at it after GSoc. <br>
</blockquote><div><br></div><div>I think it's better to first wait for some real requirement for this and first see how the acceptance is of the current TDSP.</div><div>You can mention it somewhere in the documentation, source, create a ticket or RFC or something like that, so it will be written down somewhere.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<br>Daniel, Anton, is there anything specific that I need to do with regards to the project, so that it can be bundled with the pgRouting 2.0? Currently I am using a modified CMake file[2], and not compiling the test framework. Till now, I have not worked with this testing framework designed by Kishore (right?) so should I read any docs that will get me introduced with it?<br>
</blockquote><div><br></div><div>Well, I'm not sure how quick such a 2.0 version will be. At the moment I and Anton have a lot of other work and priority is usually higher of customer projects.</div><div><br></div><div>
The current separation in Core + Extra has just one reason: being able to install pgRouting without GAUL and/or CGAL dependency.</div><div>At the moment these dependencies exist for:</div><div><ul><li>TSP</li><li>Driving distance</li>
<li>DARP</li></ul>Following the current logic everything that doesn't use GAUL or CGAL should just be part of pgRouting core functions, whether it is version 1 or 2. (Since I hope to be able to get rid of CGAL in 2.0 and GAUL is usually easy to handle, there wouldn't be such a separation anymore anyway.)</div>
<div><br></div><div>Sorry, the test framework I don't have a clear opinion yet. I think it's Kishore's proposed testing but anyone is free to make suggestions how to improve it. </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<br>Finally, back in February, I had got the All Pairs Shortest Path Algorithm working, but proper testing, documentation and tutorial is left for that. Should time permit, can we include this also as part of GSoc or keep it separate?<br>
</blockquote><div><br></div><div>Of course! That would be nice if you had a time for that as well.</div><div><br></div><div>Daniel</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<br>[1] <a href="https://github.com/pgRouting/pgrouting/wiki/TDSP-Tentative-Project-Plan" target="_blank">https://github.com/pgRouting/pgrouting/wiki/TDSP-Tentative-Project-Plan</a><br>[2] <a href="https://github.com/pgRouting/pgrouting/blob/gsoc-tdsp/CMakeLists.txt" target="_blank">https://github.com/pgRouting/pgrouting/blob/gsoc-tdsp/CMakeLists.txt</a><div>
<div></div><div class="h5"><br>
<br><br><br><div class="gmail_quote">On Fri, Jul 22, 2011 at 12:44 AM, Jay Mahadeokar <span dir="ltr"><<a href="mailto:jai.mahadeokar@gmail.com" target="_blank">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">
Hi all,<br><br>Steve, Daniel, thanks for the input. <br><br>Well, I have written the plsql function on lines of what you suggested, for the data format that I had created earlier and it seems to be working for now, with cyclic issue also taken into account and all times offset from query_start_time.<br>
<br>I have updated the code in gsoc-tdsp repository[1] .<br><br>I also changed the existing tdsp.h, tdsp.c and weight_map.hpp files so that end_time is also taken into account (I had written a more complex code earlier and thought end_time was redundant and wasn't necessary, corrected that now).<br>
<br>So, now basically the tdsp query expects a data from time_dep_costs table as set of rows: edge_id, start_time, end_time, travel_time.<br><br>Example: <br><br>SELECT * FROM time_dependent_shortest_path('<br> SELECT gid as id,<br>
source::integer,<br> target::integer,<br> length::double precision as cost<br> FROM ways',<br> 81, 359, true, false,'select edge_id, start_time, end_time, travel_time from pgr_get_time_dep_costs(''time_dep_costs'',14,12)',0);<br>
<br>Here 6th parameter is the nested pgr function.<br><br>I think there is no need to pass query_start_time to the main time_dep_shortest_path function since we are passing it to nested function and that will always be 0 in main query (parameter 7).<br>
<br>Also, the parameters is_directed and has_reverse_cost seem redundant, since in this case graph will be always directed I think. So, maybe these can be removed.<br><br>Next step would be to write similar plsql functions for most standard data formats. If you can suggest the most obvious cases, I can start working on that.<br>
<br>[1] <a href="https://github.com/pgRouting/pgrouting/blob/gsoc-tdsp/extra/tdsp/sql/tdsp_data_wrappers.sql" target="_blank">https://github.com/pgRouting/pgrouting/blob/gsoc-tdsp/extra/tdsp/sql/tdsp_data_wrappers.sql</a><div>
<div></div><div><br><br><div class="gmail_quote">
On Tue, Jul 19, 2011 at 10:29 AM, 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">
<div>On 7/19/2011 12:24 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"><div>
<br>
<br>
On Tue, Jul 19, 2011 at 9:05 AM, Stephen Woodbridge<br></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.<u></u>com</a>>> wrote:<br>
<br></div><div>
Jay, Daniel,<br>
<br>
I think we need to get our heads around this or it will be very hard<br>
for Jay to complete this as a useful tool.<br>
<br>
<br>
Jay says:<br>
<br>
What im not clear is, how do we package this in the overall<br>
pgRouting project?<br>
<br>
<br>
This is exactly the problem. So here is my 2 rupees :) on this:<br>
<br>
<br>
Wow, that was innovative! :)<br>
</div></blockquote>
<br>
Well probably not, sorry that is what happens when I'm too tired and try to be cute. <sigh><div><div></div><div><br>
<br>
<blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204, 204, 204);padding-left:1ex">
<br>
I think the core algorithm needs to be generic so it works with any<br>
time frames that someone might want to use.<br>
<br>
<br>
As far as I think, this part is ready.<br>
<br>
Then we layer over that application implementations using wrappers<br>
or additional code. So since most people today are using pgRouting<br>
for vehicle routing applications I think we need to implement and<br>
easy to use wrapper that deals with vehicle applications of date and<br>
time of day dependencies. This does not preclude someone else coming<br>
in later and writing a new wrapper to deal with their application<br>
working in years or microsecond intervals.<br>
<br>
<br>
Now, general pgRouting query is somewhat like this:<br>
<br>
1. Pass parameters to pgRouting query<br>
2. Extract data from database according to sql parameter passed<br>
3. Generate the graph and other parameters using data extracted<br>
4. Pass data and other parameters to internal function<br>
5. Function calculates the result<br>
6. Convert the result into pgRouting result and return it.<br>
<br>
So, we have steps 3,4,5 and 6 ready.<br>
<br>
For tdsp, In step 2 we need to query 2 tables separately. Query to table<br>
ways will be generic.Query to table time_dep_costs, should take care of<br>
cyclic nature and other things.<br>
<br>
We can have two approaches:<br>
<br>
1. Take some specific case like day and time, and write down code that<br>
will take care of above thing. When we bundle this for with pgRouting<br>
the query will become specific to that format.<br>
Whenever a new data format is there, someone will need to re-code step<br>
2. Since, this is internal to pgRouting, this cannot be done by<br>
application developer. Then we would need to recompile whole thing as a<br>
separate query before using it.<br>
<br>
2. We could implement specific functions that can be used as query to<br>
time_dep_costs. Those can be installed as separate pgRouting functions<br>
itself. For simple applications where the data is in intervals of 24<br>
hours, and cyclic we can just provide a postgres plsql function and it<br>
should serve the function. I am not good at plsql, but I believe it is a<br>
very flexible tool and can be used for complex data formats as well<br>
(thoughts?)<br>
<br>
I think approach 2 is much better and it keeps the main tdsp query<br>
independent of the data format. We just need to write plsql functions<br>
for different data formats and supply those as sql argument to tdsp<br>
query to retrieve data from time_dep_costs table.<br>
<br>
If you think this is a good approach, I can start learning plsql in<br>
detail and work on writing retrieval functions for specific data formats.<br>
<br>
Is this model right? I can go ahead and start work on that.<br>
</blockquote>
<br></div></div>
Yes, I think approach 2 is the better model because application developer should not be required to recompile anything.<br>
<br>
plsql is very straight forward, and I think we can all help with the learning curve or even coding some of it if we have time. I think if you assume a set returning function then you have inputs and a record structure of your results. The function takes the inputs and returns a set of records. So for example:<br>
<br>
-- define an output record structure as a type<br>
-- using pgr_ as namespace for function, change as appropriate<br>
<br>
create type pgr_time_dep_costs as (<br>
edge_id int,<br>
time_start float,<br>
time_stop float,<br>
avg_speed float,<br>
transit_time float<br>
);<br>
<br>
<br>
CREATE OR REPLACE FUNCTION pgr_get_time_dep_costs(<u></u>schedule_tab text, start_date_time timestamp, max_time_duration_sec int, ...)<br>
RETURNS SETOF pgr_time_dep_costs AS<br>
$BODY$<br>
DECLARE<br>
out pgr_time_dep_costs;<br>
<br>
BEGIN<br>
<br>
LOOP<br>
-- compute values of out from the input<br>
<br>
-- load the values into out<br>
out.edge_id := ...;<br>
out.time_start := ...;<br>
out.time_stop := ...;<br>
out.avg_spd := ...;<br>
out.tansit_time := ...;<br>
<br>
RETURN NEXT out; -- return an out record<br>
END LOOP;<br>
<br>
RETURN; -- exit the procedure<br>
END<br>
$BODY$<br>
LANGUAGE plpgsql VOLATILE<br>
COST 100<br>
ROWS 1000;<br>
<br></blockquote><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204, 204, 204);padding-left:1ex">
This is pretty basic, but it should help get you started.<br>
<br>
-Steve<br>
<br>
<blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204, 204, 204);padding-left:1ex"><div>
For this project we need a concrete implementation that allow<br>
someone to create a table of time based restrictions of some kind on<br>
edges and reasonable easy say generate a route start at X and use<br>
these time dependent restrictions.<br>
<br>
I do not think it needs to deal with every single possible case, but<br>
it should be a reason set of cases. We can always expand on this<br>
after GSoC. I think it would be good in the documentation, we add<br>
some notes about things we thought of be did not support and a short<br>
paragraph of our thoughts on how to support it in the future.<br>
<br>
You need to size this to the time you have available so you can be<br>
successful. I will let Daniel be the final arbiter on this as I will<br>
be out of town again later this week and my time here seems to on<br>
overload lately.<br>
<br>
The key idea here is layer of tasks, and structure. We need to<br>
bridge the gap between low-level generic code and higher level<br>
application specific presentation of which there my be many<br>
depending on the application in discussion.<br>
<br>
Best regards,<br>
-Steve<br clear="all"></div></blockquote></blockquote></div><br></div></div>-- <br>Regards,<br><font color="#888888">-Jay Mahadeokar<br><br>
</font></blockquote></div><br><br clear="all"><br></div></div>-- <br>Regards,<br><font color="#888888">-Jay Mahadeokar<br><br>
</font><br>_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org">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></blockquote></div><br><br clear="all"><br>-- <br><span style="font-family:arial, sans-serif;font-size:13px;border-collapse:collapse">Georepublic UG & Georepublic Japan<br>eMail: <a href="mailto:daniel.kastl@georepublic.de" style="color:rgb(66, 99, 171)" target="_blank">daniel.kastl@georepublic.de</a><br>
Web: <a href="http://georepublic.de/" style="color:rgb(66, 99, 171)" target="_blank">http://georepublic.de</a></span><br>
</div>