1v.net.steiner(1) Grass User's Manual v.net.steiner(1)
2
6 v.net.steiner - Creates Steiner tree for the network and given termi‐
7 nals.
8 Note that ’Minimum Steiner Tree’ problem is NP-hard and heuristic algo‐
9 rithm is used in this module so the result may be sub optimal.
10
12 vector, network, steiner tree
13
15 v.net.steiner
16 v.net.steiner --help
17 v.net.steiner [-g] input=name output=name
18 [arc_type=string[,string,...]] [arc_layer=string]
19 [node_layer=string] [acolumn=string] terminal_cats=range
20 [npoints=integer] [--overwrite] [--help] [--verbose] [--quiet]
21 [--ui]
22 Flags:
24 -g
25 Use geodesic calculation for longitude-latitude locations
26 --overwrite
28 Allow output files to overwrite existing files
29 --help
31 Print usage summary
32 --verbose
34 Verbose module output
35 --quiet
37 Quiet module output
38 --ui
40 Force launching GUI dialog
41 Parameters:
43 input=name [required]
44 Name of input vector map
45 Or data source for direct OGR access
46 output=name [required]
48 Name for output vector map
49 arc_type=string[,string,...]
51 Arc type
52 Input feature type
53 Options: line, boundary
54 Default: line,boundary
55 arc_layer=string
57 Arc layer
58 Vector features can have category values in different layers. This
59 number determines which layer to use. When used with direct OGR
60 access this is the layer name.
61 Default: 1
62 node_layer=string
64 Node layer (used for terminals)
65 Vector features can have category values in different layers. This
66 number determines which layer to use. When used with direct OGR
67 access this is the layer name.
68 Default: 2
69 acolumn=string
71 Arcs’ cost column (for both directions)
72 terminal_cats=range [required]
74 Category values
75 Categories of points on terminals (layer is specified by nlayer)
76 npoints=integer
78 Number of Steiner points (-1 for all possible)
79 Default: -1
80
82 v.net.steiner calculates the optimal connection of nodes on a vector
83 network.
84 A Steiner tree is used to calculate the minimum-cost vector network
86 connecting some number of end nodes in a network framework. For exam‐
87 ple it could be used to find the path following a road system which
88 will minimize the amount of fibre optic cable needed to connect a
89 series of satellite offices.
90 Costs may be either line lengths, or attributes saved in a database ta‐
92 ble. These attribute values are taken as costs of whole segments, not
93 as costs to traverse a length unit (e.g. meter) of the segment. For
94 example, if the speed limit is 100 km / h, the cost to traverse a 10 km
95 long road segment must be calculated as length / speed = 10 km / (100
96 km/h) = 0.1 h. Supported are cost assignments for both arcs and nodes.
97 For areas, costs will be calculated along boundary lines.
98 Points representing nodes must be exactly on network nodes, and the
100 input vector map needs to be prepared with v.net operation=connect.
101
103 Current implementation of obtaining Steiner tree is not memory effi‐
104 cient. An attempt to run module on a network with large number of
105 intersections thus might result in failure to allocate memory or out of
106 memory condition.
107
109 Steiner tree for 6 digitized nodes (Spearfish):
110 Shortest path, along unimproved roads:
112 Fastest path, along highways:
114 # Spearfish
116 g.copy vect=roads,myroads
117 # we have 6 locations to allocate
118 echo "1|601653.5|4922869.2|a
119 2|608284|4923776.6|b
120 3|601845|4914981.9|c
121 4|596270|4917456.3|d
122 5|593330.8|4924096.6|e
123 6|598005.5|4921439.2|f" | v.in.ascii in=- cat=1 x=2 y=3 out=centers col="cat integer, \
124 east double precision, north double precision, label varchar(43)"
125 v.db.select centers
126 v.category centers op=report
127 # type count min max
128 # point 6 1 6
129 # create lines map connecting points to network (on layer 2)
130 v.net myroads points=centers out=myroads_net op=connect thresh=500
131 # set up costs as traveling time
132 # create unique categories for each road in layer 3
133 v.category in=myroads_net out=myroads_net_time opt=add cat=1 layer=3 type=line
134 # add new table for layer 3
135 v.db.addtable myroads_net_time layer=3 col="cat integer,label varchar(43),length double precision,speed double precision,cost double precision"
136 # copy road type to layer 3
137 v.to.db myroads_net_time layer=3 qlayer=1 opt=query qcolumn=label columns=label
138 # upload road length in miles
139 v.to.db myroads_net_time layer=3 type=line option=length col=length unit=miles
140 # set speed limits in miles / hour
141 v.db.update myroads_net_time layer=3 col=speed val="5.0"
142 v.db.update myroads_net_time layer=3 col=speed val="75.0" where="label=’interstate’"
143 v.db.update myroads_net_time layer=3 col=speed val="75.0" where="label=’primary highway, hard surface’"
144 v.db.update myroads_net_time layer=3 col=speed val="50.0" where="label=’secondary highway, hard surface’"
145 v.db.update myroads_net_time layer=3 col=speed val="25.0" where="label=’light-duty road, improved surface’"
146 v.db.update myroads_net_time layer=3 col=speed val="5.0" where="label=’unimproved road’"
147 # define traveling costs as traveling time in minutes:
148 v.db.update myroads_net_time layer=3 col=cost val="length / speed * 60"
149 # shortest path
150 v.net.steiner myroads_net_time arc_layer=3 node_layer=2 terminal_cats=1-6 out=mysteiner_distance
151 # fastest path
152 v.net.steiner myroads_net_time arc_layer=3 node_layer=2 acol=cost terminal_cats=1-6 out=mysteiner_time
153 To display the result, run for example:
154 # display the results
155 g.region vector=myroads_net
156 # shortest path
157 d.mon x0
158 d.vect myroads_net
159 d.vect -c centers icon=basic/triangle
160 d.font Vera
161 d.vect centers col=red disp=attr attrcol=label lsize=12
162 d.vect mysteiner_distance col=blue width=2
163 # fastest path
164 d.mon x1
165 d.vect myroads_net
166 d.vect -c centers icon=basic/triangle
167 d.font Vera
168 d.vect centers col=red disp=attr attrcol=label lsize=12
169 d.vect mysteiner_time col=blue width=2
170
172 d.path, v.net, v.net.alloc, v.net.iso, v.net.path, v.net.salesman
173
175 Radim Blazek, ITC-Irst, Trento, Italy
176 Documentation: Markus Neteler, Markus Metz
177
179 Available at: v.net.steiner source code (history)
180 Main index | Vector index | Topics index | Keywords index | Graphical
182 index | Full index
183 © 2003-2019 GRASS Development Team, GRASS GIS 7.8.2 Reference Manual
185GRASS 7.8.2 v.net.steiner(1)