cache bug in DGLib

[martinl]

Fix outstanding bug DGLib ...

See

​http://www.nabble.com/-GRASS5--Grass-5.1%27s-Directed-Graph-Library-CVS-snapshot-td8581688.html#a8581693

​http://www.nabble.com/v.net.path-td4210952.html#a4217671

​http://www.nabble.com/-GRASS5--dgtable-vector-library-td8582331.html#a8582342

Martin

[neteler]

See also ​http://trac.osgeo.org/grass/browser/grass/trunk/lib/vector/dglib/BUGS

[mmetz]

BUG1 fixed in trunk r36109 and devbr6 r36110.

Cache not yet enabled again in Vlib, neither trunk nor devbr6.

[mmetz]

dglib cache back to life in trunk r36113 and devbr6 r36114

testing is very welcome!

[mmetz]

Leaving ticket open because of BUG2

IMHO BUG2 is nearly impossible to fix without the help of Roberto Micarelli. At least for me the code is too cryptic.

[mlennert]

Replying to mmetz:

dglib cache back to life in trunk r36113 and devbr6 r36114

testing is very welcome!

Wow !! Just tried v.net.alloc and v.net.iso on streets_wake and schools of the nc_spm_06 demo data and it finishes in seconds, instead of running the entire night without coming to a result ! Still need to look at the actual results more in detail (look good at rough glance). Also ran a few v.net.path's and everything seems fine.

So, already a very loud horray for this fix which completely changes the usability of network analysis in GRASS !!

Concerning BUG2: Maybe we could think of some test cases ?

Moritz

[mmetz]

Replying to mlennert:

Replying to mmetz:

dglib cache back to life in trunk r36113 and devbr6 r36114

testing is very welcome!

Still need to look at the actual results more in detail (look good at rough glance). Also ran a few v.net.path's and everything seems fine.

The critical values are the costs returned by Vect_net_shortest_path(). I did my testing by inserting

fprintf(stdout, "%f\n", cost);

e.g. in v.net.iso/main.c line 254 and v.net.alloc/main.c line 214

then with cache enabled: v.net.iso >costs.cache, similar for cache disabled

I have added comments in lib/vector/Vlib/net.c explaining how to disable/enable the cache. The comments and relevant code are in lines 489 - 504. Note that there is no need to comment out line 436.

Concerning BUG2: Maybe we could think of some test cases ?

For BUG1, I created a test vector as described in dglib/BUGS. It should not be too difficult to create a test vector for BUG2, but unfortunately I have not the faintest idea where to start poking around in dglib. I really tried to understand where and how the arcs are inserted, and by now I think I'm not that bad in understanding source code, but this is beyond me. You're welcome to get your hands dirty with dglib yourself:-)

Markus M

[neteler]

Since cache is enabled in >= 6.4 (thanks for the important fix), can we close this ticket?

Markus

[mmetz]

Closing ticket, opening new ticket for BUG2.

[huhabla]

It seems to me that this bug still exists in the release version of grass 6.

v.net.path produces wrong results on my 64Bit SUSE 11.2 system in case the cache is enabled.

You can reproduce the error using the following script within the spearfish location:

g.region vect=roads
d.mon start=x0
d.erase
g.copy vect=roads,roads_path --o
v.db.addcol roads_path col="forward double precision, backward double precision"

# define traveling costs as inverse of speed limit:
v.db.update roads_path col=forward val=1/50
v.db.update roads_path col=backward val=1/50
v.db.update roads_path col=forward val=1/75 where="label='interstate'"
v.db.update roads_path col=backward val=1/75 where="label='interstate'"
v.db.update roads_path col=forward val=1/5 where="label='unimproved road'"
v.db.update roads_path col=backward val=1/5 where="label='unimproved road'"
v.db.update roads_path col=forward val=1/25 where="label='light-duty road, improved surface'"
v.db.update roads_path col=backward val=1/25 where="label='light-duty road, improved surface'"
v.db.select roads_path

