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 #include "gnm_priv.h"
33 #include <vector>
34 #include <queue>
35 #include <set>
36 
37 // Types declarations.
38 
39 typedef std::vector<GNMGFID> GNMVECTOR, *LPGNMVECTOR;
40 typedef const std::vector<GNMGFID> GNMCONSTVECTOR;
41 typedef const std::vector<GNMGFID>* LPGNMCONSTVECTOR;
42 typedef std::pair<GNMGFID,GNMGFID> EDGEVERTEXPAIR;
43 typedef std::vector< EDGEVERTEXPAIR > GNMPATH;
44 
45 struct GNMStdEdge
46 {
47  GNMGFID nSrcVertexFID;
48  GNMGFID nTgtVertexFID;
49  bool bIsBidir;
50  double dfDirCost;
51  double dfInvCost;
52  bool bIsBloked;
53 };
54 
56 {
57  GNMVECTOR anOutEdgeFIDs;
58  bool bIsBloked;
59 };
60 
74 class CPL_DLL GNMGraph
75 {
76 public:
77  GNMGraph();
78  virtual ~GNMGraph();
79 
80  // GNMGraph
81 
90  virtual void AddVertex(GNMGFID nFID);
91 
96  virtual void DeleteVertex(GNMGFID nFID);
97 
107  virtual void AddEdge(GNMGFID nConFID, GNMGFID nSrcFID, GNMGFID nTgtFID,
108  bool bIsBidir, double dfCost, double dfInvCost);
109 
114  virtual void DeleteEdge(GNMGFID nConFID);
115 
122  virtual void ChangeEdge(GNMGFID nFID, double dfCost, double dfInvCost);
123 
129  virtual void ChangeBlockState (GNMGFID nFID, bool bBlock);
130 
136  virtual bool CheckVertexBlocked(GNMGFID nFID) const;
137 
145  virtual void ChangeAllBlockState (bool bBlock = false);
146 
159  virtual GNMPATH DijkstraShortestPath(GNMGFID nStartFID, GNMGFID nEndFID);
160 
180  virtual std::vector<GNMPATH> KShortestPaths(GNMGFID nStartFID,
181  GNMGFID nEndFID, size_t nK);
182 
196  virtual GNMPATH ConnectedComponents(const GNMVECTOR &anEmittersIDs);
197 
198  virtual void Clear();
199 protected:
215  virtual void DijkstraShortestPathTree(GNMGFID nFID,
216  const std::map<GNMGFID, GNMStdEdge> &mstEdges,
217  std::map<GNMGFID, GNMGFID> &mnPathTree);
218  virtual GNMPATH DijkstraShortestPath(GNMGFID nStartFID, GNMGFID nEndFID,
219  const std::map<GNMGFID, GNMStdEdge> &mstEdges);
220 
221  virtual LPGNMCONSTVECTOR GetOutEdges(GNMGFID nFID) const;
222  virtual GNMGFID GetOppositVertex(GNMGFID nEdgeFID, GNMGFID nVertexFID) const;
223  virtual void TraceTargets(std::queue<GNMGFID> &vertexQueue,
224  std::set<GNMGFID> &markedVertIds,
225  GNMPATH &connectedIds);
226 protected:
227  std::map<GNMGFID, GNMStdVertex> m_mstVertices;
228  std::map<GNMGFID, GNMStdEdge> m_mstEdges;
229 };
The simple graph class, which holds the appropriate for calculations graph in memory (based on STL co...
Definition: gnmgraph.h:74
Definition: gnmgraph.h:45
Definition: gnmgraph.h:55

Generated for GDAL by doxygen 1.8.9.1.