v.net.steiner(1grass)

1v.net.steiner(1)              Grass User's Manual             v.net.steiner(1)
2
3
4

NAME

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

KEYWORDS

12       vector, network, steiner tree
13

SYNOPSIS

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
23   Flags:
24       -g
25           Use geodesic calculation for longitude-latitude locations
26
27       --overwrite
28           Allow output files to overwrite existing files
29
30       --help
31           Print usage summary
32
33       --verbose
34           Verbose module output
35
36       --quiet
37           Quiet module output
38
39       --ui
40           Force launching GUI dialog
41
42   Parameters:
43       input=name [required]
44           Name of input vector map
45           Or data source for direct OGR access
46
47       output=name [required]
48           Name for output vector map
49
50       arc_type=string[,string,...]
51           Arc type
52           Input feature type
53           Options: line, boundary
54           Default: line,boundary
55
56       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
63       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
70       acolumn=string
71           Arcs’ cost column (for both directions)
72
73       terminal_cats=range [required]
74           Category values
75           Categories of points on terminals (layer is specified by nlayer)
76
77       npoints=integer
78           Number of Steiner points (-1 for all possible)
79           Default: -1
80

DESCRIPTION

82       v.net.steiner  calculates  the  optimal connection of nodes on a vector
83       network.
84
85       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
91       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
99       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

NOTES

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

EXAMPLE

109       Steiner tree for 6 digitized nodes (Spearfish):
110
111       Shortest path, along unimproved roads:
112
113       Fastest path, along highways:
114
115       # 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

AUTHOR

175       Radim Blazek, ITC-Irst, Trento, Italy
176       Documentation: Markus Neteler, Markus Metz
177
178       Last changed: $Date: 2016-03-08 08:50:26 +0100 (Tue, 08 Mar 2016) $
179

SOURCE CODE

181       Available at: v.net.steiner source code (history)
182
183       Main index | Vector index | Topics index | Keywords index  |  Graphical
184       index | Full index
185
186       © 2003-2019 GRASS Development Team, GRASS GIS 7.4.4 Reference Manual
187
188
189
190GRASS 7.4.4                                                   v.net.steiner(1)