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.
[GSoC 2014] GDAL/OGR Geographic Network Model
Friday, August 15, 2014
Friday, August 8, 2014
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:
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
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 7403. Now it is possible to connect features without geometries - the according system features will serve as graph edges;
// 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.
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
Friday, August 1, 2014
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:
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.
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:
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.
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 --long-usageUsage: 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 stringautoconnect tolerance: create topology automatically with the given double toleranceremove: remove connectivity or network, depending on native format support (-nt)-nt: use native network format (now unavailable)
The piece of network looks like the following:gnmmanage.exe create -f "ESRI Shapefile" -t_srs "EPSG:4326" -dsco "net_name=my_network_1" ..\network_datagnmmanage.exe import ..\in_data\krasnogorsk -l lines ..\network_datagnmmanage.exe import ..\in_data\krasnogorsk -l kolodci ..\network_datagnmmanage.exe import ..\in_data\krasnogorsk -l reshetki ..\network_datagnmmanage.exe rule "CLASS gnm_lines_line COSTS L" ..\network_datagnmmanage.exe rule "CLASS gnm_lines_line INVCOSTS L" ..\network_datagnmmanage.exe rule "CLASS gnm_lines_line DIRECTS my_dir" ..\network_datagnmmanage.exe autoconnect 0.00005 ..\network_data
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.
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.gnmmanage.exe connect 717 744 231 ..\network_data
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:
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....gnmmanage.exe rule "NETWORK CONNECTS gnm_reshetki_point WITH gnm_kolodci_point VIA gnm_lines_line" ..\network_datagnmmanage.exe rule "NETWORK CONNECTS gnm_kolodci_point WITH gnm_kolodci_point VIA gnm_lines_line" ..\network_datagnmmanage.exe autoconnect 0.00005 ..\network_data
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.
Friday, July 25, 2014
Week #10. Network analysis in GNM
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:
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.>gnmmanage.exe --long-usageUsage: 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 toleranceremove: remove connectivity or network, depending on native format support (-nt)-nt: use native network format (now unavailable)
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:
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 --long-usageUsage: 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
So the path between features with 718 and 1185 GFIDs will be found and saved into the instantly created or opened Shapefile layer.>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
Friday, July 18, 2014
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):
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, 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.
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
Friday, July 11, 2014
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.
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.
Friday, July 4, 2014
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.
- 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.
Subscribe to:
Posts (Atom)