[GRASS-dev] Re: [GRASS5] v.net.path

[Robin Chauhan]

On 5/4/06, Radim Blazek <radim.blazek at gmail.com> wrote:
> On 5/3/06, Robin Chauhan <robin.chauhan at gmail.com> wrote:
> > > dglib is not slow, the only problem is to calculate matrices of costs
> > > for more points becaus dglib cache can fail it is disabled in v.net.* modules.
> >
> > Many thanks for your reply, Radim.
> >
> > Perhaps I should first focus on dglib cache and not the algorithm
> > used.  I have also seen your email:
> >  http://grass.itc.it/pipermail/grassuser/2003-November/010745.html
> >
> > Do you know how I can enable the cache to try it?  I tried just
> > uncommenting this line in Vect_net_build_graph ( in
> > lib/vector/Vlib/net.c )  :
> >
> >   dglInitializeSPCache( gr, &(Map->spCache) );
>
> OK, but also lines 412 and 415, i am not sure if more.
>
> > ...but that didnt change my run times significantly.
>
> The cache has only efect in modules which calculates
> matrices of costs for sets of nodes and that is not
> case for v.net.path. Try the difference with
> v.net.iso, v.net.salesman, v.net.alloc and v.net.steiner.
>
> > Do you know more about the bug?  I have seen the small note in
> > lib/vector/dglib/BUGS about it.  But I cannot tell, is it just an
> > implementation detail bug, or a deeper theoretical problem.
>
> I believe that it is just a bug in implementation. The cache cannot be
> anything complex, it just saves the state reached in previous
> search. Were you able to reproduce the BUG1?
> That could be possible also with d.path but I am  not sure.
>
> Radim

As you said, I was able to see the effect of enabling the cache on
v.net.iso (very dramatic difference), but not on v.net.path.  From
running under gdb I could see that v.net.iso calls the dijkstra
function very very many times, and v.net.path just twice.

I also finally found the dijkstra functions which I was confused about
due to the unusual function naming in sp-template.c

This means fixing the cache bug will not help my primary interest of
speeding up v.net.path.   But v.net.iso might be interesting to me as
well.

I was not able to reproduce BUG1.  Ideally we would have a simple test
case which illustrates the bug.  Does such a case exist?  Otherwise I
will try to make one.  Maybe I should write to Roberto...

-Robin