<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<title>GRASS GIS: v.net.steiner</title>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<link rel="stylesheet" href="grassdocs.css" type="text/css">
</head>
<body bgcolor="white">
<img src="grass_logo.png" alt="GRASS logo"><hr align=center size=6 noshade>
<h2>NAME</h2>
<em><b>v.net.steiner</b></em> - Create Steiner tree for the network and given terminals<BR>
Note that 'Minimum Steiner Tree' problem is NP-hard and heuristic algorithm is used in this module so the result may be sub optimal
<h2>KEYWORDS</h2>
vector, networking
<h2>SYNOPSIS</h2>
<b>v.net.steiner</b><br>
<b>v.net.steiner help</b><br>
<b>v.net.steiner</b> [-<b>g</b>] <b>input</b>=<em>name</em> <b>output</b>=<em>name</em> [<b>type</b>=<em>string</em>[,<i>string</i>,...]] [<b>alayer</b>=<em>integer</em>] [<b>nlayer</b>=<em>integer</em>] [<b>acolumn</b>=<em>string</em>] <b>tcats</b>=<em>range</em> [<b>nsp</b>=<em>integer</em>] [--<b>overwrite</b>] [--<b>verbose</b>] [--<b>quiet</b>]
<h3>Flags:</h3>
<DL>
<DT><b>-g</b></DT>
<DD>Use geodesic calculation for longitude-latitude locations</DD>
<DT><b>--overwrite</b></DT>
<DD>Allow output files to overwrite existing files</DD>
<DT><b>--verbose</b></DT>
<DD>Verbose module output</DD>
<DT><b>--quiet</b></DT>
<DD>Quiet module output</DD>
</DL>
<h3>Parameters:</h3>
<DL>
<DT><b>input</b>=<em>name</em></DT>
<DD>Name of input vector map</DD>
<DT><b>output</b>=<em>name</em></DT>
<DD>Name for output vector map</DD>
<DT><b>type</b>=<em>string[,<i>string</i>,...]</em></DT>
<DD>Type</DD>
<DD>Arc type</DD>
<DD>Options: <em>line,boundary</em></DD>
<DD>Default: <em>line,boundary</em></DD>
<DT><b>alayer</b>=<em>integer</em></DT>
<DD>Layer number</DD>
<DD>Arc layer</DD>
<DD>Default: <em>1</em></DD>
<DT><b>nlayer</b>=<em>integer</em></DT>
<DD>Layer number</DD>
<DD>Node layer (used for terminals)</DD>
<DD>Default: <em>2</em></DD>
<DT><b>acolumn</b>=<em>string</em></DT>
<DD>Arcs' cost column (for both directions)</DD>
<DT><b>tcats</b>=<em>range</em></DT>
<DD>Category values</DD>
<DD>Categories of points on terminals (layer is specified by nlayer)</DD>
<DT><b>nsp</b>=<em>integer</em></DT>
<DD>Number of steiner poins (-1 for all possible)</DD>
<DD>Default: <em>-1</em></DD>
</DL>
<h2>DESCRIPTION</h2>
<em>v.net.steiner</em> calculates the optimal connection of nodes on a
vector network.
<P>
A Steiner tree is used to calculate the minimum-cost vector network
connecting some number of end nodes in a network framework.
For example it could be used to find the path following a road system
which will minimize the amount of fibre optic cable needed to connect
a series of satellite offices.
<h2>EXAMPLE</h2>
Steiner tree for for 6 digitized nodes (Spearfish):
<div class="code"><pre>
g.copy vect=roads,myroads
v.db.addcol myroads col="cost double precision"
# define traveling costs as inverse of speed limit:
v.db.update myroads col=cost val=1/50
v.db.update myroads col=cost val=1/75 where="label='interstate'"
v.db.update myroads col=cost val=1/5 where="label='unimproved road'"
v.db.update myroads col=cost val=1/25 where="label='light-duty road, improved surface'"
v.db.select myroads
# we have 6 locations to allocate
echo "1|601653.5|4922869.2|a
2|608284|4923776.6|b
3|601845|4914981.9|c
4|596270|4917456.3|d
5|593330.8|4924096.6|e
6|598005.5|4921439.2|f" | v.in.ascii cat=1 x=2 y=3 out=centers col="cat integer, \
east double precision, north double precision, label varchar(43)"
v.db.select centers
v.category centers op=report
# type count min max
# point 6 1 6
#create lines map connecting points to network (on layer 2)
v.net myroads points=centers out=myroads_net op=connect thresh=500
v.category myroads_net op=report
# Layer / table: 1 / myroads_net
# type count min max
# line 837 1 5
#
# Layer: 2
# type count min max
# point 6 1 5
# The network is now prepared.
g.region vect=myroads_net
d.mon x0
d.vect myroads_net
d.vect -c centers icon=basic/triangle
d.font verdana
d.vect centers col=red disp=attr attrcol=label lsize=12
v.net.steiner myroads_net acol=cost tcats=1-6 out=mysteiner
d.vect mysteiner col=blue width=2
</pre></div>
<img src="vnetsteiner.png" alt="v.net.steiner example" border="1">
<h2>SEE ALSO</h2>
<em><a HREF="d.path.html">d.path</a></em>,
<em><a HREF="v.net.html">v.net</a></em>,
<em><a HREF="v.net.alloc.html">v.net.alloc</a></em>,
<em><a HREF="v.net.iso.html">v.net.iso</a></em>,
<em><a HREF="v.net.path.html">v.net.path</a></em>,
<em><a HREF="v.net.salesman.html">v.net.salesman</a></em>
<h2>AUTHOR</h2>
Radim Blazek, ITC-Irst, Trento, Italy<br>
Documentation: Markus Neteler
<p><i>Last changed: $Date: 2007-12-17 14:53:55 +0100 (Mon, 17 Dec 2007) $</i>
<HR>
<P><a href="index.html">Main index</a> - <a href="vector.html">vector index</a> - <a href="full_index.html">Full index</a></P>
<P>© 2003-2008 <a href="http://grass.osgeo.org">GRASS Development Team</a></p>
</body>
</html>
