Week #13. GNM finished

At this week I've completed all that I planed to do for the last week:

1) Fixed all makefiles (GNUMakefile and makefile.vc) and built on Linux and Windows accordingly. I also tested all my apps (which use the most of GNM functionality) on these platforms and they worked fine;
2)  Complete GNM Python tests. Now the direct GNM tests and tests of gnmmanage app are available;
3) And finally I've completed all documentation:
       *  Doxyfile for GNM;
       * All public methods are commented in code for Doxygen accordingly;
       * GNM architecture;
       * GNM tutorial;
       * gnmanalyse description in .dox form;
       * gnmmanage description in .dox form.

Week #12. GNM is almost finished

What I've complete in GNM at this week:
1. Implemented the second algorithm: Connected components search and according capability in gnmanalyse app;
2. Implemented blocking capabilities for networks. Now you can calculate paths and resource distribution via gnmanalyse app as the folowing:

>gnmanalyse.exe resource -bl 12 -bl 235 -unbl 740 

// This will analyse the resource distribution (water, electricity) during the commutations of features in network: the features 12, 235 are blocked (will not be regarded during the routing process) and 740 is unblocked. All blocking features will be saved in a separate system layer. The resource will spread over the network from the features which are marked as emitters (via rules). The emitter features can also be blocked so not to 'emit' the resource. 

>gnmanalyse.exe dijkstra 718 740 -unblall

// This will calculate the shortest path between 718 and 740 when all features (saved in previous calculations) are become unblocked.

3. Now it is possible to connect features without geometries - the according system features will serve as graph edges;
4. Fixed some bugs/issues.

All these capabilities I've also previously described in my older posts.

What I need to do in order to finish my work on GNM:
1. Fix GNUMakefile-s according to some new changes
2. Make a bit more python tests
3. Complete docs: some new comments in code and finish architecture & tutorial

Week #11. Network's business logic

At this week I've implemented a support of network's business logic (commit) as I described in my previous posts which is based on the concept of string rules. More general, for the future subclasses of GNMNetwork the method CreateRule(const char *pszRuleStr) can be used to create a some kind of rule/constraint/restriction in the concrete network format. In GNMGdalNetwork it is used to determine how the costs or directions or for the graph edges can be extracted during the connection of features and how the features can be connected with each other. GNMGdalNetwork::CreateRule() parses the given string according to the special syntax (see my first post about rules). I've added to the gnmmanage utility some new commands, so now it can be used like the following:

>gnmmanage --long-usage

Usage: gnmmanage [--help][-q][-quiet][--utility_version][--long-usage]

[create [-f format_name] [-t_srs srs_name] [-dsco NAME=VALUE]... ]

[import src_dataset_name] [-l layer_name]

[connect gfid_src gfid_tgt gfid_con [-c cost] [-ic inv_cost] [-dir dir]]

[rule rule_str]

[autoconnect tolerance]

[remove]

[-nt]

gnm_name

create: create connectivity or the full network, depending on native format support (-nt)

-f format_name: output file format name, possible values are:

[ESRI Shapefile]

-t_srs srs_name: spatial reference input

-dsco NAME=VALUE: dataset creation option (format specific)

import src_dataset_name: dataset name to copy

-l layer_name: layer name in dataset (optional)

connect gfid_src gfid_tgt gfid_con: make a topological connection, where the gfid_src and gfid_tgt are vertexes and gfid_con is edge

-c cost -ic inv_cost -dir dir: manually assign the following values: the cost (weight), inverse cost and direction of the edge (optional)

rule rule_str: creates a rule/constraint in the network by the given rule_str string

autoconnect tolerance: create topology automatically with the given double tolerance

remove: remove connectivity or network, depending on native format support (-nt)

-nt: use native network format (now unavailable)

So lets use the gnmmanage in combination with gnmanalyse to see the new functionality. For example we need to calculate the shortest path between two points. The layer lines has the special field called "L" where the length of the feature is stored. We must create network, import layers and create some rules before the automatic connection will be called in order to put in the graph the "L" field values as costs. For example for bat windows file:

gnmmanage.exe create -f "ESRI Shapefile" -t_srs "EPSG:4326" -dsco "net_name=my_network_1" ..\network_data

