GDAL

- Main Page
- Related Pages
- Classes
- Files
- Download
- Issue Tracker

- File List
- File Members

gnmgraph.h
1 /******************************************************************************
2 * $Id: gnmgraph.h 36302 2016-11-19 16:54:08Z bishop $
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 "cpl_port.h"
33 #include <map>
34 #include <queue>
35 #include <set>
36 #include <vector>
37
38 // Alias for some big data type to store identificators.
39 #define GNMGFID GIntBig
40 // Graph constants
41 #define GNM_EDGE_DIR_BOTH 0 // bidirectional
42 #define GNM_EDGE_DIR_SRCTOTGT 1 // from source to target
43 #define GNM_EDGE_DIR_TGTTOSRC 2 // from target to source
44
45 // Types declarations.
46 typedef std::vector<GNMGFID> GNMVECTOR, *LPGNMVECTOR;
47 typedef const std::vector<GNMGFID> GNMCONSTVECTOR;
48 typedef const std::vector<GNMGFID>* LPGNMCONSTVECTOR;
49 typedef std::pair<GNMGFID,GNMGFID> EDGEVERTEXPAIR;
50 typedef std::vector< EDGEVERTEXPAIR > GNMPATH;
51
53 struct GNMStdEdge
54 {
55 GNMGFID nSrcVertexFID;
56 GNMGFID nTgtVertexFID;
57 bool bIsBidir;
58 double dfDirCost;
59 double dfInvCost;
60 bool bIsBloked;
61 };
62
64 struct GNMStdVertex
65 {
66 GNMVECTOR anOutEdgeFIDs;
67 bool bIsBloked;
68 };
69
83 class CPL_DLL GNMGraph
84 {
85 public:
86 GNMGraph();
87 virtual ~GNMGraph();
88
89 // GNMGraph
90
99 virtual void AddVertex(GNMGFID nFID);
100
105 virtual void DeleteVertex(GNMGFID nFID);
106
116 virtual void AddEdge(GNMGFID nConFID, GNMGFID nSrcFID, GNMGFID nTgtFID,
117 bool bIsBidir, double dfCost, double dfInvCost);
118
123 virtual void DeleteEdge(GNMGFID nConFID);
124
131 virtual void ChangeEdge(GNMGFID nFID, double dfCost, double dfInvCost);
132
138 virtual void ChangeBlockState (GNMGFID nFID, bool bBlock);
139
145 virtual bool CheckVertexBlocked(GNMGFID nFID) const;
146
154 virtual void ChangeAllBlockState (bool bBlock = false);
155
168 virtual GNMPATH DijkstraShortestPath(GNMGFID nStartFID, GNMGFID nEndFID);
169
189 virtual std::vector<GNMPATH> KShortestPaths(GNMGFID nStartFID,
190 GNMGFID nEndFID, size_t nK);
191
205 virtual GNMPATH ConnectedComponents(const GNMVECTOR &anEmittersIDs);
206
208 virtual void Clear();
209 protected:
226 virtual void DijkstraShortestPathTree(GNMGFID nFID,
227 const std::map<GNMGFID, GNMStdEdge> &mstEdges,
228 std::map<GNMGFID, GNMGFID> &mnPathTree);
230 virtual GNMPATH DijkstraShortestPath(GNMGFID nStartFID, GNMGFID nEndFID,
231 const std::map<GNMGFID, GNMStdEdge> &mstEdges);
233 virtual LPGNMCONSTVECTOR GetOutEdges(GNMGFID nFID) const;
234 virtual GNMGFID GetOppositVertex(GNMGFID nEdgeFID, GNMGFID nVertexFID) const;
235 virtual void TraceTargets(std::queue<GNMGFID> &vertexQueue,
236 std::set<GNMGFID> &markedVertIds,
237 GNMPATH &connectedIds);
238 protected:
239 std::map<GNMGFID, GNMStdVertex> m_mstVertices;
240 std::map<GNMGFID, GNMStdEdge> m_mstEdges;
242 };
GNMStdEdge::nTgtVertexFID
GNMGFID nTgtVertexFID
Target vertex FID.
Definition: gnmgraph.h:56
cpl_port.h
Core portability definitions for CPL.
GNMStdEdge::nSrcVertexFID
GNMGFID nSrcVertexFID
Source vertex FID.
Definition: gnmgraph.h:55
GNMStdEdge::bIsBidir
bool bIsBidir
Whether the edge is bidirectonal.
Definition: gnmgraph.h:57
GNMGraph
The simple graph class, which holds the appropriate for calculations graph in memory (based on STL co...
Definition: gnmgraph.h:83
GNMStdEdge::bIsBloked
bool bIsBloked
Whether the edge is blocked.
Definition: gnmgraph.h:60
GNMStdVertex::bIsBloked
bool bIsBloked
Whether the vertex is blocked.
Definition: gnmgraph.h:67
GNMStdEdge::dfInvCost
double dfInvCost
Inverse cost.
Definition: gnmgraph.h:59
GNMStdEdge
Edge.
Definition: gnmgraph.h:53
GNMStdVertex::anOutEdgeFIDs
GNMVECTOR anOutEdgeFIDs
TODO.
Definition: gnmgraph.h:66
GNMStdEdge::dfDirCost
double dfDirCost
Direct cost.
Definition: gnmgraph.h:58
GNMStdVertex
Vertex.
Definition: gnmgraph.h:64

Generated for GDAL by 1.8.8.