1.. _rfc-48:
2
3=======================================================================================
4RFC 48: Geographical networks support
5=======================================================================================
6
7Author: Mikhail Gusev, Dmitry Baryshnikov
8
9Contact: gusevmihs at gmail dot com, polimax@mail.ru
10
11Status: adopted, implemented in GDAL 2.1
12
13Introduction
14------------
15
16This document proposes the integration of the results of GSoC 2014
17project “GDAL/OGR Geography Network support” into GDAL library. GNM
18(Geographical Network Model) intends to bring the capabilities to
19create, manage and analyse networks built over spatial data in GDAL.
20
21GSoC project description:
22`http://trac.osgeo.org/gdal/wiki/geography_network_support <http://trac.osgeo.org/gdal/wiki/geography_network_support>`__
23
24GDAL fork with all changes in trunk:
25`https://github.com/MikhanGusev/gdal <https://github.com/MikhanGusev/gdal>`__
26
27GSoC blog:
28`http://gsoc2014gnm.blogspot.ru/ <http://gsoc2014gnm.blogspot.ru/>`__
29
30Purpose and description
31-----------------------
32
33There is a need to have an instrument in GDAL which on the one hand
34provides an abstraction for different existed network formats
35(pgRouting, OSRM, GraphHopper, SpatiaLite networks, etc.), like GDAL
36(previously OGR) provides one for spatial vector formats, and on the
37other hand provides a network functionality to those spatial formats
38which does not have it at all (Shapefiles).
39
40Such instrument is implemented as a separate set of C++ classes, called
41GNM. The two main of them represent an abstract network (GNMNetwork
42class) and the network of ”GDAL-native” or generic format
43(GNMGenericNetwork class). An abstract network is used by user as a
44common interface to manage his network data. The list of underlying
45format-specific classes can be extended anytime like a list of GDAL
46drivers to support more network formats. The ”GDAL-native” format
47implements the abstract network and is used to provide the network
48functionality to the spatial formats which are already supported by
49GDAL. All the network data of this format is stored in the special set
50of layers along with spatial data in a spatial dataset (internally
51GDALDataset and OGRLayer are widely used).
52
53What does the interface of working with networks include:
54
55::
56
57   * Creating/removing networks
58   * Creating network topology over spatial data manually or automatically
59   * Reading resulting connections in a common way
60   * Adding/removing  spatial layers/features to the network
61   * Defining business logic of the networks (e.g. the way of apply or deny connections with different layer features)
62   * Several methods of network analysis
63
64See the class architecture document (gdal/gnm/gnm_arch.dox) for more
65details and how this set of classes internally works.
66
67Bindings
68--------
69
70The C API wrapper functions are declared in gdal/gnm/gnm_api.h. All
71current python bindings are implemented in a swig interface file and use
72these C functions.
73
74Set of applications
75-------------------
76
77It is proposed to include the two following apps which use the GNM into
78GDAL source tree:
79
80::
81
82   * gnmmanage. Similar to gdalmanage purposes. Manages the networks of “GDAL-native” format: creates, removes networks, builds topology manually and automatically (as the GNMNetwork inherited from GDALDataset, the gdalmanage can be used with GNMNetwork)
83   * gnmanalyse. Uses the analysing capabilities of GNM. Currently: shortest path(s) and connected components searches
84
85See the description of these applications in according documentation for
86more details.
87
88Implementation
89--------------
90
91There is already a pull request on github
92(`https://github.com/OSGeo/gdal/pull/60 <https://github.com/OSGeo/gdal/pull/60>`__)
93that implements this RFC.
94
95Building GDAL with GNM support
96------------------------------
97
98By default the building of GNM support is disabled. To build GNM support
99one have to add --with-gnm key to configure or uncomment the appropriate
100line in nmake.opt.
101
102Set of tests
103------------
104
105All public methods of GNMNetwork tested in autotest gnm tests. The
106several tests for GNMGenericNetwork added. The console applications
107(gnmmanage and gnmanalyse) tested in autotest/utilities.
108
109All tests were implemented according to the general rules: they are
110written on Python and situated in /autotest folder:
111
112::
113
114   * GNM basic tests. Tests the basic “GDAL-network” functionality, using some small test shapefiles
115   * GNM utilities tests. Simple tests of the gnmmanage and gnmanalyse utilities, similarly to ogrinfo tests
116
117Documentation structure
118-----------------------
119
120All new methods and GNM classes are documented. GDAL documentation is
121updated when necessary.
122
123The following new Doxyfiles in /gnm and /apps directories will be
124automatically built into the main auto-generated html into the “Related
125pages” section. All them are similar to OGR docs:
126
127::
128
129   * GNM Architecture. The purpose and description of all GNM C++ classes
130   * GNM Tutorial. The guide how to use the C++ GNM classes
131   * GNM Utility Programs. The references to two GNM utilities
132   * gnmmanage. Description and usage of gnmmanage utility
133   * gnmanalyse. Description and usage of gnmanalyse utility
134
135Source code tree organization
136-----------------------------
137
138*What is being added:*
139
140The integration will cause the *addition* of new folders with header,
141source, make and doc files:
142
143::
144
145   * gcore/gdal.h - add new driver type GNM
146       * gdal/gnm – the main folder of GNM
147   * Source code and documentation files of applications at gdal/apps
148   * Testing python scripts at autotest/gnm and autotest/utilities
149   * Two testing shapefiles at autotest/gnm/data (~7 Kb)
150   * Swig interface file at gdal/swig/include
151
152*What is being modified:*
153
154The *changing* of the existed GDAL files *will be insignificant*:
155
156::
157
158   * GNUMakefile, makefile.vc and their configurations at /gdal and /gdal/apps
159       * /autotest/run_all.py to add gnm tests
160   * /autotest/pymod/test_cli_utilities.py to add the utility testing command
161       * /autotest/utilities/test_gnmutils.py
162   * /swig/python/setup.py and setup.cfg to add gnm module
163       * GNUMakefile and makefile.vc at /swig/java
164
165Future ideas
166------------
167
168I see many useful and interesting ways of GNM expending in future:
169
170-  More formats support. The important thing, which must be firstly
171   implemented in future, while the GNM intends to work with as many
172   network formats as possible. It includes not only the support of
173   GNMGdalNetwork formats – i.e. the testing to work with other GDAL
174   spatial formats (currently tested only for Shapefiles and PostGIS).
175   For example:
176
177   -  GNMPGRoutingNetwork. Works with pgRouting tables. Some ideas:
178
179      -  GNMPGRoutingNetwork::ConnectFeatures() will add to "source" and
180         "target" columns according values via OGRFeature::setField()
181      -  GNMPGRoutingNetwork::AutoConnect() will internally call
182         pgr_createTopology method
183
184   -  GNMSQLiteNetwork. Works with SpatiaLite VirtualNetwork networks.
185      Some ideas:
186
187      -  write all network data to the Roads_net_data table and to
188         corresponding NodeFrom and NodeTo columns
189
190   -  GNMGMLNetwork. Works with the GML topology. Some ideas:
191
192      -  write network data to the
193         `gml::TopoComplex <gml::TopoComplex>`__,
194         `gml::Node <gml::Node>`__ and `gml::Edge <gml::Edge>`__
195         directly
196
197-  More effective algorithm of topology building in GDAL-networks. The
198   current one is implemented as the default for any network format and
199   can connect any amount of line and point layers but is not so
200   efficient – the large networks are being connected too long.
201   GNMGenericNetwork can have more effective default algorithm.
202
203-  More rules in GDAL-networks, i.e. more complex syntax describing the
204   following:
205
206   -  costs extracted from geometrical lengths of lines
207   -  turn restriction roles of features
208   -  more complex connection rules: set the limit of features can be
209      connected and more complex expressions
210
211-  Applications. May be one of the most useful application which can be
212   build with GNM is *network2network*, which converts the network and
213   spatial data of the dataset from the one format to another (for
214   example from pgRouting to Oracle Spatial networks);
215
216-  Analysis. The support of different graph types and the algorithms
217   working with them, for different routing and even engineering
218   purposes. For example:
219
220   -  Boost library
221   -  Contraction Hierarchies technology (for large graphs)
222
223Voting history
224--------------
225
226+1 from JukkaR, TamasS and EvenR
227