gnmmanage.exe import ..\in_data\krasnogorsk -l lines ..\network_data

gnmmanage.exe import ..\in_data\krasnogorsk -l kolodci ..\network_data

gnmmanage.exe import ..\in_data\krasnogorsk -l reshetki ..\network_data

gnmmanage.exe rule "CLASS gnm_lines_line COSTS L" ..\network_data

gnmmanage.exe rule "CLASS gnm_lines_line INVCOSTS L" ..\network_data

gnmmanage.exe rule "CLASS gnm_lines_line DIRECTS my_dir" ..\network_data

gnmmanage.exe autoconnect 0.00005 ..\network_data

The piece of network looks like the following:

The 717 and 744 have not been connected during the automatic connection because they are far from each other. We can connect them manually in order to create the alternative path for routing.

gnmmanage.exe connect 717 744 231 ..\network_data

After that we use Dijkstra algorithm several times to calculate a path between the points: 1) 716->740; 2) 715->740; 3) 711->740. The shortest path is calculated properly, according to the summary length in each case.

During our work with network the connection rules have not been set. The concept of rules considers that if no NETWORK rules for particular classes have been set than the connections of all features with each other are allowed by default. So there were no problems. If we set at least one connection rule for the class, then during the ConnectFeatures() method the permission of the connection will be checked anytime.

We create the following rules and autoconnect the newly created network:

...

gnmmanage.exe rule "NETWORK CONNECTS gnm_reshetki_point WITH gnm_kolodci_point VIA gnm_lines_line" ..\network_data

gnmmanage.exe rule "NETWORK CONNECTS gnm_kolodci_point WITH gnm_kolodci_point VIA gnm_lines_line" ..\network_data

gnmmanage.exe autoconnect 0.00005 ..\network_data

After the automatic connection all kolodci features have been connected with reshetki features and with themselves, as opposite to reshetki & reshetki features because such rule has not been set.
 So the shortest path will not be found between 1100 and 1341 features (1). After the creation of corresponding rule two reshetki features can be connected manually and the path will be found (2). In the picture: kolodci: circle with dots, reshetki: stars, lines: lines.

Week #10. Network analysis in GNM

The new GNM functionality came to GDAL with two new applications: gnmmanage and gnmanalyse. In this post I'll describe the new classes and methods of API by example of these apps, which I also implement on this week: this is my last commit.

Note: I've also renamed some classes (e.g. GNMConnectivity -> GNMNetwork) and moved some methods from one class to another, due to the better correspondence to my concept. I'll describe the final architecture appearance a bit later, but it hasn't been changed a lot.

gnmmanage

The gnmmanage utility intends to provide all managing actions with networks: creating/deleting networks, creating/deleting features, setting/removing connections. For now it has the following usage:

>gnmmanage.exe --long-usage

Usage: gnmmanage [--help][-q][-quiet][--utility_version][--long-usage]

[create [-f format_name] [-t_srs srs_name] [-dsco NAME=VALUE]... ]

[import src_dataset_name] [-l layer_name]

[autoconnect tolerance]

[remove]

[-nt]

gnm_name

create: create connectivity or the full network, depending on native format support (-nt)

-f format_name: output file format name, possible values are: [ESRI Shapefile]

-t_srs srs_name: spatial reference input

-dsco NAME=VALUE: dataset creation option (format specific) import src_dataset_name: dataset name to copy

-l layer_name: layer name in dataset (optional)

autoconnect tolerance: create topology automatically with the given double tolerance

remove: remove connectivity or network, depending on native format support (-nt)

-nt: use native network format (now unavailable)

So the way using utility is similar to my previous utility: gnminfo, which soon will be using only for getting info about the existing networks. All managing functionality will fully migrate to gnmmanage and it will be more close to the gdalmanage.

The new method GNMNetwork::AutoConnect() tries to build the topology of the network automatically, as I described in my previous post. Remember, that if you will try to build a topology on several layers two times in different spatial reference systems - the results will be different. For example in our case the common network's SRS is 'EPSG:4326'. If we create a network in 'EPSG:3857', import all layers as previous and AutoConnect them with the same tolerance again (for me it was 0.00005) - the topology will differ from previous case.

