Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
v.net.steiner(1)	    GRASS GIS User's Manual	      v.net.steiner(1)

NAME
       v.net.steiner   - Creates Steiner tree for the network and given	termi-
       nals.
       Note that 'Minimum Steiner Tree'	problem	is NP-hard and heuristic algo-
       rithm is	used in	this module so the result may be sub optimal.

KEYWORDS
       vector, network,	steiner	tree

SYNOPSIS
       v.net.steiner
       v.net.steiner --help
       v.net.steiner	       [-g]	      input=name	   output=name
       [arc_type=string[,string,...]]			    [arc_layer=string]
       [node_layer=string]	   [acolumn=string]	   terminal_cats=range
       [npoints=integer]    [--overwrite]   [--help]   [--verbose]   [--quiet]
       [--ui]

   Flags:
       -g
	   Use geodesic	calculation for	longitude-latitude locations

       --overwrite
	   Allow output	files to overwrite existing files

       --help
	   Print usage summary

       --verbose
	   Verbose module output

       --quiet
	   Quiet module	output

       --ui
	   Force launching GUI dialog

   Parameters:
       input=nameA [required]
	   Name	of input vector	map
	   Or data source for direct OGR access

       output=nameA [required]
	   Name	for output vector map

       arc_type=string[,string,...]
	   Arc type
	   Input feature type
	   Options: line, boundary
	   Default: line,boundary

       arc_layer=string
	   Arc layer
	   Vector  features can	have category values in	different layers. This
	   number determines which layer to use. When used with	direct OGR ac-
	   cess	this is	the layer name.
	   Default: 1

       node_layer=string
	   Node	layer (used for	terminals)
	   Vector  features can	have category values in	different layers. This
	   number determines which layer to use. When used with	direct OGR ac-
	   cess	this is	the layer name.
	   Default: 2

       acolumn=string
	   Arcs' cost column (for both directions)

       terminal_cats=rangeA [required]
	   Category values
	   Categories of points	on terminals (layer is specified by nlayer)

       npoints=integer
	   Number of Steiner points (-1	for all	possible)
	   Default: -1

DESCRIPTION
       v.net.steiner  calculates  the  optimal connection of nodes on a	vector
       network.

       A Steiner tree is used to calculate  the	 minimum-cost  vector  network
       connecting  some	number of end nodes in a network framework.  For exam-
       ple 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 se-
       ries of satellite offices.

       Costs may be either line	lengths, or attributes saved in	a database ta-
       ble.  These  attribute values are taken as costs	of whole segments, not
       as costs	to traverse a length unit (e.g.	meter) of  the	segment.   For
       example,	if the speed limit is 100 km / h, the cost to traverse a 10 km
       long road segment must be calculated as length /	speed =	10 km  /  (100
       km/h) = 0.1 h.  Supported are cost assignments for both arcs and	nodes.
       For areas, costs	will be	calculated along boundary lines.

       Points representing nodes must be exactly on network nodes, and the in-
       put vector map needs to be prepared with	v.net operation=connect.

NOTES
       Current	implementation	of  obtaining Steiner tree is not memory effi-
       cient.  An attempt to run module	on a network with large	number of  in-
       tersections  thus  might	result in failure to allocate memory or	out of
       memory condition.

EXAMPLE
       Steiner tree for	6 digitized nodes (Spearfish):

       Shortest	path, along unimproved roads:

       Fastest path, along highways:

       # Spearfish
       g.copy vect=roads,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 in=- 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
       # set up	costs as traveling time
       # create	unique categories for each road	in layer 3
       v.category in=myroads_net out=myroads_net_time opt=add cat=1 layer=3 type=line
       # add new table for layer 3
       v.db.addtable myroads_net_time layer=3 col="cat integer,label varchar(43),length	double precision,speed double precision,cost double precision"
       # copy road type	to layer 3
       v.to.db myroads_net_time	layer=3	qlayer=1 opt=query qcolumn=label columns=label
       # upload	road length in miles
       v.to.db myroads_net_time	layer=3	type=line option=length	col=length unit=miles
       # set speed limits in miles / hour
       v.db.update myroads_net_time layer=3 col=speed val="5.0"
       v.db.update myroads_net_time layer=3 col=speed val="75.0" where="label='interstate'"
       v.db.update myroads_net_time layer=3 col=speed val="75.0" where="label='primary highway,	hard surface'"
       v.db.update myroads_net_time layer=3 col=speed val="50.0" where="label='secondary highway, hard surface'"
       v.db.update myroads_net_time layer=3 col=speed val="25.0" where="label='light-duty road,	improved surface'"
       v.db.update myroads_net_time layer=3 col=speed val="5.0"	where="label='unimproved road'"
       # define	traveling costs	as traveling time in minutes:
       v.db.update myroads_net_time layer=3 col=cost val="length / speed * 60"
       # shortest path
       v.net.steiner myroads_net_time arc_layer=3 node_layer=2 terminal_cats=1-6 out=mysteiner_distance
       # fastest path
       v.net.steiner myroads_net_time arc_layer=3 node_layer=2 acol=cost terminal_cats=1-6 out=mysteiner_time
       To display the result, run for example:
       # display the results
       g.region	vector=myroads_net
       # shortest path
       d.mon x0
       d.vect myroads_net
       d.vect -c centers icon=basic/triangle
       d.font Vera
       d.vect centers col=red disp=attr	attrcol=label lsize=12
       d.vect mysteiner_distance col=blue width=2
       # fastest path
       d.mon x1
       d.vect myroads_net
       d.vect -c centers icon=basic/triangle
       d.font Vera
       d.vect centers col=red disp=attr	attrcol=label lsize=12
       d.vect mysteiner_time col=blue width=2

SEE ALSO
       d.path, v.net, v.net.alloc, v.net.iso, v.net.path, v.net.salesman

AUTHOR
       Radim Blazek, ITC-Irst, Trento, Italy
       Documentation: Markus Neteler, Markus Metz

SOURCE CODE
       Available at: v.net.steiner source code (history)

       Main index | Vector index | Topics index	| Keywords index  |  Graphical
       index | Full index

       A(C) 2003-2020 GRASS Development	Team, GRASS GIS	7.8.3 Reference	Manual

GRASS 7.8.3						      v.net.steiner(1)

NAME | KEYWORDS | SYNOPSIS | DESCRIPTION | NOTES | EXAMPLE | SEE ALSO | AUTHOR | SOURCE CODE

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=v.net.steiner&sektion=1&manpath=FreeBSD+12.2-RELEASE+and+Ports>

home | help