[pgrouting-dev] First version of bi-directional dijkstra
Daniel Kastl
daniel at georepublic.de
Tue Jun 19 23:54:45 PDT 2012
Hi Razequl,
Thanks a lot and nice to read that you have success with implementing your
algorithm!
I will take a look as soon as I have some time available.
There is one thing we're absolutely missing and it would be great help to
have it: it's a good test data set and maybe even unit tests.
Currently everyone just uses network data that each of us has available,
but there may be special use cases to test as those you mentioned.
So if that also helps you and you have a time to create a test data set,
that could help us to test and compare results. It might be a big help for
everyone. Then everyone could refer to the data or even add new scenarios.
If you want to analyze PostgreSQL queries you can use EXPLAIN (and ANALYZE):
http://www.postgresql.org/docs/9.1/static/sql-explain.html
http://www.postgresql.org/docs/9.1/static/sql-analyze.html
http://wiki.postgresql.org/wiki/Introduction_to_VACUUM,_ANALYZE,_EXPLAIN,_and_COUNT
Daniel
On Wed, Jun 20, 2012 at 6:00 AM, Razequl Islam <ziboncsedu at gmail.com> 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_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
>> >
>>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> 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/4de683d7/attachment-0001.html>
More information about the pgrouting-dev
mailing list