[GRASS5] v.net.path

GRASS GIS GRASS GIS developer
1

Could anyone tell me if there have been any plans or developments for
v.net.path lately?

I have read this old thread on v.net.* implementation using dglib vs dgtable:

http://grass.itc.it/pipermail/grass5/2003-September/008673.html

...which suggests dglib is abandoned and maybe should be replaced by
dgtable. But the URL for dgtable no longer works and Google gives
nothing on it.

I would also like to know which algo is used for shortest path in
dgtable... In my understanding dijkstra's as used by dglib is terribly
inefficient for the shortest path problem, I think A* would be far
better here.

-Robin Chauhan

2

On 5/3/06, Robin Chauhan <robin.chauhan@gmail.com> wrote:

Could anyone tell me if there have been any plans or developments for
v.net.path lately?

I have read this old thread on v.net.* implementation using dglib vs dgtable:

http://grass.itc.it/pipermail/grass5/2003-September/008673.html

...which suggests dglib is abandoned and maybe should be replaced by
dgtable. But the URL for dgtable no longer works and Google gives
nothing on it.

I would also like to know which algo is used for shortest path in
dgtable... In my understanding dijkstra's as used by dglib is terribly
inefficient for the shortest path problem, I think A* would be far
better here.

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.

Radim

-Robin Chauhan

_______________________________________________
grass5 mailing list
grass5@grass.itc.it
http://grass.itc.it/mailman/listinfo/grass5

3

On 5/3/06, Radim Blazek <radim.blazek@gmail.com> wrote:

On 5/3/06, Robin Chauhan <robin.chauhan@gmail.com> wrote:
> Could anyone tell me if there have been any plans or developments for
> v.net.path lately?
>
> I have read this old thread on v.net.* implementation using dglib vs dgtable:
>
> http://grass.itc.it/pipermail/grass5/2003-September/008673.html
>
> ...which suggests dglib is abandoned and maybe should be replaced by
> dgtable. But the URL for dgtable no longer works and Google gives
> nothing on it.
>
> I would also like to know which algo is used for shortest path in
> dgtable... In my understanding dijkstra's as used by dglib is terribly
> inefficient for the shortest path problem, I think A* would be far
> better here.

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) );

...but that didnt change my run times significantly.

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.

-Robin

Radim

> -Robin Chauhan

4

On 5/3/06, Robin Chauhan <robin.chauhan@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

5

On 5/4/06, Radim Blazek <radim.blazek@gmail.com> wrote:

On 5/3/06, Robin Chauhan <robin.chauhan@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