[GRASSLIST:1723] Re: GRASS 5.7: Vector networking tutorial

[Greg Sepesi]

Radim Blazek wrote:
> 
> On Sunday 09 November 2003 23:16, Greg Sepesi wrote:
> > Here are the results of running dgtable (i.e., Directed Graph
> > implemented with lookup tables) ShortestPath variants on the FRIDA
> > data.  The screen dumps come from a Windows application in which I'm
> > using dgtable to conflate vector maps.  I'm also using dgtable in the
> > creation of vector maps for handhelds running Palm OS.  I believe the
> > last Shortest Path variant (i.e., points to graph) is equivalent to the
> > reportedly slow v.net.iso function.
> 
> ...
> 
> > shortest path variant: points to graph
> > dgtable function:      FindShortestPathMultipleStartingPoints (with
> > destination argument = 0)
> > example application:   planning location of distribution warehouses
> > screen dump:           http://www.eduneer.com/dgtable/sp11.png
> > execution time:        0.44 seconds
> > comments:              green circle represents starting point
> >                        green lines are middle third of cost range
> >                        yellow lines are final third of cost range
> >                        red lines are not reachable (as defined by the
> 
> CPU?
> 
> On 1.5GHz processor v.net.iso takes
> 9m 39.372s for current cvs version and
>     1.867s if cache is enabled
> In this case (this data) the result is the same, but there is a bug in cache,
> which may cause bad results in certain cases.
> The time includes writing vector and building topology, v.build on the result
> takes 0.988s.
> I think that 1.867s is not bad, the problem is the bug in cache.
> 
> Radim

Hi Radim,

I ran the tests on a modestly equipped PC with a 500 MHz Pentium II
processor.

The dglib cache would be helpful, but maybe not enough.  Deeply nested
(i.e., frequently called) in the dglib algorithms are calls to avl_find
which has a running time proportional to log V (where V is the number of
vertices in the graph).  In dgtable, vertex information is obtained from
a lookup table rather than a balanced tree so the frequent searching is
avoided.  It isn't clear to me that the dglib cache (even if it were
fixed) would avoid the frequent searching.  The FRIDA dataset is
relatively small.  It would be interesting to also perform timing tests
on a dataset that is 100 times larger.

Greg