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

[Michael Barton]

Thanks Moritz,

See below.

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 9, 2012, at 12:18 AM, Moritz Lennert <mlennert at club.worldonline.be>
 wrote:

> On 08/10/12 18:29, Michael Barton wrote:
>> 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?
> 
> The way I understand it:
> 
> - Spanning tree does not take into account specific nodes you add, but uses all vertices of the network. This is why you cannot specify specific nodes.

That would explain the output. But this is at variance from all other GRASS vector network operations. They all recognize ONLY vertices defined as nodes. Connecting ALL vertices in the network makes v.net.spanningtree pretty useless for network analysis. I can't help but think that this is in error here. 

> 
> - Steiner network uses only the specific nodes you provide. This is why you have the tcats options which allows you specify which nodes you want to use.

Yes. But it produces nothing on my computer. It runs, finishes, gives no error, and produces nothing. I just tried it again with 3 nodes. Nothing. So this at least is a bug. I'll file a report. Do you actually get a map from v.net.steiner?

> 
> And here's what wikipedia has to say:
> 
> "The Steiner tree problem is superficially similar to the minimum spanning tree problem: given a set V of points (vertices), interconnect them by a network (graph) of shortest length, where the length is the sum of the lengths of all edges. The difference between the Steiner tree problem and the minimum spanning tree problem is that, in the Steiner tree problem, extra intermediate vertices and edges may be added to the graph in order to reduce the length of the spanning tree. These new vertices introduced to decrease the total length of connection are known as Steiner points or Steiner vertices. It has been proved that the resulting connection is a tree, known as the Steiner tree. There may be several Steiner trees for a given set of initial vertices."
> (http://en.wikipedia.org/wiki/Steiner_tree_problem)

Yes. This is where I looked too. Good to have Wikipedia.

Michael

> 
> Moritz
>