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

[Moritz Lennert]

On 09/10/12 19:13, Michael Barton wrote:
> 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.

I have to admit I'm enough of a specialist on these question to judge 
that. CC'ing Daniel as the original author. Maybe he has something to say ?

>
>>
>> - 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?

I get memory alloc errors on my machine when trying to work on the 
entire streets_wake network, but I get it to work with a subnetwork:

g.region n=227106 s=222532 w=626211 e=633099
v.in.region out=region
v.select ain=streets_wake bin=region out=mystreets
v.select ain=schools_wake bin=region out=myschools
v.net mystreets points=myschools op=connect thresh=200 out=network
v.net.steiner in=network out=steiner_net tcats=1-150

See the attached image with the result.

Moritz

-------------- next part --------------
A non-text attachment was scrubbed...
Name: steiner.png
Type: image/png
Size: 34656 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/grass-dev/attachments/20121010/c4038447/attachment-0001.png>