gnmanalyse

The gnmmanage utility intends to provide all analysing functionality of GNM. It has the following usage:

>gnmanalyse.exe --long-usage

Usage: gnmanalyse [--help][-q][-quiet][--utility_version][--long-usage]

[dijkstra start_gfid end_gfid [-ds ds_name][-f ds_format][-l layer_name]]

gnm_name

dijkstra start_gfid end_gfid: calculates the shortest path between two points

-ds ds_name: the name&path of the dataset to save the layer with shortest path. Not need to be existed dataset

-f ds_format: define this to set the fromat of newly created dataset

-l layer_name: the name of the resulting layer. If the layer exist already — it will be rewritten

For now it has the usage of only one method: GNMStdRoutingAnalyser::DijkstraShortestPath(). For example lets use it on the network, which had been built with the gnmmanage, the following way:

>gnmanalyse.exe dijkstra 718 1185 -ds ..\shortestpath.shp -f "ESRI Shapefile" -l shortestpath ..\network_data

Path between 718 and 1185 found and saved to the ..\shortestpath.shp successfully

So the path between features with 718 and 1185 GFIDs will be found and saved into the instantly created or opened Shapefile layer.

Week #9. Working with features and gnminfo python tests

There are several methods were added to gnm: CreateFeature(), SetFeature(), DeleteFeature() which do the required actions for the connectivity and then call the corresponding GDALDataset methods.

This week I've also finally coped with python in GDAL. So for today there is a working python test which tests the gnminfo utility and can be used in command line like the following (this was tested on Windows):

D:\GitHub\gdal\autotest\utilities>c:\python27\python.exe test_gnminfo.py
  TEST: test_gnminfo_1 ... success
  TEST: test_gnminfo_2 ... success
  TEST: test_gnminfo_3 ... success
  TEST: test_gnminfo_4 ... success
  TEST: test_gnminfo_5 ... success

Test Script: test_gnminfo
Succeeded: 5
Failed:    0 (0 blew exceptions)
Skipped:   0
Expected fail:0
Duration:  0.47s

Found libgdal we are running against : D:\GitHub\gdal-build\bin\gdal20.dll

, where test #1 is simple --help test, test #2 creates a connectivity in autotest/tmp, test #3 gets info about it, test #4 imports some layers from autotest/gnm/data and test #5 deletes the connectivity.

Week #8. Automatic graph building

According GitHub commit: https://github.com/MikhanGusev/gdal/commit/12dc0678c78329f65f885958103e056491fadcd1

Automatic graph building in GNM

Similar to my old concept there can be several automatic graph building algorithms in GNM, because this mechanism is implemented as the pattern "Strategy". Firstly we must initialize the strategy with its own settings, than set the strategy for the GNMConnectivity via SetAutoConnectStrategy() and finally call the GNMConnectivity::AutoConnect(). The system graph layer will be filled with new connections.
Now there is only one algorithm in GDAL source tree - the one, which I'd implemented already in an old API. Now it is integrated to the GNM and builds graph basing on the set of line and point layer ids of the current GNMConnectivity.
So now GNM has a capability not just to create a set of obligatory layers over a dataset, but to create a real connectivity among features in this dataset, if it is needed.

Features

* We can modify any built connection via GNMConnectivity::ReconnectFeatures() and delete it via GNMConnectivity::DisconnectFeatures().

* If the graph is already built and we add some not connected features to the network we can anytime call AutoConnect() again and it will add additional connections not rebuilding old.

* The graph can be cleared anytime via GNMConnectivity::DisconnectAll().

* Virtual AutoConnect() method intends to be a generic for future derived classes for the concrete network formats. For example in GNM pgRouting Connectivity class it can call pgr_createTopology.

Convenient methods

GNMConnectivity::ConnectAllLinePoint() uses AutoConnect() but firstly counts all line and point layers, passing their ids as the parameters when the connection strategy is being created.

Week #7. Reviewed timeline

During this week I've:
- worked with python tests which I had to implement as it usual for testing GDAL. Unfortunately I didn't have enough time to fully implement them;
- chosen a final way of applying my changes in GDAL library: a fork of the official GDAL GitHub repo: https://github.com/MikhanGusev/gdal;
- added several small methods to GNM API which were committed with all my previous GNM work in the initial commit of MikhanGusev/gdal.

