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

[Greg Sepesi]

> Subject: [GRASSLIST:1590] Re: GRASS 5.7: Vector networking tutorial
> Date: Wed, 29 Oct 2003 09:08:09 +0100
> From: Markus Neteler <neteler at itc.it>
> To: GRASSLIST at baylor.edu
> 
> On Tue, Oct 28, 2003 at 02:19:01AM -0800, Maliheh wrote:
> > Hello all,
> > Thank you for everything!
> > Don't you think it's better to edit it in GRASS5.7:
> > Vector networking tutorial ?
> 
> It's already updated :-)
> 
> > and another really hard problem :
> >
> > v.net.iso input=schools_net output=schools_iso
> > ccats=200-201 costs=1000
> >
> > It goes into an infinite loop (16 hours)
> 
> It is probably (not sure) related to the disabled cache
> in DGLib (it was disabled due to a bug). So v.net.iso might
> deliver a result after 17 hours or 1 week.
> 
> Maybe the upcoming network library from Greg Sepesi is
> way faster?
> 
> Or you track down the bug in DGLib cache...
> 
> Markus Neteler

I still haven't looked at much GRASS source, but my understanding from
Radim is that GRASS 5.7 uses DGLib's shortest path algorithm a lot. 
Unlike longest path and traveling salesman algorithms, the shortest path
algorithm has a very efficient implementation, typically faster than a
sort.  To illustrate, I added some rough timing measurements to the
previously posted dgdemo application that demonstrates the dgtable
directed graph library.  Run on a modestly equipped 500 MHz Pentium II,
here is the dgdemo output:

- - -

USING HYPSOGRAPHY DATA
building directed graph ... 39.540 seconds
concatenating paths into a second directed graph ... 3.190 seconds
   1148 paths in 620 connected components before concatenation.
   727 paths in 620 connected components after.
writing and reading second directed graph ... 0.270 seconds
   3182040 bytes out; 3182040 bytes in
fitting Bezier curves through concatenated paths ... 11.870 seconds
   85631 points in 727 paths before curve fitting.
   66549 points in 727 paths after.

USING PRIMARY ROAD DATA
building directed graph ... 1.430 seconds
concatenating paths into a second directed graph ... 0.060 seconds
   516 paths in 1 connected component before concatenation.
   27 paths in 1 connected component after.
calculating shortest paths
   from intersection of Lynchburg Expy and Boonsboro Rd
   to intersection of Oakley Ave and Memorial Ave ... 0.000 seconds
   shortest path visits 81 vertices (different source, new search)

   from intersection of Lynchburg Expy and Boonsboro Rd
   to intersection of Richmond Hwy and Campbell Ave ... 0.000 seconds
   shortest path visits 135 vertices (same source, continued search)

   from intersection of Lakeside Dr and Forest Rd
   to intersection of Richmond Hwy and Campbell Ave ... 0.000 seconds
   shortest path visits 104 vertices (different source, new search)

   from intersection of Lakeside Dr and Forest Rd
   to intersection of Oakley Ave and Memorial Ave ... 0.000 seconds
   shortest path visits 42 vertices (same source, no search)

fitting Bezier curves through concatenated paths ... 0.060 seconds
   706 points in 27 paths before curve fitting.
   253 points in 27 paths after.

- - -

As you can see, most of the time is spent on building the directed
graphs but little is spent on calculating shortest paths.  It would be
interesting to know where the time is being spent by v.net.iso.

Greg