Hi Steve,<br>Thanks for your reply. I am also excited about the implementation and enjoying the work.<br><br>To measure time I used EXPLAIN ANALYZE as suggested by Daniel. but the road network I have is so small that it takes very small time to process when the cache is hot. It is typically between 20-40 ms. I think I need a bigger network so that I can try on bigger route. I am trying to get the London OSM data but struggling with the internet speed. :(<br>
<br>About the problem of undirected graph, I will let you know as soon as I find something. I think the fix can go to TRSP as well.<br><br>About the algorithm, it works as follows:<br><br>I start exploration from both source and destination using two priority queues. One is forward queue and the other is reverse. The exploration from the destination uses the reverse of the edges. I handle it in during the exploration. In my edge data structure there is a direction variable and there are cost and reverse_cost. Cost refers to the cost of getting to target from source where reverse_cost is cost to source from target. Now in case of a one way road one of cost and reverse_cost will be negative or have a very large value. When doing a forward search I use cost for getting from source to target of and edge and reverse_cost for getting from target to source. But in case of reverse search I make it reverse, i.e. I use the cost for getting from target to source and the reverse_cost for getting from source to target. This approach actually analogous to searching on a reverse graph. <br>
<br>The stopping condition is something more than just the two searches meet. I need to make sure that no path with lower cost is possible. For this I keep a variable which contains the minimum cost found so far. Until the two search meet, it is infinite. When the forward search explores a node that is already explored by the reverse search, I have a new path that goes through the node and I check if the cost is lower than the current minimum cost. If it is, the minimum cost is updated. Same check is done for a reverse exploration. When the sum of the top nodes of two queues are greater than this minimum cost, we are sure that there is no path with lower cost and we stop.<br>
<br>Please let me know if there is any confusion on my explanation or something should be changed. Also please check the implementation when you get some time and let me know the feedback.<br><br>N.B. I think I just found a bug and will commit the fix in a while. Please make sure you download and use the latest source.<br>
<br>Thanks.<br>Razequl<br><br><br><br><div class="gmail_quote">On Wed, Jun 20, 2012 at 9:18 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:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Razequl,<br>
<br>
Excellent job! You have been very busy. More comments inline below ...<div><div class="h5"><br>
<br>
On 6/20/2012 12:00 AM, Razequl Islam wrote:<br>
</div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div class="h5">
Hi All,<br>
I have incorporated the Bi Directional Dijkstra in PGRouting in my fork.<br>
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/<u></u>pgrouting</a><br>
In the extra folder I put the codes for Bi Directional Dijkstra in the<br>
folder named BDSP.<br>
<br>
From the pgrouting directory run cmake then make and make install. I<br>
have included bdsp directory in the cmakelists.txt in the pgrouting<br>
folder, so it will compile and install Bi Directional Dijkstra as well.<br>
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>
<br>
CREATE OR REPLACE FUNCTION bidir_dijkstra_shortest_path(<br>
<br>
sql text,<br>
source_vid integer,<br>
target_vid integer,<br>
<br>
directed boolean,<br>
has_reverse_cost boolean)<br>
RETURNS SETOF path_result<br>
<br>
AS '$libdir/librouting_bdsp'<br>
LANGUAGE 'C' IMMUTABLE STRICT;<br>
<br>
Now, you can call bidir_dijkstra_shortest_path from sql. Here is an<br>
example query based on the ways table from pgrouting-workshop<br>
(<a href="http://workshop.pgrouting.org/" target="_blank">http://workshop.pgrouting.<u></u>org/</a>)<br>
<br>
SELECT * FROM bidir_dijkstra_shortest_path('<br>
SELECT gid as id,<br>
source::integer,<br>
target::integer,<br>
length::double precision as cost,<br></div></div>
length::double precision as reverse_costFROM ways',<div class="im"><br>
5700, 6733, true, true);<br>
<br>
It will return the same result as the function shortest_path does with<br>
same source and destination.<br>
<br>
Issues:<br>
1. I have followed TRSP for writing the wrappers and C methods.<br>
Interestingly, I found that my code doesn't work correctly if I try with<br>
undirected graphs, i.e. remove the reverse_cost parameter and make the<br>
last two boolean false. In that case all the cost value are 0 in the<br>
returned result. The path is also not right. I tested the same with TRSP<br>
and found the same thing. May be this case is not correctly implemented<br>
in the wrappers. I will check and fix that in next versions.<br>
</div></blockquote>
<br>
Hmmm, you might have found a bug, our original use case was for a directed graph and I'm pretty sure I did not set up a test case for an undirected graph. Let us know what you find out on this.<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
2. I need to check the query time of the functions. Is there any way to<br>
get the query time in milliseconds? Then I can compare my implementation<br>
with the current shortest path algorithm. Also I have implemented my own<br>
heap data structure and I can measure the performance of that one also<br>
against the current stl queue based implementation. You can also run it<br>
on larger road network and long route and give feedback on the<br>
performance. Your suggestions are welcome.<br>
</blockquote>
<br></div>
I the command line psql you can use the command:<br>
<br>
\timing<br>
<br>
to toggle the timing response on/off. also see \? for help on the other commands available. When you are doing timing tests you need to be aware of cold/hot cache issues. Typically if you run a command twice in succession it might take 100ms on the first run and then 18ms on all successive runs. In the first run you are seeing the cost of loading pages from disk into cache, then the faster runs are pulling the pages from the hot cache and not hitting the disk again.<div class="im">
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
3. I found, beside node to node routing TRSP can also have paramenters<br>
to route from the some point of an edge to another point on another<br>
edge. I think, it is very helpful so, i have a plan to include that in<br>
BDSP also. Currently I am working with Bi Directional A*. After it is<br>
done, I will make the changes so that route from and to partial edges is<br>
possible.<br>
</blockquote>
<br></div>
Yes, this would be a nice feature to add to you implementation.<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
It will be very helpful to get your comments, feedback and suggestions.<br>
Thanks.<br>
</blockquote>
<br></div>
For you bidirectional solver do you start at each end and route until the two path meet, correct? In the reverse path (ie: from end to beginning) do you route forward from end to start or reverse the sense of the path. I'll try to explain.<br>
<br>
Forward routing basically asks the question: From the current node, what nodes can I go to?<br>
<br>
Reverse routing has to ask a different question: From the current node, what nodes could I have come from?<br>
<br>
In the simple case of an undirected graph these both reduce to the same question and can be solved with the forward routing algorithm. But this is not the case with a directed graph especially when you consider one-way streets. I think this can be solved by either constructing a reverse graph or by adding additional structures to your graph to make it a composite forward and reverse graph.<br>
<br>
So, can you explain what if any of this you are doing and/or not doing with your current algorithm.<br>
<br>
I have not had a chance to check out your code and review it yet, I hope to be able to do this over the coming weekend.<br>
<br>
Thanks,<br>
-Steve<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
regards<br>
Razequl<br>
<br>
On Fri, Jun 15, 2012 at 2:21 AM, Razequl Islam <<a href="mailto:ziboncsedu@gmail.com" target="_blank">ziboncsedu@gmail.com</a><br></div><div class="im">
<mailto:<a href="mailto:ziboncsedu@gmail.com" target="_blank">ziboncsedu@gmail.com</a>>> wrote:<br>
<br>
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/<u></u>pgrouting</a><br>
<br>
Tomorrow I will give the weekly report and my work updates for this<br>
week .<br>
<br>
regards<br>
Razequl<br>
On 6/10/12, Daniel Kastl <<a href="mailto:daniel@georepublic.de" target="_blank">daniel@georepublic.de</a><br></div><div><div class="h5">
<mailto:<a href="mailto:daniel@georepublic.de" target="_blank">daniel@georepublic.de</a>><u></u>> wrote:<br>
> Hi Razequl,<br>
><br>
> As long as you try and test Git with your personal fork in your<br>
GitHub<br>
> account, you can't do anything wrong.<br>
> Also, as long as you don't do a "git push ..." everything is only<br>
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/<u></u>pgrouting.git (fetch)<br>
> origin git@github.com:zibon/<u></u>pgrouting.git (push)<br>
><br>
> Usual steps are:<br>
><br>
> 1. git status<br>
> (tellys you which files have been modified and files that have<br>
not been<br>
> added yet)<br>
> 2. git add .<br>
> (add all files that have not been added yet ... or just<br>
specify the<br>
> files/directories you want to add)<br>
> 3. git commit -m "message" .<br>
> (commit all files that have not been added yet ... or just<br>
specify the<br>
> files/directories you want to commit)<br>
> 4. git pull <repository> <branch><br>
> (this will either tell you all is up-to-date, or merge was<br>
successful or<br>
> tell you there was a merge conflict, that you need to resolve)<br>
> 5. git push <repository> <branch><br>
> Push the changes to the repository)<br>
><br>
> The default repository is named "origin", the default branch<br>
"master".<br>
><br>
> Can you once try all the 5 steps above and see if it solves your<br>
problem?<br>
><br>
> Daniel<br>
><br>
><br>
><br>
><br>
> On Sun, Jun 10, 2012 at 4:18 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>><div class="im">
<br>
>> wrote:<br>
><br>
>> Hi Razequl,<br>
>><br>
>> I will look at it tomorrow night late if I have a chance. Jay if<br>
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><br></div>
<<a href="http://gitref.org" target="_blank">http://gitref.org</a>> site was<div><div class="h5"><br>
>> broken last I checked. So off the top of my head I think the<br>
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<br>
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<br>
using<br>
>>> dijkstra and attached the source code in this mail. Please have<br>
a look<br>
>>> and let me know your feedback.<br>
>>><br>
>>> 2. i tried to merge my source code to<br>
>>> <a href="https://github.com/zibon/**pgrouting" target="_blank">https://github.com/zibon/**<u></u>pgrouting</a><br>
>>> <<a href="https://github.com/zibon/pgrouting" target="_blank">https://github.com/zibon/<u></u>pgrouting</a>>.<br>
>>> 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<br>
found no bdsp<br>
>>> folder in<br>
>>><br>
<a href="https://github.com/zibon/**pgrouting/tree/master/extra" target="_blank">https://github.com/zibon/**<u></u>pgrouting/tree/master/extra</a><<a href="https://github.com/zibon/pgrouting/tree/master/extra" target="_blank">ht<u></u>tps://github.com/zibon/<u></u>pgrouting/tree/master/extra</a>><br>
>>> .<br>
>>><br>
>>> 3.I just copied my source code folder to my local repo<br>
directory. Is it<br>
>>> necessary to commit every single file of my folder. If so then<br>
what is<br>
>>> the procedure?<br>
>>><br>
>>> regards<br>
>>> razequl<br>
>>><br>
>>><br>
>>><br>
>>> ______________________________<u></u>**_________________<br>
>>> pgrouting-dev mailing list<br>
>>> <a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br></div></div>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><div class="im"><br>
>>><br>
<a href="http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/**<u></u>mailman/listinfo/pgrouting-dev</a><u></u><<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><u></u>><br>
>>><br>
>><br>
>> ______________________________<u></u>**_________________<br>
>> pgrouting-dev mailing list<br></div>
>> <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.<u></u>osgeo.org</a>><div class="im">
<br>
>><br>
<a href="http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/**<u></u>mailman/listinfo/pgrouting-dev</a><u></u><<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><u></u>><br>
>><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></div>
<mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@<u></u>georepublic.de</a>><br>
> Web: <a href="http://georepublic.de" target="_blank">http://georepublic.de</a><br>
><br>
<br>
<br>
<br>
<br>
______________________________<u></u>_________________<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/<u></u>mailman/listinfo/pgrouting-dev</a><br>
<br>
</blockquote>
<br>
<br>
______________________________<u></u>_________________<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/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</blockquote></div><br>