Hi,<br><br><b>A quick update:</b><br><br>I have coded apsp.h, apsp.c and apsp_boost_wrapper.cpp<br>The apsp_boost function has following prototype:<br><br>int <br>boost_apsp(edge_t *edges, unsigned int edge_count, const int node_count,<br>
bool directed, bool has_reverse_cost,<br> apsp_element_t **pair, int *pair_count, char **err_msg);<br><br>apsp_element is on similar lines to path_element in dijkestra:<br>typedef struct apsp_element <br>
{<br> int src_vertex_id;<br> int dest_vertex_id;<br> float8 cost;<br> <br>} apsp_element_t;<br><br>It has a corresponding apsp_result in routing_core.sql<br><br>Above function seems to be working for small static input data and returns the apsp_element pairs in the desired format.<br>
<br><b>Some Questions:</b><br><br>Now, I need to code apsp.c which will retrieve the edges / nodes from postgres database and call the above function. The result will be returned as apsp_result.<br><br>For dijkestra, we have the following query format: <br>
SELECT gid, source, target, cost FROM edge_table<br><br>For, apsp will the query format remain same? <br><br>Or do we take the vertices(in form of points) as input separately, in some other format? One application of this might be when a user will select a set of points on map and call apsp on those points. <br>
<br><br><br><div class="gmail_quote">On Wed, Dec 8, 2010 at 2:12 PM, Daniel Kastl <span dir="ltr"><<a href="mailto:daniel@georepublic.de">daniel@georepublic.de</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 class="gmail_quote"><div class="im"><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><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<br></blockquote></div><div><div>For now, can we go ahead and implement the above algo in pgRouting? I am thinking of a warshall_wrapper class that would call the above function, and the actuall warshall apsp would return distances in form of rows, each row having three columns:</div>
<div>source, target, distance. (We will have nC2 such rows for now..)</div></div></div></blockquote><div><br></div></div><div>As Anton mentioned, this can get confusing sometimes. Too many sources and targets, can be the ones of an edge or of a route.</div>
<div>Any good idea how define names in an easy to understand and clear way is welcome. This is probably going to become more of an issue as more pgRouting grows.</div><div><br></div><div>@Anton: maybe we should somewhere define a dictionary of terms we use and what we use them for.</div>
<div>Other thing, I didn't really get your answer how to prevent mixing source/target ... was there a "not" missing? It wasn't clear to me </div><div class="im"><div><br></div><div> </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></div><div><div>Some queries:</div><div><br></div><div>1. I have not yet tried modifying the pgRouting source code, and compiling other files together with the existing ones. I am completely new to cmake and will try and learn how to work with that. From what I have understood, every new algorithm that we add to existing set will have a similar flow and similar files etc. Is there any doc which can guide as to what configuration changes would be needed for adding a new algo (For example we would usually add following files: algo.h, algo.cpp, algo.sql, algo_boost_wrapper.cpp etc). (I hope my query is clear)</div>
</div></div></blockquote><div><br></div></div><div>If I find some time I want to study the CMake manual, too, and see if we can make some improvements here and there. I think it was also new for Anton at the time of writing the files, so if you find some possible improvements, let me know.</div>
<div><br></div><div>There are no "coding standards" defined yet, which would be probably a good idea when more algorithm will be implemented in the future.</div><div>Same as above, if you have some idea, then you can share with us. We're open for criticism! Otherwise I believe it's sometimes better to have a couple of algorithms first and then see what could be "standardized" and define them based on our experience.</div>
<div><br></div><div>Btw., if you want to make use of GitHub, then you can create an account and fork the pgRouting repository: <a href="https://github.com/pgRouting/pgrouting" target="_blank">https://github.com/pgRouting/pgrouting</a></div>
<div>It will be then easy to apply your changes.</div><div><br></div><div>Anton, where will APSP go? To "core" or to "extras"?</div><div>Seeing the number of extensions grow, does this structure still work for us?</div>
<div>How do we define what is "core" and what is "extra"? </div><div>I think the initial main idea was to provide pgRouting without Gaul and CGAL dependencies.</div><div class="im"><div>
<br></div><div> </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>
<div><br></div><div>2. Are there any sample test cases/scripts, which were used to test dijkstras algo (which can be useful here too)? </div></div></div></blockquote><div><br></div></div><div>I think that pgRouting should have unit tests ... but we don't have so far, which is not so good ;-)</div>
<div>Here is a ticket already: <a href="https://github.com/pgRouting/pgrouting/issues#issue/20" target="_blank">https://github.com/pgRouting/pgrouting/issues#issue/20</a></div><div>As usual it's a lack of time to work on this.</div>
<div>
<br></div><div>It's probably better to have some generic testing data than just take OSM data from the workshop, Anton.</div><div>OSM data won't allow us to test all possible functionality some functions provide.</div>
<div><br></div><font color="#888888"><div>Daniel</div><div><br></div><div><br></div></font></div><div><div></div><div class="h5"><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></div><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>Regards,<br>-Jay Mahadeokar<br><br>