[GRASS5] GRASS 5.1 vectors ... trees .vs. tables

Greg Sepesi sepesi at eduneer.com
Fri Jun 20 17:47:43 EDT 2003


Six weeks ago I started using GRASS, with an interest in developing code
to conflate maps (in particular, getting the label information from
TIGER maps into USGS DLG maps).  I've been using GRASS 5.0, and have
briefly experimented with the GRASS 5.1 dglib vector library.  A bit
overwhelmed by dglib, I decided to augment a vector library I had
previously written.  The resulting vector library, which I've called
dgtable, presently implements the common variants of the priority first
search (i.e., breadth first search, depth first search, minimum spanning
tree, and shortest path algorithms) as described by Sedgewick.  I
believe dglib is designed to do the same.

Comparing the two vector libraries, the most obvious difference is
size.  The files and line counts are listed below.

dglib files                  lines
===========                  =====
avl.c                       :  891
avl.h                       :  116
dgl.h                       :    8
edgemgmt-template.c         :  404
graph.c                     : 1703
graph.h                     :  547
graph_v1.c                  :  414
graph_v1.h                  :  273
graph_v2.c                  :  418
graph_v2.h                  :  279
heap.c                      :  179
heap.h                      :   92
helpers.c                   :  155
helpers.h                   :   38
misc-template.c             :  651
nodemgmt-template.c         :  443
span-template.c             :  423
sp-template.c               :  567
tavl.c                      :  982
tavl.h                      :  119
tree.c                      :  351
tree.h                      :  172
type.h                      :   72
v1-defs.h                   :  183
v2-defs.h                   :  186

TOTAL LINES:                : 9666
AVG CHARS / LINE:           : 20.4


dgtable files                lines
=============                =====
dgtable.c                   : 1324
dgtable.h                   :  132

TOTAL LINES:                : 1456
AVG CHARS / LINE:           : 19.4

 
I believe code that manipulates tables is generally a little more
concise than code that manipulates trees (AVL trees in the case of
dglib).  So that might account for some of the difference.  By the way,
from a performance perspective I'm still curious as to why dglib stores
its graph data in trees.  Granted AVL trees are balanced and therefore
have a better worst-case performance than some other trees, but the
access of vertices is deeply nested in graph algorithms and it seems
that the added complexity of accessing one of V vertices in a tree
(i.e., O(logV) as opposed to O(1) for a table) would result in
unnecessarily sluggish performance.  On the other hand, the graphics
hardware I've worked on have generally been strapped for speed.  It is
interesting to note that dglib has some large macros, which I assume are
an attempt to gain some speed by executing functions in-line.

Another reason for the difference in library size is due to dglib
allowing different data structure modes.  The dglib data structure can
be either FLAT or TREE.  I believe the intent for the dglib FLAT data
structure is primarily for serializing the TREE structure, which is the
structure required by most of dglib's graph algorithms.  However I don't
understand why its TREE data structure cannot be filled/emptied
directly.  

And finally, probably no small part of the difference in library size is
due to functionality that I overlooked in dglib and didn't implement in
dgtable.

I apologize for joining the game late.  Is the GRASS 5.1 vector
development too far along to consider using tables instead of trees?

Greg




More information about the grass-dev mailing list