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" class="line" id="LC8"><font><span class="k">CREATE</span> <span class="k">OR</span> <span class="k">REPLACE</span> <span class="k">FUNCTION</span> <span class="n">bidir_dijkstra_shortest_path</span><span class="p">(</span></font></div>
<div style="background-color:transparent;font-family:verdana,sans-serif" class="line" id="LC9"><font> <span class="k">sql</span> <span class="nb">text</span><span class="p">,</span> </font></div><div style="background-color:transparent;font-family:verdana,sans-serif" class="line" id="LC10">
<font> <span class="n">source_vid</span> <span class="nb">integer</span><span class="p">,</span> </font></div><div style="background-color:transparent;font-family:verdana,sans-serif" class="line" id="LC11"><font> <span class="n">target_vid</span> <span class="nb">integer</span><span class="p">,</span> </font></div>
<div style="background-color:transparent;font-family:verdana,sans-serif" class="line" id="LC12"><font> <span class="n">directed</span> <span class="nb">boolean</span><span class="p">,</span> </font></div><div style="background-color:transparent;font-family:verdana,sans-serif" class="line" id="LC13">
<font> <span class="n">has_reverse_cost</span> <span class="nb">boolean</span><span class="p">)</span></font></div><div style="background-color:transparent;font-family:verdana,sans-serif" class="line" id="LC14"><font> <span class="k">RETURNS</span> <span class="k">SETOF</span> <span class="n">path_result</span></font></div>
<div style="background-color:transparent;font-family:verdana,sans-serif" class="line" id="LC15"><font> <span class="k">AS</span> <span class="s1">'$libdir/librouting_bdsp'</span></font></div><div style="background-color:transparent" class="line" id="LC16">
<font style="font-family:verdana,sans-serif" size="2"> <span class="k">LANGUAGE</span> <span class="s1">'C'</span> <span class="k">IMMUTABLE</span> <span class="k">STRICT</span><span class="p">;</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/">http://workshop.pgrouting.org/</a>)<br>
<br><pre style="font-family:verdana,sans-serif"><span class="k">SELECT</span> <span class="o">*</span> <span class="k">FROM</span> bidir_dijkstra_<span class="n">shortest_path</span><span class="p">(</span><span class="s1">'</span>
<span class="s1"> SELECT gid as id,</span>
<span class="s1"> source::integer,</span>
<span class="s1"> target::integer,</span>
<span class="s1"> length::double precision as cost</span>,<br> length::double precision as reverse_cost <span class="s1">FROM ways'</span><span class="p">,</span>
<span class="mi">5700</span><span class="p">,</span> <span class="mi">6733</span><span class="p">,</span> true<span class="p">,</span> true<span class="k"></span><span class="p">);</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<br>
Razequl<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 class="im">On 6/10/12, Daniel Kastl <<a href="mailto:daniel@georepublic.de">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 class="im">> (tellys you which files have been modified and files that have not been<br>
> added yet)<br>
</div>> 2. git add .<br>
<div class="im">> (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 class="im">> (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 class="im">> (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 class="h5">> 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">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 class="im">>>> 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 class="im">>>> .<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">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">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 class="HOEnZb"><div class="h5">>><br>
><br>
><br>
><br>
> --<br>
> Georepublic UG & Georepublic Japan<br>
> eMail: <a href="mailto:daniel.kastl@georepublic.de">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>