We’re glad to introduce GNM (Geographical Network Model) for GDAL and would like to share what it is about. GNM has been developed by Mikhail Gusev during Google Summer of Code 2014 under the mentorship of NextGIS. GNM intends to bring capabilities to create, manage and analyse networks built over spatial data in GDAL.
According to the concept any dataset (the set of spatial data of one format) can have the special set of layers and fields which holds the network’s data (e.g. network’s graph and metadata). Generally this set is either already defined like in PostGIS pgRouting, SpatiaLite VirtualNetwork, Oracle Spatial networks, topology in GML, or there is no such data in the dataset at all, like in ESRI Shapefile format. Though GDAL library provides an abstraction for spatial data of these formats it didn’t provide one for their “network parts” before. We developed the special set of classes and interfaces for GDAL which intends to “know” which data of the dataset refers to network data and how to operate it.
The key purpose of GNM classes and interfaces are:
- To provide an abstraction for network data of different formats, like GDAL (previously OGR) provides one for spatial vector data;
- To provide a network functionality to those spatial formats which does not have it at all.
Network data abstraction
The interface working with networks includes:
- Creating network dataset from scratch or based on the spatial dataset; and removing network dataset
- Creating network topology manually or automatically according to some algorithm (setting connections among spatial objects);
-
Modifying spatial data in the context of network (adding, changing or removing spatial objects), that can cause the network data modification;
- Reading network data.
This interface can be implemented for the concrete formats, though for now there was no aim to support any of them, but in future it can be implemented for pgRouting, VirtualNetwork and so on.
Network functionality for spatial formats
The separate set of classes in GNM is an implementation of described interface, and it is developed not for the concrete format but for any that can be represented as GDALDataset, i.e. for any currently supported by GDAL. Such support is not “native” for these formats and that’s why all network data is stored in the special set of layers and can be represented as the set of OGRLayer-s.
The ESRI Shapefile support was tested during the work on GSoC and it’s already possible to create and analyse networks in this format now. Specifically, it is possible to create network using the described above interface and after that do the following:
* To use one of the existed for now in GNM network analysing methods: Dijkstra shortest path search and breadth-first connected components search. The resulting layer will contain the final path (as at the picture below) or connected components.
Picture 1. Shortest path between features 792 and 824.
* To use the capability to “block” any amount of features in the network and using it in a combination with the described above methods to make, for example, a commutations analysis in a water pipe network (as at the pictures below).
Picture 2. Water distribution in a network before the commutation (the source is marked as a star).
Picture 3. Water distribution after the “blocking” at features 829, 781 and 802.
* To define the rules which will be used during the network’s topology (graph) construction: to make expressions for edge costs and directions calculations, to define the connectivity rules in the network.
Documentation
The documentation is contained in the source code tree: GNM Architecture describes the purpose and description of all classes and interfaces, while GNM Tutorial describes the examples of using the new API.
Applications using GNM
In order to use the capabilities of GNM there were also developed some command line applications, which are included into GDAL:
1. gnmmanage. Network’s creating and managing.
2. gnmanalyse. Network’s analysing.
Links
GSoC development blog: http://gsoc2014gnm.blogspot.ru/
GsoC project: http://trac.osgeo.org/gdal/wiki/geography_network_support
GDAL fork with all changes: https://github.com/nextgis/gdal-gnm
RFC about GNM integration into GDAL: http://trac.osgeo.org/gdal/wiki/rfc48_geographical_networks_support