[GRASS5] dgtable vector library

[Radim Blazek]

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.

> 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