RFC 48: Geographical networks support

Author: Mikhail Gusev
Contact: gusevmihs at gmail dot com
Status:

Introduction

This document proposes the integration of the results of GSoC 2014 project “GDAL/OGR Geography Network support” into GDAL library. GNM (Geographical Network Model) intends to bring the capabilities to create, manage and analyse networks built over spatial data in GDAL.

GSoC project description: http://trac.osgeo.org/gdal/wiki/geography_network_support
GDAL fork with all changes in trunk: ​https://github.com/MikhanGusev/gdal
GSoC blog: ​http://gsoc2014gnm.blogspot.ru/

Purpose and description

There is a need to have an instrument in GDAL which on the one hand provides an abstraction for different existed network formats (pgRouting and SpatiaLite networks), like GDAL (previously OGR) provides one for spatial vector formats, and on the other hand provides a network functionality to those spatial formats which does not have it at all (Shapefiles).

Such instrument is implemented as a separate set of C++ classes, called GNM. The two main of them represent an abstract network and the network of ”GDAL-native” format. An abstract network is used by user as a common interface to manage his network data. The list of underlying format-specific classes can be extended anytime like a list of GDAL drivers to support more network formats. The ”GDAL-native” format implements the abstract network and is used to provide the network functionality to the spatial formats which are already supported by GDAL. All the network data of this format is stored in the special set of layers along with spatial data in a spatial dataset (internally GDALDataset and OGRLayer are widely used).

What does the interface of working with networks include:

• Creating/removing networks;
• Creating network topology over spatial data manually or automatically;
• Reading resulting connections in a common way;
• Adding/removing spatial layers/features to the network;
• Defining business logic of the networks (e.g. the way of assigning graph costs);
• Several methods of network analysis.

See the class architecture document (gdal/gnm/gnm_arch.dox) for more details and how this set of classes internally works.

Bindings

The C API wrapper functions are declared in gdal/gnm/gnm_api.h. All current python bindings are implemented in a swig interface file and use these C functions.

Set of applications

It is proposed to include the two following apps which use the GNM into GDAL source tree:

• gnmmanage. Similar to gdalmanage purposes. Manages the networks of “GDAL-native” format: creates, removes networks, builds topology manually and automatically;
• gnmanalyse. Uses the analysing capabilities of GNM. Currently: shortest paths and connected components searches.

See the description of these apps in according documentation for more details.

Set of tests

All tests were implemented according to the general rules: they are written on Python and situated in /autotest folder:

• GNM basic tests. Tests the basic “GDAL-network” functionality, using some small test shapefiles;
• GNM utilities tests. Simple tests of the gnmmanage utility, similarly to ogrinfo tests.

Documentation structure

The following new Doxyfiles in /gnm and /apps directories will be automatically built into the main auto-generated html into the “Related pages” section. All them are similar to OGR docs:

• GNM Architecture. The purpose and description of all GNM C++ classes;
• GNM Tutorial. The guide how to use the C++ GNM classes;
• GNM Utility Programs. The references to two GNM utilities;
• gnmmanage. Description and usage of gnmmanage utility;
• gnmanalyse. Description and usage of gnmanalyse utility.

Source code tree organization

What is being added:

The integration will cause the addition of new folders with header, source, make and doc files:

• gdal/gnm – the main folder of GNM;
• Source code and documentation files of applications at gdal/apps;
• Testing python scripts at autotest/gnm and autotest/utilities;
• Two testing shapefiles at autotest/gnm/data (~7 Kb);
• Swig interface file at gdal/swig/include.

What is being modified:

The changing of the existed GDAL files will be insignificant:

• GNUMakefile and makefile.vc at /gdal and /gdal/apps;
• /autotest/pymod/test_cli_utilities.py to add the utility testing command;
• /swig/python/setup.py and setup.cfg to add gnm module.

Future ideas

I see many useful and interesting ways of GNM expending in future:

• More formats support. The important thing, which must be firstly implemented in future, while the GNM intends to work with as many network formats as possible. It includes not only the support of GNMGdalNetwork formats – i.e. the testing to work with other GDAL spatial formats (currently tested only for Shapefiles) – but especially the concrete implementations of GNMFormat – GNMNetwork pair. For example:

• GNMPGNetwork. Works with pgRouting tables. Some ideas:
  • GNMPGNetwork::ConnectFeatures() will add to "source" and "target"columns according values via OGRFeature::setField();
  • GNMPGNetwork::AutoConnect() will internally call pgr_createTopology method.

• GNMSQLiteNetwork. Works with SpatiaLite VirtualNetwork networks. Some ideas:
  • write all network data to the Roads_net_data table and to corresponding NodeFrom and NodeTo columns.

• GNMGMLNetwork. Works with the GML topology. Some ideas:
  • write network data to the <gml::TopoComplex>, <gml::Node> and <gml::Edge> directly.

• More effective algorithm of topology building in GDAL-networks. The current one is implemented as the default for any network format and can connect any amount of line and point layers but is not so efficient – the large networks are being connected too long. GNMGdalNetwork can have more effective default algorithm.

• More rules in GDAL-networks, i.e. more complex syntax describing the following:
  • costs extracted from geometrical lengths of lines;
  • turn restriction roles of features;
  • more complex connection rules: set the limit of features can be connected and more complex expressions.

• Applications. May be one of the most useful application which can be build with GNM is network2network, which converts the network and spatial data of the dataset from the one format to another (for example from pgRouting to Oracle Spatial networks);

• Analysis. The support of different graph types and the algorithms working with them, for different routing and even engineering purposes. For example:
  • GNMBoostAnalyser. Based on Boost library;
  • GNMCHAnalyser. Contraction Hierarchies technology (for large graphs).