[GRASS5] dgtable vector library

[Greg Sepesi]

Hello,

I have updated dgtable at

	http://www.eduneer.com/gad/dg_src_0.1.tar.gz   (847848 bytes)

The new version 

   - has GPL notice in source files
   - has DirectedGraphStateType so dgtable can be called from multiple
threads
   - implements shortest path search continuation
   - demonstrates shortest path in dgdemo.out
   - contains road data for shortest path demonstration

The new version does not have

   - the extraneous Visual C++ files I accidently included before
   - the fast Delaunay triangulation (#ifdef'd out because I have not
finished debugging it)

I looked at Vlib/net.c, but it will probably be several months before I
can switch to GRASS ver >= 5.1 and offer help with GRASS
integration/maintenance.  Meanwhile I will support dgtable by responding
to questions and problems or writing documentation.  Hopefully some part
of dgtable will be useful to GRASS.

Greg

P.S., the README is listed below.

- - -

README
14 sep 2003
Greg Sepesi (sepesi at eduneer.com)


Definition
----------
dgtable:     a directed graph structure based upon lookup tables

Directory Contents
------------------
dg:          test data
dg/demo:     test code for exercising dgtable's graphics, search, and
comp. geometry algorithms
dg/dgbezier: least squared error Bezier curve fitting (using Graphics
Gems, ISBN:0122861663)
dg/dgrtree:  R-Tree code (using Toni Gutman, Michael Stonebrakier, and
Daniel Green's work)
dg/dgtable:  dgtable structure and code

Demonstration
-------------
To run the dgtable demonstration, go to the dg/demo directory and
execute

> make
> ./dgdemo.out

Expected screen output:

USING HYPSOGRAPHY DATA
building directed graph ...
concatenating paths into a second directed graph ...
   1148 paths in 620 connected components before concatenation.
   730 paths in 620 connected components after.
writing and reading second directed graph ...
   3176780 bytes out; 3176780 bytes in
performing some computational geometry on points in path 5 (i.e.,
"140.00") ...
   140 points in path; 11 points in its 2D convex hull.
   160 triangles in its delaunay triangulation.
fitting Bezier curves through concatenated paths ...
   85641 points in 730 paths before curve fitting.
   66581 points in 730 paths after.
 
USING PRIMARY ROAD DATA
building directed graph ...
concatenating paths into a second directed graph ...
   516 paths in 1 connected component before concatenation.
   27 paths in 1 connected component after.
calculating shortest path ...
   from intersection of Boonsboro Rd and Lynchburg Expy
   to intersection of Memorial Ave and Oakley Ave
   shortest path visits 81 vertices (different source, new search)
 
   from intersection of Boonsboro Rd and Lynchburg Expy
   to intersection of Campbell Ave and Richmond Hwy
   shortest path visits 135 vertices (same source, continued search)
 
   from intersection of Forest Rd and Lakeside Dr
   to intersection of Campbell Ave and Richmond Hwy
   shortest path visits 104 vertices (different source, new search)
 
   from intersection of Forest Rd and Lakeside Dr
   to intersection of Memorial Ave and Oakley Ave
   shortest path visits 42 vertices (same source, no search)
 
fitting Bezier curves through concatenated paths ...
   706 points in 27 paths before curve fitting.
   253 points in 27 paths after.

Expected file output (see dg/demo/dgdemo.c for context of data dumps): 

trash.convexhull.txt   trash.path2.dg        trash.path.txt 
trash.sp13.txt
trash.curve3.road.svg  trash.path2.road.txt  trash.sp02.txt
trash.curve3.svg       trash.path2.txt       trash.sp03.txt
trash.delaunay.txt     trash.path.road.txt   trash.sp12.txt


Design Intent: a simpler dglib
------------------------------
Looking for an open-source, stand-alone directed graph library for a
Palm OS application, the GRASS 5.1 dglib vector library seemed ideal
even though there was work to be done on a few of dglib's modes. 
Unfortunately after a couple days and several emails, I was not able to
understand enough of dglib to work on it.  Two questions remained.

   Why use a tree for vertex storage?
   Why use two modes for RAM storage (i.e., FLAT and TREE)?

I then started writing dgtable using lookup tables instead of balanced
trees to store vertices, and using just one mode for RAM storage.

Implementation Results: simpler in some cases, but not in others
----------------------------------------------------------------
dgtable benefits from avoiding multiple modes.  dgtable has no need for
a cache mode because it already efficiently accesses vertices in lookup
tables.  dgtable also has only one storage mode and it is analogous to
dglib's FLAT mode.

On the other hand, the lookup tables of dgtable are not as dynamic as
the trees of dglib and this could be a big expense if an application's
directed graph frequently changes.  I suppose a good compromise would be
to change table size in blocks, but I haven't implemented that yet.

Design
------ 
Referring to dg/dgtable/dgtable.h, a dgtable directed graph consists of 

   - a table of paths (e.g., connected points along a road)
   - a table of vertices (i.e., unique path points)
   - a table of intersections (i.e., non-unique path points)
   - an R-Tree table that provides a spatial link to each 3 point
subsection of each path

Presently, the dgtable library applies this data structure in the
following directed graph algorithms (see dg/dgtable/dgsearch.c):

   - depth first search (uni- or bi-directional paths)
   - breadth first search (uni- or bi-directional paths)
   - minimum spanning tree (uni- or bi-directional paths)
   - shortest path search (uni- or bi-directional paths),

the following computational geometry algorithms (see
dg/dgtable/dggeo.c):

   - 2D convex hull
   - 2D Delaunay triangulation,

and the following graphics algorithm (see dg/dgbezier):

   - least squared error Bezier curve fit.