[GRASS5] dgtable vector library

[Greg Sepesi]

Hi Radim,

Radim Blazek wrote:
> 
> On Wednesday 10 September 2003 15:40, Greg Sepesi wrote:
> > 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.
> 
> It should stop when the destination point is reached, keep the status
> and continue filling if new starting point is the same and destination is not yet
> reached.

That is a good idea for shortest path when it is frequently called. 
Just for my curiosity, how does GRASS use it?  As an implementation
note, the priority-first search algorithm also easily handles
disconnected subgraphs.  So if the starting point is the same and the
destination is not yet reached AND the subgraph connected to (i.e.,
reachable from) the starting point isn't already filled, keep filling. 
I'll have to think more about what it will take to implement a reentrant
status (as you suggest below).  I know it needs to include the dgtable
heap (i.e., priority queue, which is used in the shortest path algorithm
for storing/sorting the "visit fringe" vertices, which are the vertices
not yet filled but are neighboring a filled vertex) and the arrays it
uses for results (presently part of the vertex array).  

> 
> > 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 am not sure, but I think that in dglib all info about SP is stored in
> the structure separate from graph and this structure may be optionaly stored.
> It is important don't mix SP info with input graph, because then the same
> graph may be used for more threads at the same time. I think that it shoud be possible
> to extend v.net.path to server, wayting for requests from - to and
> returning list of arcs.
> 
> Radim

Yes I believe dglib stores results in their own tree.  Once I get a
reentrant status, I could add the ability to optionally save it to
disk.  This option provides a good debug/test point.  However is there a
need to read status?  Does dglib read as well as write its result trees?

Greg