Hi Razequl,<div><br></div><div>Thanks a lot and nice to read that you have success with implementing your algorithm!</div><div>I will take a look as soon as I have some time available.</div><div><br></div><div>There is one thing we're absolutely missing and it would be great help to have it: it's a good test data set and maybe even unit tests.</div>
<div><br></div><div>Currently everyone just uses network data that each of us has available, but there may be special use cases to test as those you mentioned.</div><div>So if that also helps you and you have a time to create a test data set, that could help us to test and compare results. It might be a big help for everyone. Then everyone could refer to the data or even add new scenarios. </div>
<div><br></div><div>If you want to analyze PostgreSQL queries you can use EXPLAIN (and ANALYZE):</div><div><a href="http://www.postgresql.org/docs/9.1/static/sql-explain.html">http://www.postgresql.org/docs/9.1/static/sql-explain.html</a></div>
<div><a href="http://www.postgresql.org/docs/9.1/static/sql-analyze.html">http://www.postgresql.org/docs/9.1/static/sql-analyze.html</a></div><div><a href="http://wiki.postgresql.org/wiki/Introduction_to_VACUUM,_ANALYZE,_EXPLAIN,_and_COUNT">http://wiki.postgresql.org/wiki/Introduction_to_VACUUM,_ANALYZE,_EXPLAIN,_and_COUNT</a></div>
<div><br></div><div>Daniel</div><div><br></div><div><br></div><div><br><br><div class="gmail_quote">On Wed, Jun 20, 2012 at 6:00 AM, Razequl Islam <span dir="ltr"><<a href="mailto:ziboncsedu@gmail.com" target="_blank">ziboncsedu@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi All,<br>I have incorporated the Bi Directional Dijkstra in PGRouting in my fork. Please try it and let me know your opinion. Here are the steps:<br>
<br>Download the source from <a href="https://github.com/zibon/pgrouting" target="_blank">https://github.com/zibon/pgrouting</a> <br>
In the extra folder I put the codes for Bi Directional Dijkstra in the folder named BDSP.<br><br>From the pgrouting directory run cmake then make and make install. I have included bdsp directory in the cmakelists.txt in the pgrouting folder, so it will compile and install Bi Directional Dijkstra as well. The library file is librouting_bdsp.so.<br>
<br>You need to create the stored procedure by running the routing_bdsp.sql i.e.<br><pre><div style="background-color:transparent;font-family:verdana,sans-serif"><font><span>CREATE</span> <span>OR</span> <span>REPLACE</span> <span>FUNCTION</span> <span>bidir_dijkstra_shortest_path</span><span>(</span></font></div>
<div style="background-color:transparent;font-family:verdana,sans-serif"><font> <span>sql</span> <span>text</span><span>,</span> </font></div><div style="background-color:transparent;font-family:verdana,sans-serif">
<font> <span>source_vid</span> <span>integer</span><span>,</span> </font></div><div style="background-color:transparent;font-family:verdana,sans-serif"><font> <span>target_vid</span> <span>integer</span><span>,</span> </font></div>
<div style="background-color:transparent;font-family:verdana,sans-serif"><font> <span>directed</span> <span>boolean</span><span>,</span> </font></div><div style="background-color:transparent;font-family:verdana,sans-serif">
<font> <span>has_reverse_cost</span> <span>boolean</span><span>)</span></font></div><div style="background-color:transparent;font-family:verdana,sans-serif"><font> <span>RETURNS</span> <span>SETOF</span> <span>path_result</span></font></div>
<div style="background-color:transparent;font-family:verdana,sans-serif"><font> <span>AS</span> <span>'$libdir/librouting_bdsp'</span></font></div><div style="background-color:transparent">
<font style="font-family:verdana,sans-serif" size="2"> <span>LANGUAGE</span> <span>'C'</span> <span>IMMUTABLE</span> <span>STRICT</span><span>;</span></font><br>
</div></pre>Now, you can call bidir_dijkstra_shortest_path from sql. Here is an example query based on the ways table from pgrouting-workshop (<a href="http://workshop.pgrouting.org/" target="_blank">http://workshop.pgrouting.org/</a>)<br>
<br><pre style="font-family:verdana,sans-serif"><span>SELECT</span> <span>*</span> <span>FROM</span> bidir_dijkstra_<span>shortest_path</span><span>(</span><span>'</span>
<span> SELECT gid as id,</span>
<span> source::integer,</span>
<span> target::integer,</span>
<span> length::double precision as cost</span>,<br> length::double precision as reverse_cost <span>FROM ways'</span><span>,</span>
<span>5700</span><span>,</span> <span>6733</span><span>,</span> true<span>,</span> true<span></span><span>);</span></pre>It will return the same result as the function shortest_path does with same source and destination.<br>
<br>Issues:<br>1. I have followed TRSP for writing the wrappers and C methods. Interestingly, I found that my code doesn't work correctly if I try with undirected graphs, i.e. remove the reverse_cost parameter and make the last two boolean false. In that case all the cost value are 0 in the returned result. The path is also not right. I tested the same with TRSP and found the same thing. May be this case is not correctly implemented in the wrappers. I will check and fix that in next versions.<br>
<br>2. I need to check the query time of the functions. Is there any way to get the query time in milliseconds? Then I can compare my implementation with the current shortest path algorithm. Also I have implemented my own heap data structure and I can measure the performance of that one also against the current stl queue based implementation. You can also run it on larger road network and long route and give feedback on the performance. Your suggestions are welcome.<br>
<br>3. I found, beside node to node routing TRSP can also have paramenters to route from the some point of an edge to another point on another edge. I think, it is very helpful so, i have a plan to include that in BDSP also. Currently I am working with Bi Directional A*. After it is done, I will make the changes so that route from and to partial edges is possible.<br>
<br>It will be very helpful to get your comments, feedback and suggestions. Thanks.<br><br>regards<span class="HOEnZb"><font color="#888888"><br>
Razequl</font></span><div class="HOEnZb"><div class="h5"><br><br><div class="gmail_quote">On Fri, Jun 15, 2012 at 2:21 AM, Razequl Islam <span dir="ltr"><<a href="mailto:ziboncsedu@gmail.com" target="_blank">ziboncsedu@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi Daniel,<br>
Thanks for your suggestion. 5 steps process worked. I have added my<br>
updates to my repository.<br>
<br>
<a href="https://github.com/zibon/pgrouting" target="_blank">https://github.com/zibon/pgrouting</a><br>
<br>
Tomorrow I will give the weekly report and my work updates for this week .<br>
<br>
regards<br>
Razequl<br>
<div>On 6/10/12, Daniel Kastl <<a href="mailto:daniel@georepublic.de" target="_blank">daniel@georepublic.de</a>> wrote:<br>
> Hi Razequl,<br>
><br>
> As long as you try and test Git with your personal fork in your GitHub<br>
> account, you can't do anything wrong.<br>
> Also, as long as you don't do a "git push ..." everything is only on your<br>
> local repository and not on the GitHub repository.<br>
><br>
> What does "git remote -v" return? Does it return something like<br>
><br>
> origin git@github.com:zibon/pgrouting.git (fetch)<br>
> origin git@github.com:zibon/pgrouting.git (push)<br>
><br>
> Usual steps are:<br>
><br>
</div>> 1. git status<br>
<div>> (tellys you which files have been modified and files that have not been<br>
> added yet)<br>
</div>> 2. git add .<br>
<div>> (add all files that have not been added yet ... or just specify the<br>
> files/directories you want to add)<br>
</div>> 3. git commit -m "message" .<br>
<div>> (commit all files that have not been added yet ... or just specify the<br>
> files/directories you want to commit)<br>
</div>> 4. git pull <repository> <branch><br>
<div>> (this will either tell you all is up-to-date, or merge was successful or<br>
> tell you there was a merge conflict, that you need to resolve)<br>
</div>> 5. git push <repository> <branch><br>
<div><div>> Push the changes to the repository)<br>
><br>
> The default repository is named "origin", the default branch "master".<br>
><br>
> Can you once try all the 5 steps above and see if it solves your problem?<br>
><br>
> Daniel<br>
><br>
><br>
><br>
><br>
> On Sun, Jun 10, 2012 at 4:18 AM, Stephen Woodbridge<br>
> <<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a><br>
>> wrote:<br>
><br>
>> Hi Razequl,<br>
>><br>
>> I will look at it tomorrow night late if I have a chance. Jay if you can<br>
>> make some time to review and comment that would be great also.<br>
>><br>
>> I only have limited access at the moment and my favor <a href="http://gitref.org" target="_blank">gitref.org</a> site was<br>
>> broken last I checked. So off the top of my head I think the commands are<br>
>> something like:<br>
>><br>
>> git add <list of files><br>
>> git commit<br>
>> git push origin master<br>
>><br>
>> I think you can also do something like<br>
>> git -A commit<br>
>> which will commit all changed files, but you still probably new the git<br>
>> add for any new files you want to add to your directory.<br>
>><br>
>> So read the docs and see if the above works.<br>
>><br>
>> Thanks and congratulations for getting this far.<br>
>><br>
>> -Steve<br>
>><br>
>><br>
>> On 6/9/2012 3:46 AM, Razequl Islam wrote:<br>
>><br>
>>> Hi Steve,<br>
>>><br>
>>> 1.I implemented the first version bi directional shortest path using<br>
>>> dijkstra and attached the source code in this mail. Please have a look<br>
>>> and let me know your feedback.<br>
>>><br>
>>> 2. i tried to merge my source code to<br>
</div></div>>>> <a href="https://github.com/zibon/**pgrouting" target="_blank">https://github.com/zibon/**pgrouting</a><br>
>>> <<a href="https://github.com/zibon/pgrouting" target="_blank">https://github.com/zibon/pgrouting</a>>.<br>
<div>>>> but failed.<br>
>>><br>
>>> I have checked out the fork the local folder and created my source<br>
>>> directory bdsp under the extra folder. Then<br>
>>> i tried the following command:<br>
>>><br>
>>> git push origin master<br>
>>><br>
>>> After a few time it said that 'Everything up-to-date', but found no bdsp<br>
>>> folder in<br>
</div>>>> <a href="https://github.com/zibon/**pgrouting/tree/master/extra" target="_blank">https://github.com/zibon/**pgrouting/tree/master/extra</a><<a href="https://github.com/zibon/pgrouting/tree/master/extra" target="_blank">https://github.com/zibon/pgrouting/tree/master/extra</a>><br>
<div>>>> .<br>
>>><br>
>>> 3.I just copied my source code folder to my local repo directory. Is it<br>
>>> necessary to commit every single file of my folder. If so then what is<br>
>>> the procedure?<br>
>>><br>
>>> regards<br>
>>> razequl<br>
>>><br>
>>><br>
>>><br>
</div>>>> ______________________________**_________________<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><<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>
>> <a href="http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev</a><<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a>><br>
<div><div>>><br>
><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>
> Web: <a href="http://georepublic.de" target="_blank">http://georepublic.de</a><br>
><br>
</div></div></blockquote></div><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"><div><br></div>-- <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>