[GRASS5] dgtable vector library

[Greg Sepesi]

Radim Blazek wrote:
> 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.)

Although writing the nodes to disk during a traversal of the TREE's
linked nodes would be simple, maybe the FLAT mode reduces file size.

> 
> >    - 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?

gdtable implements a O(V*log(V)) shortest path algorithm using the
priority-first-search described by Sedgewick (ISBN: 0201066734).  I
think of the algorithm as a terrain being filled by a water source at
the starting point.  The water flows to the lowest elevation (cost)
until it reaches the destination point.  Each vertex keeps track of the
direction (i.e., dad vertex) water flowed into it ... allowing
recreation of the path back to the source.  Presently the algorithm
stops when reaching the destination point, but it would be easy to "keep
filling" until covering the graph.  I'm not sure what the cache is in
'short path cache', but dgtable stores the dad vertex in dgtable's
vertex table so that it remains available (for recreating the path back
to the source) until another dgtable search algorithm is executed.

> 
> > 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.

I'll take a look at Vlib/net.c sometime this weekend.

Greg