I also made a reviewed timeline which more strictly describes the rest of my summer of code, though it doesn't differ so much from the general plan. The main differ is that I'm no longer implementing the driver, while I implement the separate set of classes. This differ causes the shifting of the timeline. Also, some steps which I planed for the ending (like API-testing applications) I've already partly implemented, so the order of general plan steps now differs a bit.

1. (July 5 – July 11) Complete python tests of current functionality

1.1. API tests (GNMConnectivity, GNMManager)

1.2. Application tests (gnminfo)

2. (July 5 – July 25) Complete moving all functionality to new API in this order:

2.1. ~(July 5 – July 11) Automatic connectivity building

2.2. ~(July 12 – July 18) Features addition and deletion

2.3. ~(July 12 – July 18) Graph analysis

2.4. ~(July 19 – July 25) Network's business logic

3. (Also July 19 – July 25) Another console application which works with the new API.

4. (July 26 – August 1) Python tests of the rest of functionality and applications.

5. (Also July 26 – August 1) Documentation and tutorial.

6. (August 2 – August 11) Either create method smth like GNMConnectivity :: ImportFromPGRouting() or implement a full support of pgRouting as I described here.

Week #6. GNM in GDAL 2.0

Take a look at my repo to see the source code with comments and methods description.

GNM API
(source code at <gdal root>/gnm)

In general the approach is like in one of my first posts, but now we have the API, which integrated into GDAL library (for the moment only in my fork of GDAL repo) and this API has a key change: it is no longer the OGR driver, not only because in GDAL 2.0 all migrates to GDAL drivers but also because of my concept which I described earlier. So now it is the separate set of classes.

Application
(source code in <gdal root>/apps/gnminfo.cpp)

This console utility is similar to those like gdalinfo.exe or ogrinfo.exe and was made to provide the use of several GNM API methods. Type this in command line:

>gnminfo.exe --long-usage

and you will see its usage:

Usage: gnminfo [--help-general] [-progress] [-quiet]
               [-create [-f format_name] [-t_srs srs_name] [-dsco NAME=VALUE]...]
               [-i]
               [-cp src_dataset_name] [-l layer_name]
               gnm_name

 -f format_name: output file format name, possible values are:
    [ESRI Shapefile]
 -progress: Display progress on terminal. Only works if input layers have the "fast feature count" capability
 -dsco NAME=VALUE: Dataset creation option (format specific)
 -cp src_datasource_name: Datasource to copy
 -l layer_name: Layer name in datasource (optional)

So with this utility you can now do the following. Note: we assume that the "connectivity" is a set of special system layers which store the network data (contrary to the set of layers with spatial data on which the connectivity though is based).

1. Create a connectivity:

>gnminfo.exe -create -f "ESRI Shapefile" -t_srs "EPSG:3857" -dsco "con_name=my_connectivity_1" ..\data\my_con

The connectivity will be created in the Shapefile format at the given path and with the passed parameters. Technically there will be created several system layers (in our case several .dbf files for Shapefile dataset).

2. Import layers with spatial data:

>gnminfo.exe -cp ..\data -l kolodci ..\data\my_con
>gnminfo.exe -cp ..\data -l lines ..\data\my_con
>gnminfo.exe -cp ..\data -l reshetki \..\data\my_con

These 3 layers will be copied with all features from an external dataset to a given connectivity with special names. The according changes will be made in system layers and also the system fields will be added to this data in order to maintain the work with future network.

3. Give an info about connectivity:

>gnminfo.exe -i ..\data\my_con

 The info will be printed:

Connectivity opened successfully at ..\data\my_con
1: _gnm_meta (None)
2: _gnm_graph (None)
3: _gnm_classes (None)
4: gnm_kolodci_point (Point)
5: gnm_lines_line (Line String)
6: gnm_reshetki_point (Point)

Connectivity metadata [Name=Value]:
    [common_srs=EPSG:3857]
    [gnm_version=1.0.0]
    [gfid_counter=1350]
    [con_name=my_connectivity_1]
