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

GRASS GIS GRASS GIS developer
1

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 --overwrite input=streets_wake@grass7vect_sqlite points=highschools@spatialtech2012 output=hs_net operation=connect alayer=1 nlayer=2 thresh=200

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@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 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@spatialtech2012 output=hs_spanningtree alayer=1 nlayer=2

Any suggestions?

Michael

C. Michael Barton
Director, Center for Social Dynamics & Complexity
Professor of Anthropology, School of Human Evolution & Social Change
Arizona State University

voice: 480-965-6262 (SHESC), 480-727-9746 (CSDC)
fax: 480-965-7671 (SHESC), 480-727-0709 (CSDC)

www: http://www.public.asu.edu/~cmbarton, http://csdc.asu.edu

2

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@grass7vect_sqlite
points=highschools@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@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@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

(attachments)

spanning.png

3

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@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@grass7vect_sqlite
points=highschools@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@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@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>

4

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.

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

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)

Moritz

5

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@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."
(Steiner tree problem - Wikipedia)

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

Michael

Moritz

6

On 09/10/12 19:13, Michael Barton wrote:

On Oct 9, 2012, at 12:18 AM, Moritz
Lennert<mlennert@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

(attachments)

steiner.png