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