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