[GRASS-dev] spanning tree and steiner tree problems?

[Michael Barton]

Then perhaps this spanning tree and Steiner net is different from what it used to do and what I've seen for a definition.

By my understanding (and my recollection of previous behavior in 6.3), a Steiner tree and spanning net should produce similar, if not identical graphs (Steiner net is a type of spanning tree). They should be connecting all nodes via a set of shortest paths. That is, for 4 nodes, there should be a total of 4+3+2+1 = 10 total paths, not the complex set of paths in your graphic (same as mine BTW). 

If these are not connecting all nodes via a set of minimal paths, what ARE they doing? 

Michael
______________________________
C. Michael Barton 
Director, Center for Social Dynamics & Complexity
Professor of Anthropology, School of Human Evolution & Social Change
Arizona State University
Tempe, AZ  85287-2402
USA

voice: 	480-965-6262 (SHESC), 480-727-9746 (CSDC)
fax:          480-965-7671(SHESC), 480-727-0709 (CSDC)
www: 	http://csdc.asu.edu, http://shesc.asu.edu
		http://www.public.asu.edu/~cmbarton

On Oct 8, 2012, at 8:53 AM, Moritz Lennert <mlennert at club.worldonline.be> wrote:

> On 07/10/12 08:27, Michael Barton wrote:
>> Hi Moritz,
>> 
>> Thanks to your help, I now have been able to run through a number of the
>> vector network operations. Two that don't seem to work are v.net.steiner
>> and v.net.spanningtree. But perhaps I am not doing it right.
>> 
>> Here is the setup using Highschools from the schools_wake vector and
>> streets_wake in the sc_08 demo data set.
>> 
>> First I connect highschools (previously extracted from schools_wake)
>> with the streets.
>> 
>> v.net <http://v.net> --overwrite input=streets_wake at grass7vect_sqlite
>> points=highschools at spatialtech2012 output=hs_net operation=connect
>> alayer=1 nlayer=2 thresh=200
> 
> 
> Are you sure there are highschools connected to the network (is this the schools_wake layer) ?
> 
> 
>> When I run v.net.stiener, it gives no error but doesn't create anything
>> either. Here is the command:
>> 
>> v.net.steiner input=hs_net at spatialtech2012 output=hs_steiner type=line
>> alayer=1 nlayer=2
>> tcats=4,7,11,12,37,49,50,65,67,69,77,83,91,101,103,115,117,138,153,158,164,165
> 
> When I try to do this on the entire streets_wake network, my machine immediately goes into disk swap and I don't have the time to wait and see if and when it finishes. However, when I cut out a small part of the network, it works as expected.
> 
>> 
>> When I run v.net.spanningtree, I do get results, but it is a complex
>> street network that is almost the same as the original street network.
>> Here is the command I am using:
>> 
>> v.net.spanningtree --overwrite input=hs_net at spatialtech2012
>> output=hs_spanningtree alayer=1 nlayer=2
> 
> See the attached image for results I get with the streets_wake layer. In black the original layer and in green the spanning tree. As you can see it seems to have worked.
> 
> It seems that this module ignores any nodes you might have on layer 2 and just happily finds the minimum spanning tree of the entire network, using the intersections as nodes. I'm no expert on spanning trees and cannot say whether this is expected behavior or a bug.
> 
> Moritz
> 
> 
> <spanning.png>