[pgrouting-dev] First version of bi-directional dijkstra
Razequl Islam
ziboncsedu at gmail.com
Tue Jun 19 21:00:03 PDT 2012
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_cost FROM 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.
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.
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.
It will be very helpful to get your comments, feedback and suggestions.
Thanks.
regards
Razequl
On Fri, Jun 15, 2012 at 2:21 AM, Razequl Islam <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> 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
> >> 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 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
> >>> 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
> >> 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
> > Web: http://georepublic.de
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20120620/6c2005b9/attachment-0001.html>
More information about the pgrouting-dev
mailing list