[GRASS5] dgtable vector library

[Radim Blazek]

On Tuesday 09 September 2003 03:31, Greg Sepesi wrote:
> 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.

I had the same problem, it is too complicated, this is realy the problem.

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

Roberto definitely had reasons for that, once he explained it to
me but I partially did not understand and partially forgot.
If I recall well FLAT was used to store graph on the disk while TREE 
for computatio. Read FLAT and convert to TREE is faster than build 
new TREE? Is it possible? (Not used in GRASS.)

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

Very important for most v.net* is 'short path cache (SPC)'. It means that
when it is necessary to calculate SP from one node to all/many others, 
whole process is not repeated for each destination node and current 
state of graph is stored until starting point is changed. 
Performance with SPC is many times higher! Unfortunately there is 
a bug in SPC in dglib. Is it SPC available in gdtable or could be implemented?


> I'm using dgtable in a couple projects.  If there's interest in using it
> in GRASS ver >= 5.1, I'll add the appropriate formatting and headers.

There is interest, but I don't have time to work on that, do you think
that you could write alternative Vlib/net.c, put dgtable to GRASS CVS 
and make it alternative graph library (conditional compilation)?
Later we can switch to dgtable as default.

Radim