GDAL
gnmgraph.h
1/******************************************************************************
2 * $Id: gnmgraph.h 80f31ac0b0753868ab421bf0ff62e6682ad9617e 2017-12-07 18:13:41Z Even Rouault $
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.
52typedef std::vector<GNMGFID> GNMVECTOR, *LPGNMVECTOR;
53typedef const std::vector<GNMGFID> GNMCONSTVECTOR;
54typedef const std::vector<GNMGFID>* LPGNMCONSTVECTOR;
55typedef std::pair<GNMGFID,GNMGFID> EDGEVERTEXPAIR;
56typedef std::vector< EDGEVERTEXPAIR > GNMPATH;
57
60{
61 GNMGFID nSrcVertexFID;
62 GNMGFID nTgtVertexFID;
63 bool bIsBidir;
64 double dfDirCost;
65 double dfInvCost;
66 bool bIsBloked;
67};
68
71{
72 GNMVECTOR anOutEdgeFIDs;
73 bool bIsBloked;
74};
75
89class CPL_DLL GNMGraph
90{
91public:
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
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();
215protected:
232 virtual void DijkstraShortestPathTree(GNMGFID nFID,
233 const std::map<GNMGFID, GNMStdEdge> &mstEdges,
234 std::map<GNMGFID, GNMGFID> &mnPathTree);
236 virtual GNMPATH DijkstraShortestPath(GNMGFID nStartFID, GNMGFID nEndFID,
237 const std::map<GNMGFID, GNMStdEdge> &mstEdges);
239 virtual LPGNMCONSTVECTOR GetOutEdges(GNMGFID nFID) const;
240 virtual GNMGFID GetOppositVertex(GNMGFID nEdgeFID, GNMGFID nVertexFID) const;
241 virtual void TraceTargets(std::queue<GNMGFID> &vertexQueue,
242 std::set<GNMGFID> &markedVertIds,
243 GNMPATH &connectedIds);
244protected:
245 std::map<GNMGFID, GNMStdVertex> m_mstVertices;
246 std::map<GNMGFID, GNMStdEdge> m_mstEdges;
248};
249
250#endif // __cplusplus
251
252#endif /* GNMGRAPH_H */
The simple graph class, which holds the appropriate for calculations graph in memory (based on STL co...
Definition: gnmgraph.h:90
virtual void DeleteEdge(GNMGFID nConFID)
Delete edge from graph.
virtual void ChangeAllBlockState(bool bBlock=false)
Change all vertices and edges block state.
virtual void ChangeEdge(GNMGFID nFID, double dfCost, double dfInvCost)
Change edge properties.
virtual GNMPATH DijkstraShortestPath(GNMGFID nStartFID, GNMGFID nEndFID, const std::map< GNMGFID, GNMStdEdge > &mstEdges)
DijkstraShortestPath.
virtual void AddVertex(GNMGFID nFID)
Add a vertex to the graph.
virtual void DijkstraShortestPathTree(GNMGFID nFID, const std::map< GNMGFID, GNMStdEdge > &mstEdges, std::map< GNMGFID, GNMGFID > &mnPathTree)
Method to create best path tree.
virtual void DeleteVertex(GNMGFID nFID)
Delete vertex from the graph.
virtual void Clear()
Clear.
virtual void AddEdge(GNMGFID nConFID, GNMGFID nSrcFID, GNMGFID nTgtFID, bool bIsBidir, double dfCost, double dfInvCost)
Add an edge to the graph.
virtual std::vector< GNMPATH > KShortestPaths(GNMGFID nStartFID, GNMGFID nEndFID, size_t nK)
An implementation of KShortest paths algorithm.
virtual GNMPATH ConnectedComponents(const GNMVECTOR &anEmittersIDs)
Search connected components of the network.
virtual bool CheckVertexBlocked(GNMGFID nFID) const
Check if vertex is blocked.
virtual void ChangeBlockState(GNMGFID nFID, bool bBlock)
Change the block state of edge or vertex.
virtual GNMPATH DijkstraShortestPath(GNMGFID nStartFID, GNMGFID nEndFID)
An implementation of Dijkstra shortest path algorithm.
Core portability definitions for CPL.
Edge.
Definition: gnmgraph.h:60
GNMGFID nTgtVertexFID
Target vertex FID.
Definition: gnmgraph.h:62
bool bIsBidir
Whether the edge is bidirectonal.
Definition: gnmgraph.h:63
GNMGFID nSrcVertexFID
Source vertex FID.
Definition: gnmgraph.h:61
bool bIsBloked
Whether the edge is blocked.
Definition: gnmgraph.h:66
double dfInvCost
Inverse cost.
Definition: gnmgraph.h:65
double dfDirCost
Direct cost.
Definition: gnmgraph.h:64
Vertex.
Definition: gnmgraph.h:71
bool bIsBloked
Whether the vertex is blocked.
Definition: gnmgraph.h:73
GNMVECTOR anOutEdgeFIDs
TODO.
Definition: gnmgraph.h:72

Generated for GDAL by doxygen 1.9.4.