SRS WKT:
PROJCS["WGS 84 / Pseudo-Mercator",
    GEOGCS["WGS 84",
        DATUM["WGS_1984",
    <... Additional info about SRS ...>
    AUTHORITY["EPSG","3857"]]

We see the system and simple layers, and also the contents of _gnm_meta - the network metadata.

The connect, disconnect, reconnect methods were not used in the gnminfo utility. If we want to make some connections in the created connectivity we can just call ConnectFeatures() and pass the global identifiers (which were set automatically when the layers were imported) to it. The graph layer (_gnm_graph) will be modified. As I planed my next steps will be to widen the GNM API and particularly to add an automatic graph building (so not to use ConnectFeatures() manually on the big sets of spatial data). Maybe I also make a similar utility to test this functionality.

Week #4 and #5

These two weeks were hard for me, because I had to spend additional time to prepare and defend my Master's thesis. Now it is successfully done and I fully concentrate on GSoC coding.
Nevertheless I have already done some important things:

* Made some main methods of a new GNM API: create and remove connectivity.
* Integrated it directly into GDAL 2.0dev (my fork https://github.com/MikhanGusev/gdal-svn/tree/cmake4gdal), built the library and tested with my old testing application, improving it a bit in order to use new GDAL 2.0.

So, according to my concept the following algorithm is actual for these methods just now:

Income: we have a set of spatial data. It can be void (without layers) or full of layers.
1. Initialize GDALDataset.
2. Create the GNMConnectivity over this dataset. The according system layers and fields will be created.
3. ... <here will be modifying, analysis and so on>
4. Remove the connectivity if it is necessary to restore an old "pure of network" dataset, so:
Outcome: we have the initial set of spatial data without any changes.

I continue to move old methods to the new API and to implement my concept.

Week #3. Some old methods completed

Some new methods have been added to an old API:
[commit]

* New decorator for connectivity behavior. It checks whether the features being connected have the according geometries: wkbPoint for source and target vertexes and wkbLine for edge. If this decorator hasn't been set any geometries must "lie under" the graph (even poligons).

* Delete feature method. Deletes the feature from data source, from the according system tables and from the graph.

* Remove edge, remove vertex methods. The removing methods of the graph.

All these methods will be moved to the new API in future.

Week #2. New GDAL networking API

In this post I would like to propose the final appearance of the new GDAL networking API.

I suppose, that implementing a network functionality as a GDAL driver has the following disadvantages:

1. The concept of driver in general is to provide a "bridge" between GDAL abstraction and the real data format. There is no network format itself, because every vector format stores the network (or simply connectivity) together with spatial objects or in the separate set of layers but anyway the same format.
2. An implementation of a new GDALDataset must be generic and implement only the defined interface, while we need to add new network functionality.We will need to do a type cast if we want to use network methods of the new GDALDataset.
3. Network is usually built over the ready set of spatial data. In case of driver there is a need firstly to create a void network and then import some layers from external data sets.
4. If we inherit the GDALDataset a lot of unnecessary for networks methods, such as working with rasters, will be inherited too.
5. Some drivers, which serves as an "inner" for networking driver does not support several layers, such as GeoJSON, so there is no capability to create a network over them, while this requires several layers.
6. I also suppose that some mechanisms of network model extensions, which I've implement in my driver are a bit excess and I think it is unnecessary to include it into GDAL library.

Solution

The separate class GNMConnectivity represents a network as an object and aggregates a GDALDataset instance, but not inherits it. The network data and spatial/attribute in fact are not separable (just additional layers or fields), while the GNMConnectivity "knows" which data from the data set refers to network data and operates it. The network can be built only over the existing data set (though, it can be void), wrapping it and adding missing network layers/field.

All network functionality in GDAL will be split to two levels: GNMConnectivity (level 0) and GNMNetwork (level 1). The 0 level represents a simple graph (simple connectivity or topology) which holds the connections among features. The level 1 is based on the level 0 and adds the support of network's business logic. For each level the default network functionality will be provided for any GDAL-supported vector format (at first actually for several), as it is now in my driver.

The derived classes intend to provide a support of native networking of different formats as an alternative to default. Some of these formats (like pgRouting or GML) have just connectivity capabilities without any business logic support, while others (Oracle Spatial, GDF or even ArcGIS networks) have the concept of network constraints (connectivity rules, turn restrictions). The main point is that GNMConnectivity / GNMNetwork provides the generic interface for these network formats, like GDAL provides the generic interface for spatial formats.

The derived classes also define how the network data stores in its format. For example for SpatiaLite VirtualNetwork the according "driver" will write all network data to the Roads_net_data table and to corresponding NodeFrom and NodeTo columns. If use of such "driver" hadn't been selected - the corresponding network_ layers in this simple SpatiaLite data set will be created (see my previous posts about how the network is stored). Another example: in the native form the GML "driver" will write network data to the <gml::TopoComplex>, <gml::Node> and <gml::Edge>.

API

This is a set of classes with public functions, which should be used:

Take a look at detailed description of classes, methods and its parameters:https://github.com/MikhanGusev/gnm/blob/master/gnm.h

C API: https://github.com/MikhanGusev/gnm/blob/master/gnm_api.h

network2network

The following code can be an example of using GDAL network API. It is a part of possible future utility network2network which converts the networks of different formats:

void main (void)
{
    //...
    // poPGDS initialized as a PostGIS Dataset. It has spatial data and connectivity
    // over it already.
    // poShpDS initialized as a Shapefile Dataset. It has all corresponding spatial data
    // (with the same GFIDs also), or the process of network copying will fail or be incorrect.
   
    GNMConnectivity *poPGCon = GNMManager::OpenConnectivity(poPGDS,TRUE);
    if (poPGCon == NULL) return;
    
    OGRSpatialReference *poSRS = poPGCon->GetCommonSpatialRef();
    GNMConnectivity *poShpCon = GNMManager::CreateConnectivity(poShpDS,poSRS,NULL);
    if (poShpCon == NULL) return;
   
    GNMConnection *con;
    poPGCon->ResetReading();
    while ((con = poPGCon->GetNextConnection()) != NULL)
    {
        GNMErr err = poShpCon->ConnectFeatures(con->nSourceGFID,
                                               con->nTargetGFID
                                               con->nConnectorGFID
                                               con->dDirCost,
                                               con->dInvCost,
                                               con->dir);           
        delete con;
       
        if (err != GNMERR_NONE)
        {
            poShpCon->DisconnectAll();
            return;
        }
    }
   
    // The correct resources freeing.
    //...   
}

Week #1. Network's business logic

As I mentioned in one of my previous posts (http://gsoc2014gnm.blogspot.ru/2014/05/model-in-action-2-analyse-network.html) all this week I worked on network's business logic. The providing capabilities are similar, for example, to ArcGIS connectivity rules, but more general: http://resources.arcgis.com/en/help/main/10.1/#/na/002r0000000q000000/

All business logic of the network is based on the string-like rules. Each string describes the rule for the class (layer) or for the whole network. It is easy to set them and remove, while they are stored in a single non-geometry layer. When the OGRGnmDataSource::addRule() is called, this string is added to the network_rules layer and immediately built into the inner structures. The rules have an effect when the methods like OGRGnmDataSource:: connectFeatures() are called.

Now the rule syntax looks like the following (but it will be certainly widen in future):

CLASS <Class name> [COSTS <Attribute name>] 
[BEHAVES AS EMITTER | TRANSMITTER | RECEIVER]

NETWORK CONNECTS <Class name 1> WITH <Class name 2> [VIA  <Class name 3>]

[] means that these parts can be set separately in different strings;
| means that one of the operands can be used at the same time;

So, let's take a look at the example how to use rules.


// Code begins --------------------------------------------------------------------------

// Initialize the dataSrc as OGRGnmDataSource*.
// Import some layers: tanks, kolodci, lines, reshetki.
// The network is not created yet.

dataSrc->addRule("CLASS tanks BEHAVES AS EMITTER"); // String 1.
dataSrc->addRule("CLASS lines COSTS L"); // String 2.
dataSrc->addRule("NETWORK CONNECTS kolodci WITH kolodci VIA lines"); // String 3.
dataSrc->addRule("NETWORK CONNECTS tanks WITH kolodci"); // String 4.

// The inner rule structures will be built.
// Now, let's create a network.

dataSrc->connectFeatures(0, 1, -1, 0.0, 0.0); // 0 and 1 are GFIDs of the tanks layer.
// The result will be an error, while there is no connectivity rule between two features of tanks.

dataSrc->connectFeatures(145, 146, 5, 0.0, 0.0); // 145, 146 are kolodci features. 5 is lines feature.
// The corresponding record will be created in the network_graph, because of String 3.
// The costs of this connection will be the values of an "L" field of lines layer, because of String 2.

// Code ends ---------------------------------------------------------------------------


After that we can use a GNMSimpleNetworkAnalyser::resourceDestribution() method. It will firstly collect all source points (all tanks features) and create a connected component starting from them, because of a String 1.

Take a look at my github to see the source code: https://github.com/MikhanGusev/gnm

Model's architecture

Current model's architecture is the following (with the description at the project's repository https://github.com/MikhanGusev/gnm/blob/master/description.md):

But it is also a question now, how this new API will look like in GDAL. There are several ideas:
1. Leave all as it is now - there will be an OGR driver with additional non-generic OGR behavior, such as connectFeatures() method.

2. Create a set of new C API like functions. For example OGR_GMN_DS_ConnectFeatures(hD
S, ...) where there is a user's responsibility to pass hDS as OGRGmnDataSource.

3. Similar to (2), but fully object-oriented approach is to create a separate class hierarchy (like OGRSFDriver - OGRDataSource - OGRLayer). It will require the initialized data source of the spatial format. For example:

OGRDataSource *poDS;

// initialization of poDS ...

OGRNetwork *poNetwork;

poNetwork = OGRNetwork::create(poDS); // or OGRNetwork::open(poDS)

//...

poNetwork->createFeatures(...);

4.Use pseudo-SQL functions passed through the OGRDataSource::ExecuteSQL() method. For example ExecuteSQL("SELECT connectFeatures(/*...*/)")

Model in action #2. Analyse network

In this post I would like to describe the current network analysis functionality of the GDAL/OGR network model. If you want to know how this all "technically" works you could take a look at the description document at my Github.

Shortest path search

The shortest path problem is the typical routing problem of the road networks. To define the shortest path between to points we will use the shortestPath(long startGfid, long endGfid, OGRLayer *resultLayer) method of the simplenetworkanalysis.h package (which for its turn uses Dijkstra shortest path tree search algorithm). Let's create a new network as at was shown at previous post, defining the Esri Shapfile as the spatial format now. Note: I made some preparations to visualize the results and save them at the QGIS project, which can be also found at my Github. For example, I set the "kolodci" layer's labeling options so the GFIDs of this layer features are displayed (using the joining with network_features layer).

When all features are added and connected we firstly create a new layer (also shape) which will serve as a holder of the resulting path. Let's find the shortest path between features with 801 and 807 GFIDs. We pass the new layer and these GFIDs to the shortestPath() and after the calculations the new layer will be filled with the geometries of a built path (displayed in red).

That was the simple task because there is no alternative path between 801 and 807. Let's create them. We connect 816 with 802 and 819 with 806 and use the method with the same parameters again. The new shortest path will be found. This path will lie through the connection between 816 and 802, because the costs of the network's edges were formed with the line lengths (see the previous post) and this path is definitely shorter. Note, that while the two new connections are "logical" there are no real geometries under them and so they can not be displayed.

Now let's try another interesting capability of the model - features blocking. We block the 815 feature and that means that it will not be considered in the following graph tracing, like it is now removed from the graph. So the previous path becomes unavailable and the shortest path will lie through 819 and 806.

If we block then 818 feature there will be no path between 807 and 801 and the according error code will be returned.

Resource distribution

In the field of engineering networks the resource can be anything that spreads over the network (water, gas, electricity) from the emitter features, along the transmitter features, to the receiver features. So there is a task to see, which part of network is covered by resource in different situations, such as blocking (breaking) of some network elements.

The concept of rules plays the key role in the work with resource. It is proposed that all features of the class, that marked as EMITTER will “emit” the resource. Thus the resourceDestribution() method of the simplenetworkanalysis.h package can use the connected component search algorithm (the concrete implementation is a Breadth-first search) to define which (line) features are connected to these emitters, that means that they have a resource. Let's open our previous network and make some preparations before the resource can be collected. 

We say that the three features from the layer “tanks” (marked as stars) will play the role of emitters. We connect them with the nearest features: 0 with 807, 2 with 721 and 1 with 717. Now let's create the resulting layer and pass it to the resourceDestribution(). This layer will be filled with the features, showing the resource spreading from the multiple emitters.

Let's imagine that some junctions in our water network are broken. We block 720 and 718 and see that though a small part of network has no water now, the most part of it still has it. 

To resolve this “problem” we can build a temporary pipe from any place where the water persists. We connect 721 with 719 and see that the void section is now full with water.

The rule syntax and its analysis is the subject that I'm working on now. In the code of resourceDestribution() I simply pass the GFIDs of the “emitters” instead of parse the rule string and use some inner structures. The rules itself are more useful and describe such things as cost assignment and allowing connections verification. So I suppose that my next steps will be the following: complete and debug all, that I have already, implement the rules support and make some good tests.

Model in action #1. Building network

In this post I would like to tell about the current status of the building and storing network capabilities in the GDAL/OGR network model. To show the progress I will use my small test application and QGIS to visualize the spatial data.

Manual network creation

We start from creating a network with defining the GIS format, in which the spatial data along with all its network data will be stored. I chose a PostGIS. Though the created void network has neither spatial nor network data there are already all system tables. We add a new point layer called "tanks" and create some features in it. The network_features table will be updated with new Global Feature Identifers (GFIDs) for these features, which were assigned automatically. Now we have a set of spatial data, but don't have any topological relations among the features.

As for code - all the time before we used only the generic methods of the OGRGnmDataSource and OGRGnmLayer, such as OGRDataSource::createLayer() or OGRLayer::createFeature(). When it's time to call the specific network's behavior we need to use a type cast. For connection we call for example OGRGnmDataSource::connectFeatures(0, 1, -1, 0.0, 0.0, 2), where parameters are:

1), 2) Source and target feature GFIDs. Now these features are vertexes in a graph.
3) Connector feature GFID. If we pass -1 it means that there is no physical feature between source and target and the connection is logical. This is an edge in a graph.
4), 5) The cost of edge from source to target (direct) and from target to source (inverse).
6) Direction of edge. 2 equals to bi-directional edge.

