[pgrouting-dev] First version of bi-directional dijkstra
Razequl Islam
ziboncsedu at gmail.com
Thu Jun 21 05:13:27 PDT 2012
Hi Steve,
Thanks for your reply. I am also excited about the implementation and
enjoying the work.
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. :(
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.
About the algorithm, it works as follows:
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.
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.
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.
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.
Thanks.
Razequl
On Wed, Jun 20, 2012 at 9:18 PM, Stephen Woodbridge <woodbri at swoodbridge.com
> wrote:
> 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<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/ <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<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<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>
>> >>> <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>
>> <ht**tps://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<pgrouting-dev at lists.osgeo.org>
>> >
>>
>> >>>
>> http://lists.osgeo.org/****mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev>
>> **<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 <pgrouting-dev at lists.osgeo.org>>
>>
>> >>
>> http://lists.osgeo.org/****mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev>
>> **<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@**georepublic.de <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<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>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20120621/985e7255/attachment-0001.html>
More information about the pgrouting-dev
mailing list