/****************************************************************************** * $Id$ * * Project: GDAL/OGR Geography Network support (Geographic Network Model) * Purpose: GNM general public declarations. * Authors: Mikhail Gusev (gusevmihs at gmail dot com) * Dmitry Baryshnikov, polimax@mail.ru * ****************************************************************************** * Copyright (c) 2014, Mikhail Gusev * Copyright (c) 2014-2015, NextGIS * * Permission is hereby granted, free of charge, to any person obtaining a * copy of this software and associated documentation files (the "Software"), * to deal in the Software without restriction, including without limitation * the rights to use, copy, modify, merge, publish, distribute, sublicense, * and/or sell copies of the Software, and to permit persons to whom the * Software is furnished to do so, subject to the following conditions: * * The above copyright notice and this permission notice shall be included * in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER * DEALINGS IN THE SOFTWARE. ****************************************************************************/ #ifndef GNM #define GNM #if defined(__cplusplus) && !defined(CPL_SUPRESS_CPLUSPLUS) #include "ogrsf_frmts.h" #endif #include "gnmgraph.h" // Direction of an edge. typedef int GNMDirection; // We use int values in order to save them to the // network data. // Network's metadata parameters names. #define GNM_MD_NAME "net_name" #define GNM_MD_DESCR "net_description" #define GNM_MD_SRS "net_srs" #define GNM_MD_VERSION "net_version" #define GNM_MD_RULE "net_rule" #define GNM_MD_FORMAT "FORMAT" #define GNM_MD_FETCHEDGES "fetch_edge" #define GNM_MD_FETCHVERTEX "fetch_vertex" #define GNM_MD_NUM_PATHS "num_paths" #define GNM_MD_EMITTER "emitter" // TODO: Constants for capabilities. //#define GNMCanChangeConnections "CanChangeConnections" typedef enum { /** Dijkstra shortest path */ GATDijkstraShortestPath = 1, /** KShortest Paths */ GATKShortestPath, /** Recursive Breadth-first search */ GATConnectedComponents } GNMGraphAlgorithmType; #if defined(__cplusplus) && !defined(CPL_SUPRESS_CPLUSPLUS) /** * General GNM class which represents a geography network of common format. * * @since GDAL 2.1 */ class CPL_DLL GNMNetwork : public GDALDataset { public: GNMNetwork(); virtual ~GNMNetwork(); // GDALDataset Interface const OGRSpatialReference* GetSpatialRef() const override { return GetSpatialRefFromOldGetProjectionRef(); } virtual char **GetFileList(void) override; // GNMNetwork Interface /** * @brief Create network system layers * * Creates the connectivity (the "network path" of data) over the dataset * and returns the resulting network. * NOTE: This method does not create any connections among features * but creates the necessary set of fields, layers, etc. * NOTE: After the successful creation the passed dataset must not be * modified outside (but can be read as usual). * NOTE: For the common network format the creation is forbidden if the * passed dataset already has network system layers and OVERWRITE creation * option is FALSE. * * @param pszFilename - A path there the network folder (schema, etc.) will * be created. The folder (schema, etc.) name get * options. * @param papszOptions - create network options. The create options * specific for gnm driver. * @return CE_None on success */ virtual CPLErr Create( const char* pszFilename, char** papszOptions ) = 0; /** * @brief Open a network * @param poOpenInfo GDALOpenInfo pointer * @return CE_None on success */ virtual CPLErr Open( GDALOpenInfo* poOpenInfo ) = 0; /** * @brief Delete network. Delete all dependent layers * @return CE_None on success */ virtual CPLErr Delete() = 0; /** * @brief GetName - a network name. The value provided to create function * in GNM_MD_NAME key. While creation this value used to create the * folder or db schema name. But can be changed after creation. * @return Network name string */ virtual const char* GetName() const; /** * @brief GetVersion return the network version if applicable * @return version value */ virtual int GetVersion() const { return 0;} /** * @brief DisconnectAll method clears the network graph * @return CE_None on success */ virtual CPLErr DisconnectAll () = 0; /** * @brief GetFeatureByGlobalFID search all network layers for given feature * identificator. * @param nGFID feature identificator. * @return OGRFeature pointer or NULL. The pointer should be freed via * OGRFeature::DestroyFeature(). */ virtual OGRFeature *GetFeatureByGlobalFID (GNMGFID nGFID) = 0; /** * @brief Create path between start and end GFIDs. * @param nStartFID - start identificator * @param nEndFID - end identificator * @param eAlgorithm - The algorithm to get path * @param papszOptions - algorithm specific options * @return In memory OGRLayer pointer with features constituting * the shortest path (or paths). The caller have to free * the pointer via @see ReleaseResultSet(). */ virtual OGRLayer *GetPath (GNMGFID nStartFID, GNMGFID nEndFID, GNMGraphAlgorithmType eAlgorithm, char** papszOptions) = 0; protected: /** * @brief Check if network already exist * @param pszFilename - path to network (folder or database * @param papszOptions - create options * @return TRUE if exist and not overwrite or FALSE */ virtual int CheckNetworkExist( const char* pszFilename, char** papszOptions ) = 0; //! @cond Doxygen_Suppress const char *_GetProjectionRef(void) override; //! @endcond protected: //! @cond Doxygen_Suppress CPLString m_soName; CPLString m_soSRS; //! @endcond }; class GNMRule; class OGRGNMWrappedResultLayer; /** * GNM class which represents a geography network of generic format. * * @since GDAL 2.1 */ class CPL_DLL GNMGenericNetwork: public GNMNetwork { public: GNMGenericNetwork(); virtual ~GNMGenericNetwork(); // GDALDataset Interface virtual int GetLayerCount() override; virtual OGRLayer *GetLayer(int) override; virtual OGRErr DeleteLayer(int) override; virtual int TestCapability( const char * ) override; virtual OGRLayer *CopyLayer( OGRLayer *poSrcLayer, const char *pszNewName, char **papszOptions = nullptr ) override; virtual int CloseDependentDatasets() override; virtual void FlushCache(void) override; // GNMNetwork Interface virtual CPLErr Create( const char* pszFilename, char** papszOptions ) override = 0; virtual CPLErr Delete() override; virtual int GetVersion() const override; /** * @brief GetNewGlobalFID increase the global ID counter. * @return New global feature ID. */ virtual GNMGFID GetNewGlobalFID(); /** * @brief Get the algorithm name * @param eAlgorithm GNM algorithm type * @param bShortName Indicator which name to return - short or long * @return String with algorithm name */ virtual CPLString GetAlgorithmName(GNMDirection eAlgorithm, bool bShortName); /** * @brief AddFeatureGlobalFID add the FID <-> Layer name link to fast access * features by global FID. * @param nFID - global FID * @param pszLayerName - layer name * @return CE_None on success */ virtual CPLErr AddFeatureGlobalFID(GNMGFID nFID, const char* pszLayerName); /** * @brief Connects two features via third feature (may be virtual, so the * identificator should be -1). The features may be at the same layer * or different layers. * @param nSrcFID - source feature identificator * @param nTgtFID - target feature identificator * @param nConFID - connection feature identificator (-1 for virtual connection) * @param dfCost - cost moving from source to target (default 1) * @param dfInvCost - cost moving from target to source (default 1) * @param eDir - direction, may be source to target, traget to source or both. * (default - both) * @return CE_None on success */ virtual CPLErr ConnectFeatures (GNMGFID nSrcFID, GNMGFID nTgtFID, GNMGFID nConFID = -1, double dfCost = 1, double dfInvCost = 1, GNMDirection eDir = GNM_EDGE_DIR_BOTH); /** * @brief Remove features connection * @param nSrcFID - source feature identificator * @param nTgtFID - target feature identificator * @param nConFID - connection feature identificator * @return CE_None on success */ virtual CPLErr DisconnectFeatures (GNMGFID nSrcFID, GNMGFID nTgtFID, GNMGFID nConFID); /** * @brief Find the corresponding identificator in graph (source, target, * connector) and remove such connections. * @param nFID - identificator to find. * @return CE_None on success */ virtual CPLErr DisconnectFeaturesWithId(GNMGFID nFID); /** * @brief Change connection attributes. Search the connection by source * feature identificator, target feature identificator and connection * identificator. * @param nSrcFID - source feature identificator * @param nTgtFID - target feature identificator * @param nConFID - connection feature identificator * @param dfCost - new cost moving from source to target * @param dfInvCost - new cost moving from target to source * @param eDir - new direction * @return CE_None on success */ virtual CPLErr ReconnectFeatures (GNMGFID nSrcFID, GNMGFID nTgtFID, GNMGFID nConFID, double dfCost = 1, double dfInvCost = 1, GNMDirection eDir = GNM_EDGE_DIR_BOTH); virtual CPLErr DisconnectAll() override; virtual OGRFeature *GetFeatureByGlobalFID(GNMGFID nFID) override; /** * @brief Create network rule * * Creates the rule in the network according to the special syntax. These * rules are declarative and make an effect for the network when they exist. * Each rule for layer can be created only if the corresponding layer * existed and removed when the layer is being deleted. * * Rules syntax for the common network format in GNM contains the key words * (words in capital letters or signs) and the modifiers which refers to the * network objects. All the following combinations are available: * * Notation: * layer1, layer2, layer3 - a layer names (the corresponding layers must be * exist; * field1 - a field name (field must be exist); * constant1 - any double constant; * string1 - any string; * * Rules describing which layer can be connected or not connected with each * other, and (optional) which layer must serve as a connector. By default * all connections are forbidden. But while network creation process the * rule to allow any connection added. During the connection process each * rule tested if this connection can be created. * * "ALLOW CONNECTS ANY" * "DENY CONNECTS ANY" * "DENY CONNECTS layer1 WITH layer2" * "ALLOW CONNECTS layer1 WITH layer2 VIA layer3" * * @param pszRuleStr Rule string which will parsed. If the parsing was * successful, the rule will start having effect immediately. * @return CE_None on success. */ virtual CPLErr CreateRule (const char *pszRuleStr); /** * @brief Delete all rules from network * @return CE_None on success. */ virtual CPLErr DeleteAllRules(); /** * @brief Delete the specified rule * @param pszRuleStr - the rule to delete * @return CE_None on success. */ virtual CPLErr DeleteRule(const char *pszRuleStr); /** * @brief Get the rule list * @return list of rule strings. The caller have to free the lis via CPLDestroy. */ virtual char** GetRules() const; /** * @brief Attempts to build the network topology automatically * * The method simply gets point and line or multiline layers from the * papszLayerList and searches for each line which connects two points: start * and end, so it can be not so effective in performance when it is called * on huge networks. * Note, when passing your tolerance value: this value will depend of spatial * reference system of the network, and especially of its 0,0 position * because dfTolerance is just divided by 2 and added/subtracted to/from * both sides of each line-feature end point forming thus the square area * around it. The first point-feature occurred inside this area will be given * as a start/end point for the current connection. So it is also desirable * that at least two layers are passed in papszLayerList (one point and one * line), and they are already connected "visually" ("geometrically"). * * @param papszLayerList A list of layers to connect. The list should be * freed via CSLDestroy. * @param dfTolerance Snapping tolerance. * @param dfCost Direct cost. * @param dfInvCost Inverse cost. * @param eDir Direction. * @return CE_None on success */ virtual CPLErr ConnectPointsByLines (char **papszLayerList, double dfTolerance, double dfCost, double dfInvCost, GNMDirection eDir); /** * @brief Change the block state of edge or vertex * @param nFID Identificator * @param bIsBlock Block or unblock * @return CE_None on success */ virtual CPLErr ChangeBlockState (GNMGFID nFID, bool bIsBlock); /** * @brief Change all vertices and edges block state. * * This is mainly use for unblock all vertices and edges. * * @param bIsBlock Block or unblock * @return CE_None on success */ virtual CPLErr ChangeAllBlockState (bool bIsBlock = false); virtual OGRLayer *GetPath (GNMGFID nStartFID, GNMGFID nEndFID, GNMGraphAlgorithmType eAlgorithm, char** papszOptions) override; protected: /** * @brief Check or create layer OGR driver * @param pszDefaultDriverName - default driver name * @param papszOptions - create options * @return CE_None if driver is exist or CE_Failure */ virtual CPLErr CheckLayerDriver(const char* pszDefaultDriverName, char** papszOptions); /** * @brief Check if provided OGR driver accepted as storage for network data * @param pszDriverName The driver name * @return true if supported, else false */ virtual bool CheckStorageDriverSupport(const char* pszDriverName) = 0; protected: //! @cond Doxygen_Suppress virtual CPLErr CreateMetadataLayer( GDALDataset* const pDS, int nVersion, size_t nFieldSize = 1024 ); virtual CPLErr StoreNetworkSrs(); virtual CPLErr LoadNetworkSrs(); virtual CPLErr CreateGraphLayer( GDALDataset* const pDS ); virtual CPLErr CreateFeaturesLayer( GDALDataset* const pDS ); virtual CPLErr LoadMetadataLayer( GDALDataset* const pDS ); virtual CPLErr LoadGraphLayer( GDALDataset* const pDS ); virtual CPLErr LoadGraph(); virtual CPLErr LoadFeaturesLayer( GDALDataset* const pDS ); virtual CPLErr DeleteMetadataLayer() = 0; virtual CPLErr DeleteGraphLayer() = 0; virtual CPLErr DeleteFeaturesLayer() = 0; virtual CPLErr LoadNetworkLayer(const char* pszLayername) = 0; virtual CPLErr DeleteNetworkLayers() = 0; virtual void ConnectPointsByMultiline(GIntBig nFID, const OGRMultiLineString *poMultiLineString, const std::vector &paPointLayers, double dfTolerance, double dfCost, double dfInvCost, GNMDirection eDir); virtual void ConnectPointsByLine(GIntBig nFID, const OGRLineString *poLineString, const std::vector &paPointLayers, double dfTolerance, double dfCost, double dfInvCost, GNMDirection eDir); virtual GNMGFID FindNearestPoint(const OGRPoint* poPoint, const std::vector& paPointLayers, double dfTolerance); virtual OGRFeature* FindConnection(GNMGFID nSrcFID, GNMGFID nTgtFID, GNMGFID nConFID); virtual void SaveRules(); virtual GNMGFID GetNewVirtualFID(); virtual void FillResultLayer(OGRGNMWrappedResultLayer* poResLayer, const GNMPATH &path, int nNoOfPath, bool bReturnVertices, bool bReturnEdges); //! @endcond protected: //! @cond Doxygen_Suppress int m_nVersion; GNMGFID m_nGID; GNMGFID m_nVirtualConnectionGID; OGRLayer* m_poMetadataLayer; OGRLayer* m_poGraphLayer; OGRLayer* m_poFeaturesLayer; GDALDriver *m_poLayerDriver; std::map m_moFeatureFIDMap; std::vector m_apoLayers; std::vector m_asRules; bool m_bIsRulesChanged; GNMGraph m_oGraph; bool m_bIsGraphLoaded; //! @endcond }; /** * GNM layer which represents a geography network layer of generic format. * The class override some OGRLayer methods to fulfill the network requirements. * * @since GDAL 2.1 */ class GNMGenericLayer : public OGRLayer { public: GNMGenericLayer(OGRLayer* poLayer, GNMGenericNetwork* poNetwork); virtual ~GNMGenericLayer(); // OGRLayer Interface virtual OGRGeometry *GetSpatialFilter() override; virtual void SetSpatialFilter( OGRGeometry * ) override; virtual void SetSpatialFilterRect( double dfMinX, double dfMinY, double dfMaxX, double dfMaxY ) override; virtual void SetSpatialFilter( int iGeomField, OGRGeometry * ) override; virtual void SetSpatialFilterRect( int iGeomField, double dfMinX, double dfMinY, double dfMaxX, double dfMaxY ) override; virtual OGRErr SetAttributeFilter( const char * ) override; virtual void ResetReading() override; virtual OGRFeature *GetNextFeature() override; virtual OGRErr SetNextByIndex( GIntBig nIndex ) override; virtual OGRErr DeleteFeature( GIntBig nFID ) override; virtual const char *GetName() override; virtual OGRwkbGeometryType GetGeomType() override; virtual OGRFeatureDefn *GetLayerDefn() override; virtual int FindFieldIndex( const char *pszFieldName, int bExactMatch ) override; virtual OGRSpatialReference *GetSpatialRef() override; virtual GIntBig GetFeatureCount( int bForce = TRUE ) override; virtual OGRErr GetExtent(OGREnvelope *psExtent, int bForce = TRUE) override; virtual OGRErr GetExtent(int iGeomField, OGREnvelope *psExtent, int bForce = TRUE) override; virtual int TestCapability( const char * ) override; virtual OGRErr CreateField( OGRFieldDefn *poField, int bApproxOK = TRUE ) override; virtual OGRErr DeleteField( int iField ) override; virtual OGRErr ReorderFields( int* panMap ) override; virtual OGRErr AlterFieldDefn( int iField, OGRFieldDefn* poNewFieldDefn, int nFlagsIn ) override; virtual OGRErr CreateGeomField( OGRGeomFieldDefn *poField, int bApproxOK = TRUE ) override; virtual OGRErr SyncToDisk() override; virtual OGRStyleTable *GetStyleTable() override; virtual void SetStyleTableDirectly( OGRStyleTable *poStyleTable ) override; virtual void SetStyleTable(OGRStyleTable *poStyleTable) override; virtual OGRErr StartTransaction() override; virtual OGRErr CommitTransaction() override; virtual OGRErr RollbackTransaction() override; virtual const char *GetFIDColumn() override; virtual const char *GetGeometryColumn() override; virtual OGRErr SetIgnoredFields( const char **papszFields ) override; /** Intersection */ OGRErr Intersection( OGRLayer *pLayerMethod, OGRLayer *pLayerResult, char** papszOptions = nullptr, GDALProgressFunc pfnProgress = nullptr, void * pProgressArg = nullptr ); /** Union */ OGRErr Union( OGRLayer *pLayerMethod, OGRLayer *pLayerResult, char** papszOptions = nullptr, GDALProgressFunc pfnProgress = nullptr, void * pProgressArg = nullptr ); /** SymDifference */ OGRErr SymDifference( OGRLayer *pLayerMethod, OGRLayer *pLayerResult, char** papszOptions, GDALProgressFunc pfnProgress, void * pProgressArg ); /** Identity */ OGRErr Identity( OGRLayer *pLayerMethod, OGRLayer *pLayerResult, char** papszOptions = nullptr, GDALProgressFunc pfnProgress = nullptr, void * pProgressArg = nullptr ); /** Update */ OGRErr Update( OGRLayer *pLayerMethod, OGRLayer *pLayerResult, char** papszOptions = nullptr, GDALProgressFunc pfnProgress = nullptr, void * pProgressArg = nullptr ); /** Clip */ OGRErr Clip( OGRLayer *pLayerMethod, OGRLayer *pLayerResult, char** papszOptions = nullptr, GDALProgressFunc pfnProgress = nullptr, void * pProgressArg = nullptr ); /** Erase */ OGRErr Erase( OGRLayer *pLayerMethod, OGRLayer *pLayerResult, char** papszOptions = nullptr, GDALProgressFunc pfnProgress = nullptr, void * pProgressArg = nullptr ); /** GetFeaturesRead */ GIntBig GetFeaturesRead(); /** AttributeFilterEvaluationNeedsGeometry */ int AttributeFilterEvaluationNeedsGeometry(); //! @cond Doxygen_Suppress /* consider these private */ OGRErr InitializeIndexSupport( const char * ); OGRLayerAttrIndex *GetIndex(); //! @endcond protected: //! @cond Doxygen_Suppress virtual OGRErr ISetFeature( OGRFeature *poFeature ) override; virtual OGRErr ICreateFeature( OGRFeature *poFeature ) override; protected: CPLString m_soLayerName; OGRLayer *m_poLayer; GNMGenericNetwork* m_poNetwork; std::map m_mnFIDMap; //! @endcond }; typedef enum { /** Rule for connect features */ GRTConnection = 0 } GNMRuleType; /** * @brief The simple class for rules * * By now we have only connect rules, so the one class is enough. Maybe in * future the set of classes for different rule types will be needed. * * @since GDAL 2.1 */ class CPL_DLL GNMRule { // to hopefully please Coverity Scan which complains about missing // move assignment operator for performance reasons GNMRule& operator==(GNMRule&&) = delete; public: /** Constructor */ GNMRule(); /** Constructor */ explicit GNMRule(const std::string &oRule ); /** Constructor */ explicit GNMRule(const char* pszRule); /** Constructor */ GNMRule(const GNMRule &oRule); /** Assignment operator */ GNMRule& operator=(const GNMRule&) = default; virtual ~GNMRule(); /** * @brief This function indicate if rule string was parsed successfully * @return true if rule is valid */ virtual bool IsValid() const; /** * @brief Indicator of any layer state * @return true if accept any layer */ virtual bool IsAcceptAny() const; /** * @brief This is for future use to indicate the rule type/ Now return only * GRTConnection type. * @return the rule type */ virtual GNMRuleType GetType() const; /** * @brief Check if connection can take place. * @param soSrcLayerName - the layer name * @param soTgtLayerName - the layer name * @param soConnLayerName - the layer name * @return true if can connect features from soSrcLayerName and soTgtLayerName * via soConnLayerName */ virtual bool CanConnect(const CPLString &soSrcLayerName, const CPLString &soTgtLayerName, const CPLString &soConnLayerName = ""); /** Return source layer name */ virtual CPLString GetSourceLayerName() const; /** Return target layer name */ virtual CPLString GetTargetLayerName() const; /** Return connector layer name */ virtual CPLString GetConnectorLayerName() const; /** Return rule as a string */ const char* c_str() const; /** Return rule as a string */ operator const char* (void) const; protected: //! @cond Doxygen_Suppress virtual bool ParseRuleString(); protected: CPLString m_soSrcLayerName; CPLString m_soTgtLayerName; CPLString m_soConnLayerName; bool m_bAllow; bool m_bValid; bool m_bAny; CPLString m_soRuleString; //! @endcond }; /** * @brief The OGRGNMWrappedResultLayer class for search paths queries results. * * @since GDAL 2.1 */ class OGRGNMWrappedResultLayer : public OGRLayer { public: OGRGNMWrappedResultLayer(GDALDataset* poDS, OGRLayer* poLayer); ~OGRGNMWrappedResultLayer(); // OGRLayer virtual void ResetReading() override; virtual OGRFeature *GetNextFeature() override; virtual OGRErr SetNextByIndex( GIntBig nIndex ) override; virtual OGRFeature *GetFeature( GIntBig nFID ) override; virtual OGRFeatureDefn *GetLayerDefn() override; virtual GIntBig GetFeatureCount( int bForce = TRUE ) override; virtual int TestCapability( const char * pszCap ) override; virtual OGRErr CreateField( OGRFieldDefn *poField, int bApproxOK = TRUE ) override; virtual OGRErr CreateGeomField( OGRGeomFieldDefn *poField, int bApproxOK = TRUE ) override; virtual const char *GetFIDColumn() override; virtual const char *GetGeometryColumn() override; virtual OGRSpatialReference *GetSpatialRef() override; // OGRGNMWrappedResultLayer virtual OGRErr InsertFeature(OGRFeature* poFeature, const CPLString &soLayerName, int nPathNo, bool bIsEdge); protected: virtual OGRErr ISetFeature( OGRFeature *poFeature ) override; virtual OGRErr ICreateFeature( OGRFeature *poFeature ) override; protected: //! @cond Doxygen_Suppress GDALDataset *poDS; OGRLayer *poLayer; //! @endcond }; #endif // __cplusplus #endif // GNM