Now the network's graph is formed. We can see in pgAdmin that there were automatically created two system edges between the connected vertexes in the network_sysedges table.

Automatic network creation

Now we are going to build a network over the existing set of spatial data. Let's take a piece of the city's drain network, which includes one line Shapefile with pipes and two point Shapefiles with wells.

Firstly we open the created on the first step network and then import this data. An importing is similar to ogr2ogr utility, while it copies all features of the layer from the external data source to our one. The coordinates of the imported features are transformed to the global network SRS. After the successful importing there is no built network yet. We must connect the required features manually (for such big amount of features it can be too difficult) or use the automatic graph building capability. In our example set of data each line feature starts and ends geographically right at the point features (or very close to them). So we can use the GNMLinePointBuilder strategy to build the graph. We define the snap tolerance (in our case it will equal 0.00005) and pass it with the layers' ids to the strategy constructor. After the successful building we get the ready graph. Note, that during the graph building the specific cost assignment behavior was used. Thus, GNMGeometryCostConnection decorator is responsible for measuring the length of the edge feature.

Conclusion

Though, there is already some network functionality in OGR there is still much work. First of all the driver is not included in GDAL. There are also many small unfinished points in the code which must be completed, such as the correct network deletion behavior or correct working with SpatiaLite format.

But by this time we can see the following: with the help of the network model based on the OGR driver it is possible to create networks. The network is a set of layers (for PostGIS it is a set of DB tables) which exist along with spatial layers. The basis of network is a graph. It can be built over spatial data manually or automatically. In the next post I would like to show what can be done from network analysis with the built network.

Introduction

Hello everyone!

In my first posts I would like to tell about what does the model look like today and what I've done already in this field. The code and technical description can be found at my Github, so I won't concentrate on it here. In my next few posts I would like to demonstrate the network model in action, to show what can be already done from the user's point of view with the concept which I propose.