Hi Razequl,
Excellent job! You have been very busy. More comments inline below ...
On 6/20/2012 12:00 AM, Razequl Islam wrote:
Hi All,
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:
Download the source from https://github.com/zibon/pgrouting
In the extra folder I put the codes for Bi Directional Dijkstra in the
folder named BDSP.
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.
You need to create the stored procedure by running the routing_bdsp.sql i.e.
CREATE OR REPLACE FUNCTION bidir_dijkstra_shortest_path(
sql text,
source_vid integer,
target_vid integer,
directed boolean,
has_reverse_cost boolean)
RETURNS SETOF path_result
AS '$libdir/librouting_bdsp'
LANGUAGE 'C' IMMUTABLE STRICT;
Now, you can call bidir_dijkstra_shortest_path from sql. Here is an
example query based on the ways table from pgrouting-workshop
(http://workshop.pgrouting.org/)
SELECT * FROM bidir_dijkstra_shortest_path('
SELECT gid as id,
source::integer,
target::integer,
length::double precision as cost,
length::double precision as reverse_costFROM ways',
5700, 6733, true, true);
It will return the same result as the function shortest_path does with
same source and destination.
Issues:
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.
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.
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.
I the command line psql you can use the command:
\timing
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.
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.
Yes, this would be a nice feature to add to you implementation.
It will be very helpful to get your comments, feedback and suggestions.
Thanks.
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.
Forward routing basically asks the question: From the current node, what nodes can I go to?
Reverse routing has to ask a different question: From the current node, what nodes could I have come from?
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.
So, can you explain what if any of this you are doing and/or not doing with your current algorithm.
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.
Thanks,
-Steve
regards
Razequl
On Fri, Jun 15, 2012 at 2:21 AM, Razequl Islam <ziboncsedu@gmail.com
<mailto:ziboncsedu@gmail.com>> wrote:
Hi Daniel,
Thanks for your suggestion. 5 steps process worked. I have added my
updates to my repository.
https://github.com/zibon/pgrouting
Tomorrow I will give the weekly report and my work updates for this
week .
regards
Razequl
On 6/10/12, Daniel Kastl <daniel@georepublic.de
<mailto:daniel@georepublic.de>> wrote:
> Hi Razequl,
>
> As long as you try and test Git with your personal fork in your
GitHub
> account, you can't do anything wrong.
> Also, as long as you don't do a "git push ..." everything is only
on your
> local repository and not on the GitHub repository.
>
> What does "git remote -v" return? Does it return something like
>
> origin git@github.com:zibon/pgrouting.git (fetch)
> origin git@github.com:zibon/pgrouting.git (push)
>
> Usual steps are:
>
> 1. git status
> (tellys you which files have been modified and files that have
not been
> added yet)
> 2. git add .
> (add all files that have not been added yet ... or just
specify the
> files/directories you want to add)
> 3. git commit -m "message" .
> (commit all files that have not been added yet ... or just
specify the
> files/directories you want to commit)
> 4. git pull <repository> <branch>
> (this will either tell you all is up-to-date, or merge was
successful or
> tell you there was a merge conflict, that you need to resolve)
> 5. git push <repository> <branch>
> Push the changes to the repository)
>
> The default repository is named "origin", the default branch
"master".
>
> Can you once try all the 5 steps above and see if it solves your
problem?
>
> Daniel
>
> On Sun, Jun 10, 2012 at 4:18 AM, Stephen Woodbridge
> <woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>
>> wrote:
>
>> Hi Razequl,
>>
>> I will look at it tomorrow night late if I have a chance. Jay if
you can
>> make some time to review and comment that would be great also.
>>
>> I only have limited access at the moment and my favor gitref.org
<http://gitref.org> site was
>> broken last I checked. So off the top of my head I think the
commands are
>> something like:
>>
>> git add <list of files>
>> git commit
>> git push origin master
>>
>> I think you can also do something like
>> git -A commit
>> which will commit all changed files, but you still probably new
the git
>> add for any new files you want to add to your directory.
>>
>> So read the docs and see if the above works.
>>
>> Thanks and congratulations for getting this far.
>>
>> -Steve
>>
>> On 6/9/2012 3:46 AM, Razequl Islam wrote:
>>
>>> Hi Steve,
>>>
>>> 1.I implemented the first version bi directional shortest path
using
>>> dijkstra and attached the source code in this mail. Please have
a look
>>> and let me know your feedback.
>>>
>>> 2. i tried to merge my source code to
>>> https://github.com/zibon/**pgrouting
>>> <https://github.com/zibon/pgrouting>\.
>>> but failed.
>>>
>>> I have checked out the fork the local folder and created my source
>>> directory bdsp under the extra folder. Then
>>> i tried the following command:
>>>
>>> git push origin master
>>>
>>> After a few time it said that 'Everything up-to-date', but
found no bdsp
>>> folder in
>>>
https://github.com/zibon/**pgrouting/tree/master/extra<https://github.com/zibon/pgrouting/tree/master/extra>
>>> .
>>>
>>> 3.I just copied my source code folder to my local repo
directory. Is it
>>> necessary to commit every single file of my folder. If so then
what is
>>> the procedure?
>>>
>>> regards
>>> razequl
>>>
>>> ______________________________**_________________
>>> pgrouting-dev mailing list
>>> pgrouting-dev@lists.osgeo.org
<mailto:pgrouting-dev@lists.osgeo.org>
>>>
http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>>>
>>
>> ______________________________**_________________
>> pgrouting-dev mailing list
>> pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
>>
http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>>
>
> --
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl@georepublic.de
<mailto:daniel.kastl@georepublic.de>
> Web: http://georepublic.de
>
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
