[pgrouting-dev] First version of bi-directional dijkstra
Stephen Woodbridge
woodbri at swoodbridge.com
Wed Jun 20 08:18:47 PDT 2012
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 at gmail.com
> <mailto:ziboncsedu at 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 at georepublic.de
> <mailto:daniel at 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 at github.com:zibon/pgrouting.git (fetch)
> > origin git at 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 at swoodbridge.com <mailto:woodbri at 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 at lists.osgeo.org
> <mailto:pgrouting-dev at 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 at lists.osgeo.org <mailto:pgrouting-dev at 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 at georepublic.de
> <mailto:daniel.kastl at georepublic.de>
> > Web: http://georepublic.de
> >
>
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
More information about the pgrouting-dev
mailing list