#    cat      x                y               x               y
echo "1 601241.63900415 4914234.39834025 592750.64315353 4925991.16182573" > /tmp/input.txt
echo "2 601241.63900415 4914234.39834025 595808.58921162 4926703.69294606" >> /tmp/input.txt
echo "3 601241.63900415 4914234.39834025 604507.406639 4915125.06224066" >> /tmp/input.txt
echo "4 601241.63900415 4914234.39834025 591206.82572614 4919103.36099585" >> /tmp/input.txt
echo "5 601241.63900415 4914234.39834025 590791.18257261 4926614.62655602" >> /tmp/input.txt
echo "6 601241.63900415 4914234.39834025 591088.07053942 4927119.33609959" >> /tmp/input.txt
echo "7 601241.63900415 4914234.39834025 596194.54356846 4917322.03319502" >> /tmp/input.txt
echo "8 601241.63900415 4914234.39834025 600172.84232365 4925575.5186722" >> /tmp/input.txt
echo "9 601241.63900415 4914234.39834025 605041.80497925 4920736.24481328" >> /tmp/input.txt
echo "10 601241.63900415 4914234.39834025 599074.35684647 4914946.92946058" >> /tmp/input.txt
echo "11 601241.63900415 4914234.39834025 595452.32365145 4920676.86721992" >> /tmp/input.txt
echo "12 601241.63900415 4914234.39834025 608277.88381743 4924269.21161826" >> /tmp/input.txt

v.net.path roads_path afcol=forward abcol=backward out=mypath type=line dmax=50 file=/tmp/input.txt --o

d.vect map=roads_path@user1 color=255:0:0 lcolor=0:0:0 fcolor=170:170:170 display=shape type=point,line,boundary,area icon=basic/circle size=5 width=4 layer=1 lsize=8 xref=left yref=center llayer=1

d.vect map=mypath@user1 color=0:0:0 lcolor=0:0:0 fcolor=170:170:170 display=shape type=point,line,boundary,area icon=basic/circle size=5 width=2 layer=1 lsize=8 xref=left yref=center llayer=1

Screenshot is attached.

Disabling the caching mechanism in Vlib/net.c solves the problem:

