Changes between Version 3 and Version 4 of rfc48_geographical_networks_support
- Timestamp:
- Jul 17, 2015, 2:52:05 AM (9 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
rfc48_geographical_networks_support
v3 v4 1 1 = RFC 48: Geographical networks support = 2 2 3 Author: Mikhail Gusev [[BR]]4 Contact: gusevmihs at gmail dot com [[BR]]3 Author: Mikhail Gusev, Dmitry Baryshnikov [[BR]] 4 Contact: gusevmihs at gmail dot com, polimax@mail.ru [[BR]] 5 5 Status: 6 6 … … 15 15 == Purpose and description == 16 16 17 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).17 There is a need to have an instrument in GDAL which on the one hand provides an abstraction for different existed network formats (pgRouting, OSRM, GraphHopper, SpatiaLite networks, etc.), 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). 18 18 19 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).19 Such instrument is implemented as a separate set of C++ classes, called GNM. The two main of them represent an abstract network (GNMNetwork class) and the network of ”GDAL-native” or generic format (GNMGenericNetwork class). 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). 20 20 21 21 What does the interface of working with networks include: 22 22 23 * Creating/removing networks ;24 * Creating network topology over spatial data manually or automatically ;25 * Reading resulting connections in a common way ;26 * Adding/removing spatial layers/features to the network ;27 * Defining business logic of the networks (e.g. the way of a ssigning graph costs);28 * Several methods of network analysis .23 * Creating/removing networks 24 * Creating network topology over spatial data manually or automatically 25 * Reading resulting connections in a common way 26 * Adding/removing spatial layers/features to the network 27 * Defining business logic of the networks (e.g. the way of apply or deny connections with different layer features) 28 * Several methods of network analysis 29 29 30 30 See the class architecture document (gdal/gnm/gnm_arch.dox) for more details and how this set of classes internally works. … … 38 38 It is proposed to include the two following apps which use the GNM into GDAL source tree: 39 39 40 * gnmmanage. Similar to gdalmanage purposes. Manages the networks of “GDAL-native” format: creates, removes networks, builds topology manually and automatically ;41 * gnmanalyse. Uses the analysing capabilities of GNM. Currently: shortest path s and connected components searches.40 * 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) 41 * gnmanalyse. Uses the analysing capabilities of GNM. Currently: shortest path(s) and connected components searches 42 42 43 See the description of these apps in according documentation for more details. 43 See the description of these applications in according documentation for more details. 44 45 == Implementation == 46 47 There is already a pull request on github (https://github.com/OSGeo/gdal/pull/60) that implements this RFC. 44 48 45 49 == Set of tests == 46 50 51 All public methods of GNMNetwork tested in autotest gnm tests. The several tests for GNMGenericNetwork added. The console applications (gnmmanage and gnmanalyse) tested in autotest/utilities. 52 47 53 All tests were implemented according to the general rules: they are written on Python and situated in /autotest folder: 48 54 49 * GNM basic tests. Tests the basic “GDAL-network” functionality, using some small test shapefiles ;50 * GNM utilities tests. Simple tests of the gnmmanage utility, similarly to ogrinfo tests.55 * GNM basic tests. Tests the basic “GDAL-network” functionality, using some small test shapefiles 56 * GNM utilities tests. Simple tests of the gnmmanage and gnmanalyse utilities, similarly to ogrinfo tests 51 57 52 58 == Documentation structure == 53 59 60 All new methods and GNM classes are documented. GDAL documentation is updated when necessary. 61 54 62 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: 55 63 56 * GNM Architecture. The purpose and description of all GNM C++ classes ;57 * GNM Tutorial. The guide how to use the C++ GNM classes ;58 * GNM Utility Programs. The references to two GNM utilities ;59 * gnmmanage. Description and usage of gnmmanage utility ;60 * gnmanalyse. Description and usage of gnmanalyse utility .64 * GNM Architecture. The purpose and description of all GNM C++ classes 65 * GNM Tutorial. The guide how to use the C++ GNM classes 66 * GNM Utility Programs. The references to two GNM utilities 67 * gnmmanage. Description and usage of gnmmanage utility 68 * gnmanalyse. Description and usage of gnmanalyse utility 61 69 62 70 == Source code tree organization == … … 66 74 The integration will cause the '''addition''' of new folders with header, source, make and doc files: 67 75 68 * gdal/gnm – the main folder of GNM; 69 * Source code and documentation files of applications at gdal/apps; 70 * Testing python scripts at autotest/gnm and autotest/utilities; 71 * Two testing shapefiles at autotest/gnm/data (~7 Kb); 72 * Swig interface file at gdal/swig/include. 76 * gcore/gdal.h - add new driver type GNM 77 * gdal/gnm – the main folder of GNM 78 * Source code and documentation files of applications at gdal/apps 79 * Testing python scripts at autotest/gnm and autotest/utilities 80 * Two testing shapefiles at autotest/gnm/data (~7 Kb) 81 * Swig interface file at gdal/swig/include 73 82 74 83 ''What is being modified:'' … … 76 85 The '''changing''' of the existed GDAL files '''will be insignificant''': 77 86 78 * GNUMakefile and makefile.vc at /gdal and /gdal/apps; 79 * /autotest/pymod/test_cli_utilities.py to add the utility testing command; 80 * /swig/python/setup.py and setup.cfg to add gnm module. 87 * GNUMakefile, makefile.vc and their configurations at /gdal and /gdal/apps 88 * /autotest/run_all.py to add gnm tests 89 * /autotest/pymod/test_cli_utilities.py to add the utility testing command 90 * /autotest/utilities/test_gnmutils.py 91 * /swig/python/setup.py and setup.cfg to add gnm module 92 * GNUMakefile and makefile.vc at /swig/java 93 81 94 82 95 == Future ideas == … … 84 97 I see many useful and interesting ways of GNM expending in future: 85 98 86 * 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:99 * 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 and PostGIS). For example: 87 100 88 * GNMPG Network. Works with pgRouting tables. Some ideas:89 * GNMPG Network::ConnectFeatures() will add to "source" and "target"columns according values via OGRFeature::setField();90 * GNMPG Network::AutoConnect() will internally call pgr_createTopology method.101 * GNMPGRoutingNetwork. Works with pgRouting tables. Some ideas: 102 * GNMPGRoutingNetwork::ConnectFeatures() will add to "source" and "target" columns according values via OGRFeature::setField() 103 * GNMPGRoutingNetwork::AutoConnect() will internally call pgr_createTopology method 91 104 92 105 * GNMSQLiteNetwork. Works with SpatiaLite VirtualNetwork networks. Some ideas: 93 * write all network data to the Roads_net_data table and to corresponding NodeFrom and NodeTo columns .106 * write all network data to the Roads_net_data table and to corresponding NodeFrom and NodeTo columns 94 107 95 108 * GNMGMLNetwork. Works with the GML topology. Some ideas: 96 * write network data to the <gml::TopoComplex>, <gml::Node> and <gml::Edge> directly .109 * write network data to the <gml::TopoComplex>, <gml::Node> and <gml::Edge> directly 97 110 98 * 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. GNMG dalNetwork can have more effective default algorithm.111 * 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. GNMGenericNetwork can have more effective default algorithm. 99 112 100 113 * More rules in GDAL-networks, i.e. more complex syntax describing the following: 101 * costs extracted from geometrical lengths of lines ;102 * turn restriction roles of features ;103 * more complex connection rules: set the limit of features can be connected and more complex expressions .114 * costs extracted from geometrical lengths of lines 115 * turn restriction roles of features 116 * more complex connection rules: set the limit of features can be connected and more complex expressions 104 117 105 118 * 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); 106 119 107 120 * Analysis. The support of different graph types and the algorithms working with them, for different routing and even engineering purposes. For example: 108 * GNMBoostAnalyser. Based on Boost library;109 * GNMCHAnalyser. Contraction Hierarchies technology (for large graphs).121 * Boost library 122 * Contraction Hierarchies technology (for large graphs)