GDAL

gnmgraph.h
1/******************************************************************************
2 *
3 * Project: GDAL/OGR Geography Network support (Geographic Network Model)
4 * Purpose: GNM graph implementation.
5 * Authors: Mikhail Gusev (gusevmihs at gmail dot com)
6 * Dmitry Baryshnikov, polimax@mail.ru
7 *
8 ******************************************************************************
9 * Copyright (c) 2014, Mikhail Gusev
10 * Copyright (c) 2014-2015, NextGIS <info@nextgis.com>
11 *
12 * Permission is hereby granted, free of charge, to any person obtaining a
13 * copy of this software and associated documentation files (the "Software"),
14 * to deal in the Software without restriction, including without limitation
15 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
16 * and/or sell copies of the Software, and to permit persons to whom the
17 * Software is furnished to do so, subject to the following conditions:
18 *
19 * The above copyright notice and this permission notice shall be included
20 * in all copies or substantial portions of the Software.
21 *
22 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
23 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
25 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
27 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
28 * DEALINGS IN THE SOFTWARE.
29 ****************************************************************************/
30
31#ifndef GNMGRAPH_H
32#define GNMGRAPH_H
33
34#include "cpl_port.h"
35#if defined(__cplusplus) && !defined(CPL_SUPRESS_CPLUSPLUS)
36#include <map>
37#include <queue>
38#include <set>
39#include <vector>
40#endif
41
42// Alias for some big data type to store identificators.
43#define GNMGFID GIntBig
44// Graph constants
45#define GNM_EDGE_DIR_BOTH 0 // bidirectional
46#define GNM_EDGE_DIR_SRCTOTGT 1 // from source to target
47#define GNM_EDGE_DIR_TGTTOSRC 2 // from target to source
48
49#if defined(__cplusplus) && !defined(CPL_SUPRESS_CPLUSPLUS)
50// Types declarations.
51 typedef std::vector<GNMGFID> GNMVECTOR, *LPGNMVECTOR;
52 typedef const std::vector<GNMGFID> GNMCONSTVECTOR;
53 typedef const std::vector<GNMGFID> *LPGNMCONSTVECTOR;
54 typedef std::pair<GNMGFID, GNMGFID> EDGEVERTEXPAIR;
55 typedef std::vector<EDGEVERTEXPAIR> GNMPATH;
56
58 struct GNMStdEdge
59{
60 GNMGFID nSrcVertexFID = 0;
61 GNMGFID nTgtVertexFID = 0;
62 bool bIsBidir = false;
63 double dfDirCost = 0;
64 double dfInvCost = 0;
65 bool bIsBlocked = false;
66};
67
69 struct GNMStdVertex
70{
71 GNMVECTOR anOutEdgeFIDs{};
72 bool bIsBlocked = false;
73};
74
88 class CPL_DLL GNMGraph /* non final */
89{
90 public:
91 GNMGraph();
92 virtual ~GNMGraph();
93
94 // GNMGraph
95
104 virtual void AddVertex(GNMGFID nFID);
105
110 virtual void DeleteVertex(GNMGFID nFID);
111
121 virtual void AddEdge(GNMGFID nConFID, GNMGFID nSrcFID, GNMGFID nTgtFID,
122 bool bIsBidir, double dfCost, double dfInvCost);
123
128 virtual void DeleteEdge(GNMGFID nConFID);
129
136 virtual void ChangeEdge(GNMGFID nFID, double dfCost, double dfInvCost);
137
143 virtual void ChangeBlockState(GNMGFID nFID, bool bBlock);
144
150 virtual bool CheckVertexBlocked(GNMGFID nFID) const;
151
159 virtual void ChangeAllBlockState(bool bBlock = false);
160
173 virtual GNMPATH DijkstraShortestPath(GNMGFID nStartFID, GNMGFID nEndFID);
174
195 virtual std::vector<GNMPATH> KShortestPaths(GNMGFID nStartFID,
196 GNMGFID nEndFID, size_t nK);
197
211 virtual GNMPATH ConnectedComponents(const GNMVECTOR &anEmittersIDs);
212
214 virtual void Clear();
215
216 protected:
233 virtual void
234 DijkstraShortestPathTree(GNMGFID nFID,
235 const std::map<GNMGFID, GNMStdEdge> &mstEdges,
236 std::map<GNMGFID, GNMGFID> &mnPathTree);
238 virtual GNMPATH
239 DijkstraShortestPath(GNMGFID nStartFID, GNMGFID nEndFID,
240 const std::map<GNMGFID, GNMStdEdge> &mstEdges);
242 virtual LPGNMCONSTVECTOR GetOutEdges(GNMGFID nFID) const;
243 virtual GNMGFID GetOppositVertex(GNMGFID nEdgeFID,
244 GNMGFID nVertexFID) const;
245 virtual void TraceTargets(std::queue<GNMGFID> &vertexQueue,
246 std::set<GNMGFID> &markedVertIds,
247 GNMPATH &connectedIds);
248
249 protected:
250 std::map<GNMGFID, GNMStdVertex> m_mstVertices{};
251 std::map<GNMGFID, GNMStdEdge> m_mstEdges{};
253};
254
255#endif // __cplusplus
256
257#endif /* GNMGRAPH_H */
GNMGraph
The simple graph class, which holds the appropriate for calculations graph in memory (based on STL co...
Definition gnmgraph.h:89
GNMGraph::DeleteEdge
virtual void DeleteEdge(GNMGFID nConFID)
Delete edge from graph.
GNMGraph::ChangeAllBlockState
virtual void ChangeAllBlockState(bool bBlock=false)
Change all vertices and edges block state.
GNMGraph::ChangeEdge
virtual void ChangeEdge(GNMGFID nFID, double dfCost, double dfInvCost)
Change edge properties.
GNMGraph::DijkstraShortestPath
virtual GNMPATH DijkstraShortestPath(GNMGFID nStartFID, GNMGFID nEndFID, const std::map< GNMGFID, GNMStdEdge > &mstEdges)
DijkstraShortestPath.
GNMGraph::AddVertex
virtual void AddVertex(GNMGFID nFID)
Add a vertex to the graph.
GNMGraph::DijkstraShortestPathTree
virtual void DijkstraShortestPathTree(GNMGFID nFID, const std::map< GNMGFID, GNMStdEdge > &mstEdges, std::map< GNMGFID, GNMGFID > &mnPathTree)
Method to create best path tree.
GNMGraph::DeleteVertex
virtual void DeleteVertex(GNMGFID nFID)
Delete vertex from the graph.
GNMGraph::Clear
virtual void Clear()
Clear.
GNMGraph::AddEdge
virtual void AddEdge(GNMGFID nConFID, GNMGFID nSrcFID, GNMGFID nTgtFID, bool bIsBidir, double dfCost, double dfInvCost)
Add an edge to the graph.
GNMGraph::KShortestPaths
virtual std::vector< GNMPATH > KShortestPaths(GNMGFID nStartFID, GNMGFID nEndFID, size_t nK)
An implementation of KShortest paths algorithm.
GNMGraph::ConnectedComponents
virtual GNMPATH ConnectedComponents(const GNMVECTOR &anEmittersIDs)
Search connected components of the network.
GNMGraph::CheckVertexBlocked
virtual bool CheckVertexBlocked(GNMGFID nFID) const
Check if vertex is blocked.
GNMGraph::ChangeBlockState
virtual void ChangeBlockState(GNMGFID nFID, bool bBlock)
Change the block state of edge or vertex.
GNMGraph::DijkstraShortestPath
virtual GNMPATH DijkstraShortestPath(GNMGFID nStartFID, GNMGFID nEndFID)
An implementation of Dijkstra shortest path algorithm.
cpl_port.h
Core portability definitions for CPL.
GNMStdEdge
Edge.
Definition gnmgraph.h:59
GNMStdEdge::nTgtVertexFID
GNMGFID nTgtVertexFID
Target vertex FID.
Definition gnmgraph.h:61
GNMStdEdge::bIsBidir
bool bIsBidir
Whether the edge is bidirectonal.
Definition gnmgraph.h:62
GNMStdEdge::nSrcVertexFID
GNMGFID nSrcVertexFID
Source vertex FID.
Definition gnmgraph.h:60
GNMStdEdge::dfInvCost
double dfInvCost
Inverse cost.
Definition gnmgraph.h:64
GNMStdEdge::bIsBlocked
bool bIsBlocked
Whether the edge is blocked.
Definition gnmgraph.h:65
GNMStdEdge::dfDirCost
double dfDirCost
Direct cost.
Definition gnmgraph.h:63
GNMStdVertex
Vertex.
Definition gnmgraph.h:70
GNMStdVertex::bIsBlocked
bool bIsBlocked
Whether the vertex is blocked.
Definition gnmgraph.h:72
GNMStdVertex::anOutEdgeFIDs
GNMVECTOR anOutEdgeFIDs
TODO.
Definition gnmgraph.h:71