grass64_release/lib/vector> svn diff
Index: Vlib/net.c
===================================================================
--- Vlib/net.c  (Revision 43825)
+++ Vlib/net.c  (Arbeitskopie)
@@ -486,22 +486,22 @@

     pclip = NULL;
     if (List != NULL) {
-       nRet =
+       /*nRet =
            dglShortestPath(&(Map->graph), &pSPReport, (dglInt32_t) from,
                            (dglInt32_t) to, clipper, pclip, &(Map->spCache));
-       /* comment out above and uncomment below to debug dglib cache */
-       /* nRet =
+       comment out above and uncomment below to debug dglib cache */
+        nRet =
            dglShortestPath(&(Map->graph), &pSPReport, (dglInt32_t) from,
-                           (dglInt32_t) to, clipper, pclip, NULL); */
+                           (dglInt32_t) to, clipper, pclip, NULL);
     }
     else {
-       nRet =
+       /*nRet =
            dglShortestDistance(&(Map->graph), &nDistance, (dglInt32_t) from,
                                (dglInt32_t) to, clipper, pclip, &(Map->spCache));
-       /* comment out above and uncomment below to debug dglib cache */
-       /* nRet =
+        comment out above and uncomment below to debug dglib cache */
+       nRet =
            dglShortestDistance(&(Map->graph), &nDistance, (dglInt32_t) from,
-                               (dglInt32_t) to, clipper, pclip, NULL); */
+                               (dglInt32_t) to, clipper, pclip, NULL);
     }

     if (nRet == 0) {

[mmetz]

Replying to huhabla:

It seems to me that this bug still exists in the release version of grass 6.

v.net.path produces wrong results on my 64Bit SUSE 11.2 system in case the cache is enabled.

I could reproduce the wrong results and have disabled the dglib cache in 6.4.1. There is a new fix for the dglib cache in trunk and devbr6 (r43857 and r43860, respectively), plus some added documentation about how (I think that) the cache works.

Markus M

[huhabla]

Thanks a lot for this patch and the documentation Martin. It works for me with trunk and devbr6 using the speafish dataset.

I will test it again with a huge dataset to see if it's stable.

Can the changes be back ported to milestone 6.4.1?

Soeren

[mmetz]

Replying to huhabla:

I will test it again with a huge dataset to see if it's stable.

Can the changes be back ported to milestone 6.4.1?

After some more testing, yes. It would be great to have fast vector network analysis tools in 6.4.1 that produce accurate results.

Markus M

[huhabla]

I have tested v.net.path using a dataset with 460000 lines, one start point and 100 end points. It works quite fast (<5min) and the result seems to be correct. Screenshot is attached. IMHO back porting to 6.4.1 would be greatly appreciated.

Soeren

[huhabla]

correct result of v.net.path

[mmetz]

Replying to huhabla:

I have tested v.net.path using a dataset with 460000 lines, one start point and 100 end points. It works quite fast (<5min) and the result seems to be correct. Screenshot is attached. IMHO back porting to 6.4.1 would be greatly appreciated.

Thanks for testing!

Would it be asked too much to do the same test with the cache disabled and compare results? I am aware that this might take some time, e.g. running overnight.

Also, with cache enabled it would be great if you could design a test where you recover a path to a given point and in the very next step recover a path from the same starting point but the end point must be exactly one line (edge) farther away from the previous end point. First, this second end point must be reachable, second, the shortest path to this second end point should go through the previous end point, unless there is a shorter path avoiding the previous end point. I have done that with a small test vector that should represent all sorts of special cases targeting BUG1 and BUG2 but I might have overlooked something.

Markus M

[mmetz]

Replying to mmetz:

Also, with cache enabled it would be great if you could design a test where you recover a path to a given point and in the very next step recover a path from the same starting point but the end point must be exactly one line (edge) farther away from the previous end point. First, this second end point must be reachable, second, the shortest path to this second end point should go through the previous end point, unless there is a shorter path avoiding the previous end point. I have done that with a small test vector that should represent all sorts of special cases targeting BUG1 and BUG2 but I might have overlooked something.

Done with OpenStreetMap roads, the cache is now robust, results are correct. BTW, time to update the documentation: when many shortest paths or distances are to be calculated from the same starting point, v.net.path is fastest if the (estimated) longest path/distance is calculated first and the shorter paths/distances are extracted later (chances are good that they are now already known).

Markus M

[huhabla]

I have tested v.net.path with a large dataset (460000 lines and 100 check points) with and without cache support. The results are identical. Computing without cache enabled needs twice as long as with cache enabled, here the bash terminal output:

##############################################################################
########################## Cache enabled benchmark ###########################
##############################################################################

GRASS 6.5.svn (Niedersachsen_Lambert):~/grassdata/Niedersachsen_Lambert > v.info test
 +----------------------------------------------------------------------------+
 | Layer:           test                                                      |
 | Mapset:          PERMANENT                                                 |
 | Location:        Niedersachsen_Lambert                                     |
 | Database:        /home/soeren/grassdata                                    |
 | Title:                                                                     |
 | Map scale:       1:1                                                       |
 | Map format:      native                                                    |
 | Name of creator: institut                                                  |
 | Organization:                                                              |
 | Source date:     Tue Oct 05 09:42:49 2010                                  |
 |----------------------------------------------------------------------------|
 |   Type of Map:  vector (level: 2)                                          |
 |                                                                            |
 |   Number of points:       0               Number of areas:      0          |
 |   Number of lines:        464452          Number of islands:    0          |
 |   Number of boundaries:   0               Number of faces:      0          |
 |   Number of centroids:    0               Number of kernels:    0          |
 |                                                                            |
 |   Map is 3D:              No                                               |
 |   Number of dblinks:      1                                                |
 |                                                                            |
 |         Projection: x,y                                                    |
 |               N:      2658319.4974    S:      2365859.4479                 |
 |               E:         108601.19    W:      -222120.0652                 |
 |                                                                            |
 |   Digitization threshold: 0                                                |
 |   Comments:                                                                |
 |                                                                            |
 +----------------------------------------------------------------------------+


GRASS 6.5.svn (Niedersachsen_Lambert):~/grassdata/Niedersachsen_Lambert > time v.net.path input=test output=test_paths_100_cache_enabled type=line afcolumn=t_time_min file=NS_Sources_SinksPath_test.txt --o
Building graph...
Registering arcs...
 100%
Flattening the graph...
Graph was built
 100%
WARNING: Point -217249.204900,2624762.857300 is not reachable from point
         -27264.284444,2373360.000000
WARNING: Point 25376.264700,2602749.415200 is not reachable from point
         -27264.284444,2373360.000000
WARNING: Point -130178.530600,2612861.471700 is not reachable from point
         -27264.284444,2373360.000000
WARNING: 3 destination(s) unreachable (including points out of threshold)
Building topology for vector map <test_paths_100_cache_enabled>...
Registering primitives...
97 primitives registered
106646 vertices registered
Building areas...
 100%
0 areas built
0 isles built
Attaching islands...
Attaching centroids...
 100%
Number of nodes: 98
Number of primitives: 97
Number of points: 0
Number of lines: 97
Number of boundaries: 0
Number of centroids: 0
Number of areas: 0
Number of isles: 0

real    3m16.618s
user    3m5.422s
sys     0m8.607s

##############################################################################
########################## Cache disabled benchmark ##########################
##############################################################################

GRASS 6.5.svn (Niedersachsen_Lambert):~/grassdata/Niedersachsen_Lambert > time v.net.path input=test output=test_paths_100_cache_disabled type=line afcolumn=t_time_min file=NS_Sources_SinksPath_test.txt --o
Building graph...
Registering arcs...
 100%
Flattening the graph...
Graph was built
 100%
WARNING: Point -217249.204900,2624762.857300 is not reachable from point
         -27264.284444,2373360.000000
WARNING: Point 25376.264700,2602749.415200 is not reachable from point
         -27264.284444,2373360.000000
WARNING: Point -130178.530600,2612861.471700 is not reachable from point
         -27264.284444,2373360.000000
WARNING: 3 destination(s) unreachable (including points out of threshold)
Building topology for vector map <test_paths_100_cache_disabled>...
Registering primitives...
97 primitives registered
106646 vertices registered
Building areas...
 100%
0 areas built
0 isles built
Attaching islands...
Attaching centroids...
 100%
Number of nodes: 98
Number of primitives: 97
Number of points: 0
Number of lines: 97
Number of boundaries: 0
Number of centroids: 0
Number of areas: 0
Number of isles: 0

real    6m12.256s
user    6m1.214s
sys     0m10.338s

Here is a spearfish example which (hopefully) generates a dataset following the suggestion of Markus:

g.region vect=roads
d.mon start=x0
d.erase
g.copy vect=roads,roads_path --o
v.db.addcol roads_path col="forward double precision, backward double precision"

# define traveling costs as inverse of speed limit:
v.db.update roads_path col=forward val=1/50
v.db.update roads_path col=backward val=1/50
v.db.update roads_path col=forward val=1/75 where="label='interstate'"
v.db.update roads_path col=backward val=1/75 where="label='interstate'"
v.db.update roads_path col=forward val=1/5 where="label='unimproved road'"
v.db.update roads_path col=backward val=1/5 where="label='unimproved road'"
v.db.update roads_path col=forward val=1/25 where="label='light-duty road, improved surface'"
v.db.update roads_path col=backward val=1/25 where="label='light-duty road, improved surface'"
v.db.select roads_path

#    cat      x                y               x               y
echo "1 601241.63900415 4914234.39834025 592750.64315353 4925991.16182573" > /tmp/input.txt
echo "2 601241.63900415 4914234.39834025 591866.59045237 4926913.56316479" >> /tmp/input.txt
echo "3 601241.63900415 4914234.39834025 595808.58921162 4926703.69294606" >> /tmp/input.txt
echo "4 601241.63900415 4914234.39834025 596038.555971 4926823.06308527" >> /tmp/input.txt
echo "5 601241.63900415 4914234.39834025 604507.406639 4915125.06224066" >> /tmp/input.txt
echo "6 601241.63900415 4914234.39834025 605057.73125402 4915511.07087975" >> /tmp/input.txt
echo "9 601241.63900415 4914234.39834025 590791.18257261 4926614.62655602" >> /tmp/input.txt
echo "10 601241.63900415 4914234.39834025 590761.78330618 4926783.71536375" >> /tmp/input.txt

v.net.path roads_path afcol=forward abcol=backward out=mypath type=line dmax=50 file=/tmp/input.txt --o

d.vect map=roads_path@user1 color=255:0:0 lcolor=0:0:0 fcolor=170:170:170 display=shape type=point,line,boundary,area icon=basic/circle size=5 width=4 layer=1 lsize=8 xref=left yref=center llayer=1

d.vect map=mypath@user1 color=0:0:0 lcolor=0:0:0 fcolor=170:170:170 display=shape type=point,line,boundary,area icon=basic/circle size=5 width=2 layer=1 lsize=8 xref=left yref=center llayer=1

Results are correct.

Well done Markus!!!

I think we can close this ticked when the changes are backported to 6.4.1.

[mmetz]

Replying to huhabla:

I have tested v.net.path with a large dataset (460000 lines and 100 check points) with and without cache support. The results are identical.

Great, thanks for testing!

I think we can close this ticked when the changes are backported to 6.4.1.

Done in r44066 and r44067. Closing ticket.

Markus M