GDAL

- Main Page
- Related Pages
- Classes
- Files

- File List
- File Members

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
55 struct GNMStdVertex
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 };
GNMGraph
The simple graph class, which holds the appropriate for calculations graph in memory (based on STL co...
Definition: gnmgraph.h:74
GNMStdEdge
Definition: gnmgraph.h:45
GNMStdVertex
Definition: gnmgraph.h:55

Generated for GDAL by 1.8.8.