Line data Source code
1 : /******************************************************************************
2 : *
3 : * Project: GDAL/OGR Geography Network support (Geographic Network Model)
4 : * Purpose: GNM graph implementation.
5 : * Authors: Mikhail Gusev (gusevmihs at gmail dot com)
6 : * Dmitry Baryshnikov, polimax@mail.ru
7 : *
8 : ******************************************************************************
9 : * Copyright (c) 2014, Mikhail Gusev
10 : * Copyright (c) 2014-2015, NextGIS <info@nextgis.com>
11 : *
12 : * Permission is hereby granted, free of charge, to any person obtaining a
13 : * copy of this software and associated documentation files (the "Software"),
14 : * to deal in the Software without restriction, including without limitation
15 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
16 : * and/or sell copies of the Software, and to permit persons to whom the
17 : * Software is furnished to do so, subject to the following conditions:
18 : *
19 : * The above copyright notice and this permission notice shall be included
20 : * in all copies or substantial portions of the Software.
21 : *
22 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
23 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
25 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
27 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
28 : * DEALINGS IN THE SOFTWARE.
29 : ****************************************************************************/
30 :
31 : #include "gnmgraph.h"
32 : #include "gnm_priv.h"
33 : #include <algorithm>
34 : #include <limits>
35 : #include <set>
36 :
37 : //! @cond Doxygen_Suppress
38 16 : GNMGraph::GNMGraph()
39 : {
40 16 : }
41 :
42 16 : GNMGraph::~GNMGraph()
43 : {
44 16 : }
45 :
46 462 : void GNMGraph::AddVertex(GNMGFID nFID)
47 : {
48 462 : if (m_mstVertices.find(nFID) != m_mstVertices.end())
49 245 : return;
50 :
51 434 : GNMStdVertex stVertex;
52 217 : stVertex.bIsBlocked = false;
53 217 : m_mstVertices[nFID] = std::move(stVertex);
54 : }
55 :
56 0 : void GNMGraph::DeleteVertex(GNMGFID nFID)
57 : {
58 0 : m_mstVertices.erase(nFID);
59 :
60 : // remove all edges with this vertex
61 0 : std::vector<GNMGFID> aoIdsToErase;
62 0 : for (std::map<GNMGFID, GNMStdEdge>::iterator it = m_mstEdges.begin();
63 0 : it != m_mstEdges.end(); ++it)
64 : {
65 0 : if (it->second.nSrcVertexFID == nFID ||
66 0 : it->second.nTgtVertexFID == nFID)
67 0 : aoIdsToErase.push_back(it->first);
68 : }
69 0 : for (size_t i = 0; i < aoIdsToErase.size(); i++)
70 0 : m_mstEdges.erase(aoIdsToErase[i]);
71 0 : }
72 :
73 231 : void GNMGraph::AddEdge(GNMGFID nConFID, GNMGFID nSrcFID, GNMGFID nTgtFID,
74 : bool bIsBidir, double dfCost, double dfInvCost)
75 : {
76 : // We do not add edge if an edge with the same id already exist
77 : // because each edge must have only one source and one target vertex.
78 231 : std::map<GNMGFID, GNMStdEdge>::iterator it = m_mstEdges.find(nConFID);
79 231 : if (it != m_mstEdges.end())
80 : {
81 0 : CPLError(CE_Failure, CPLE_AppDefined, "The edge already exist.");
82 0 : return;
83 : }
84 :
85 231 : AddVertex(nSrcFID);
86 231 : AddVertex(nTgtFID);
87 :
88 231 : auto itSrs = m_mstVertices.find(nSrcFID);
89 231 : auto itTgt = m_mstVertices.find(nTgtFID);
90 231 : if (itSrs == m_mstVertices.end() || itTgt == m_mstVertices.end())
91 : {
92 0 : CPLAssert(false);
93 : return;
94 : }
95 :
96 : // Insert edge to the array of edges.
97 : GNMStdEdge stEdge;
98 231 : stEdge.nSrcVertexFID = nSrcFID;
99 231 : stEdge.nTgtVertexFID = nTgtFID;
100 231 : stEdge.bIsBidir = bIsBidir;
101 231 : stEdge.dfDirCost = dfCost;
102 231 : stEdge.dfInvCost = dfInvCost;
103 231 : stEdge.bIsBlocked = false;
104 :
105 231 : m_mstEdges[nConFID] = stEdge;
106 :
107 231 : if (bIsBidir)
108 : {
109 231 : itSrs->second.anOutEdgeFIDs.push_back(nConFID);
110 231 : itTgt->second.anOutEdgeFIDs.push_back(nConFID);
111 : }
112 : else
113 : {
114 0 : itSrs->second.anOutEdgeFIDs.push_back(nConFID);
115 : }
116 : }
117 :
118 0 : void GNMGraph::DeleteEdge(GNMGFID nConFID)
119 : {
120 0 : m_mstEdges.erase(nConFID);
121 :
122 : // remove edge from all vertices anOutEdgeFIDs
123 0 : for (auto &it : m_mstVertices)
124 : {
125 : it.second.anOutEdgeFIDs.erase(
126 0 : std::remove(it.second.anOutEdgeFIDs.begin(),
127 0 : it.second.anOutEdgeFIDs.end(), nConFID),
128 0 : it.second.anOutEdgeFIDs.end());
129 : }
130 0 : }
131 :
132 0 : void GNMGraph::ChangeEdge(GNMGFID nFID, double dfCost, double dfInvCost)
133 : {
134 0 : std::map<GNMGFID, GNMStdEdge>::iterator it = m_mstEdges.find(nFID);
135 0 : if (it != m_mstEdges.end())
136 : {
137 0 : it->second.dfDirCost = dfCost;
138 0 : it->second.dfInvCost = dfInvCost;
139 : }
140 0 : }
141 :
142 0 : void GNMGraph::ChangeBlockState(GNMGFID nFID, bool bBlock)
143 : {
144 : // check vertices
145 0 : std::map<GNMGFID, GNMStdVertex>::iterator itv = m_mstVertices.find(nFID);
146 0 : if (itv != m_mstVertices.end())
147 : {
148 0 : itv->second.bIsBlocked = bBlock;
149 0 : return;
150 : }
151 :
152 : // check edges
153 0 : std::map<GNMGFID, GNMStdEdge>::iterator ite = m_mstEdges.find(nFID);
154 0 : if (ite != m_mstEdges.end())
155 : {
156 0 : ite->second.bIsBlocked = bBlock;
157 : }
158 : }
159 :
160 337 : bool GNMGraph::CheckVertexBlocked(GNMGFID nFID) const
161 : {
162 : std::map<GNMGFID, GNMStdVertex>::const_iterator it =
163 337 : m_mstVertices.find(nFID);
164 337 : if (it != m_mstVertices.end())
165 337 : return it->second.bIsBlocked;
166 0 : return false;
167 : }
168 :
169 0 : void GNMGraph::ChangeAllBlockState(bool bBlock)
170 : {
171 0 : for (std::map<GNMGFID, GNMStdVertex>::iterator itv = m_mstVertices.begin();
172 0 : itv != m_mstVertices.end(); ++itv)
173 : {
174 0 : itv->second.bIsBlocked = bBlock;
175 : }
176 :
177 0 : for (std::map<GNMGFID, GNMStdEdge>::iterator ite = m_mstEdges.begin();
178 0 : ite != m_mstEdges.end(); ++ite)
179 : {
180 0 : ite->second.bIsBlocked = bBlock;
181 : }
182 0 : }
183 :
184 : GNMPATH
185 42 : GNMGraph::DijkstraShortestPath(GNMGFID nStartFID, GNMGFID nEndFID,
186 : const std::map<GNMGFID, GNMStdEdge> &mstEdges)
187 : {
188 84 : std::map<GNMGFID, GNMGFID> mnShortestTree;
189 42 : DijkstraShortestPathTree(nStartFID, mstEdges, mnShortestTree);
190 :
191 : // We search for a path in the resulting tree, starting from end point to
192 : // start point.
193 :
194 84 : GNMPATH aoShortestPath;
195 42 : GNMGFID nNextVertexId = nEndFID;
196 42 : std::map<GNMGFID, GNMGFID>::iterator it;
197 42 : EDGEVERTEXPAIR buf;
198 :
199 : while (true)
200 : {
201 116 : it = mnShortestTree.find(nNextVertexId);
202 :
203 116 : if (it == mnShortestTree.end())
204 : {
205 : // We haven't found the start vertex - there is no path between
206 : // to given vertices in a shortest-path tree.
207 32 : break;
208 : }
209 84 : else if (it->first == nStartFID)
210 : {
211 : // We've reached the start vertex and return an array.
212 10 : aoShortestPath.push_back(std::make_pair(nNextVertexId, -1));
213 :
214 : // Revert array because the first vertex is now the last in path.
215 10 : int size = static_cast<int>(aoShortestPath.size());
216 52 : for (int i = 0; i < size / 2; ++i)
217 : {
218 42 : buf = aoShortestPath[i];
219 42 : aoShortestPath[i] = aoShortestPath[size - i - 1];
220 42 : aoShortestPath[size - i - 1] = buf;
221 : }
222 10 : return aoShortestPath;
223 : }
224 : else
225 : {
226 : // There is only one edge which leads to this vertex, because we
227 : // analyse a tree. We add this edge with its target vertex into
228 : // final array.
229 74 : aoShortestPath.push_back(std::make_pair(nNextVertexId, it->second));
230 :
231 : // An edge has only two vertices, so we get the opposite one to the
232 : // current vertex in order to continue search backwards.
233 74 : nNextVertexId = GetOppositVertex(it->second, it->first);
234 : }
235 74 : }
236 :
237 : // return empty array
238 64 : GNMPATH oRet;
239 32 : return oRet;
240 : }
241 :
242 4 : GNMPATH GNMGraph::DijkstraShortestPath(GNMGFID nStartFID, GNMGFID nEndFID)
243 : {
244 4 : return DijkstraShortestPath(nStartFID, nEndFID, m_mstEdges);
245 : }
246 :
247 2 : std::vector<GNMPATH> GNMGraph::KShortestPaths(GNMGFID nStartFID,
248 : GNMGFID nEndFID, size_t nK)
249 : {
250 : // Resulting array with paths.
251 : // A will be sorted by the path costs' descending.
252 2 : std::vector<GNMPATH> A;
253 :
254 2 : if (nK == 0)
255 0 : return A; // return empty array if K is incorrect.
256 :
257 : // Temporary array for storing paths-candidates.
258 : // B will be automatically sorted by the cost descending order. We
259 : // need multimap because there can be physically different paths but
260 : // with the same costs.
261 4 : std::multimap<double, GNMPATH> B;
262 :
263 : // Firstly get the very shortest path.
264 : // Note, that it is important to obtain the path from DijkstraShortestPath()
265 : // as vector, rather than the map, because we need the correct order of the
266 : // path segments in the Yen's algorithm iterations.
267 4 : GNMPATH aoFirstPath = DijkstraShortestPath(nStartFID, nEndFID);
268 2 : if (aoFirstPath.empty())
269 0 : return A; // return empty array if there is no path between points.
270 :
271 2 : A.push_back(aoFirstPath);
272 :
273 : size_t i, k, l;
274 2 : GNMPATH::iterator itAk, tempIt, itR;
275 2 : std::vector<GNMPATH>::iterator itA;
276 2 : std::map<GNMGFID, double>::iterator itDel;
277 4 : GNMPATH aoRootPath, aoRootPathOther, aoSpurPath;
278 : GNMGFID nSpurNode, nVertexToDel, nEdgeToDel;
279 : double dfSumCost;
280 :
281 4 : std::map<GNMGFID, GNMStdEdge> mstEdges = m_mstEdges;
282 :
283 6 : for (k = 0; k < nK - 1; ++k) // -1 because we have already found one
284 : {
285 : std::map<GNMGFID, double>
286 4 : mDeletedEdges; // for infinity costs assignment
287 4 : itAk = A[k].begin();
288 :
289 42 : for (i = 0; i < A[k].size() - 1; ++i) // avoid end node
290 : {
291 : // Get the current node.
292 38 : nSpurNode = A[k][i].first;
293 :
294 : // Get the root path from the 0 to the current node.
295 :
296 : // Equivalent to A[k][i]
297 : // because we will use std::vector::assign, which assigns [..)
298 : // range, not [..]
299 38 : ++itAk;
300 :
301 38 : aoRootPath.assign(A[k].begin(), itAk);
302 :
303 : // Remove old incidence edges of all other best paths.
304 : // i.e. if the spur vertex can be reached in already found best
305 : // paths we must remove the following edge after the end of root
306 : // path from the graph in order not to take in account these already
307 : // seen best paths.
308 : // i.e. it ensures that the spur path will be different.
309 96 : for (itA = A.begin(); itA != A.end(); ++itA)
310 : {
311 : // check if the number of node exceed the number of last node in
312 : // the path array (i.e. if one of the A paths has less amount of
313 : // segments than the current candidate path)
314 58 : if (i >= itA->size())
315 0 : continue;
316 :
317 : // + 1, because we will use std::vector::assign, which assigns
318 : // [..) range, not [..]
319 58 : aoRootPathOther.assign(itA->begin(), itA->begin() + i + 1);
320 :
321 : // Get the edge which follows the spur node for current path
322 : // and delete it.
323 : //
324 : // NOTE: we do not delete edges due to performance reasons,
325 : // because the deletion of edge and all its GFIDs in vertex
326 : // records is slower than the infinity cost assignment.
327 :
328 : // also check if node number exceed the number of the last node
329 : // in root array.
330 100 : if ((aoRootPath == aoRootPathOther) &&
331 42 : (i < aoRootPathOther.size()))
332 : {
333 42 : tempIt = itA->begin() + i + 1;
334 0 : mDeletedEdges.insert(std::make_pair(
335 42 : tempIt->second, mstEdges[tempIt->second].dfDirCost));
336 42 : mstEdges[tempIt->second].dfDirCost =
337 42 : std::numeric_limits<double>::infinity();
338 : }
339 : }
340 :
341 : // Remove root path nodes from the graph. If we do not delete them
342 : // the path will be found backwards and some parts of the path will
343 : // duplicate the parts of old paths.
344 : // Note: we "delete" all the incidence to the root nodes edges, so
345 : // to restore them in a common way.
346 :
347 : // end()-1, because we should not remove the spur node
348 200 : for (itR = aoRootPath.begin(); itR != aoRootPath.end() - 1; ++itR)
349 : {
350 162 : nVertexToDel = itR->first;
351 162 : for (l = 0;
352 544 : l < m_mstVertices[nVertexToDel].anOutEdgeFIDs.size(); ++l)
353 : {
354 382 : nEdgeToDel = m_mstVertices[nVertexToDel].anOutEdgeFIDs[l];
355 0 : mDeletedEdges.insert(std::make_pair(
356 382 : nEdgeToDel, mstEdges[nEdgeToDel].dfDirCost));
357 382 : mstEdges[nEdgeToDel].dfDirCost =
358 382 : std::numeric_limits<double>::infinity();
359 : }
360 : }
361 :
362 : // Find the new best path in the modified graph.
363 38 : aoSpurPath = DijkstraShortestPath(nSpurNode, nEndFID, mstEdges);
364 :
365 : // Firstly, restore deleted edges in order to calculate the summary
366 : // cost of the path correctly later, because the costs will be
367 : // gathered from the initial graph.
368 : // We must do it here, after each edge removing, because the later
369 : // Dijkstra searches must consider these edges.
370 332 : for (itDel = mDeletedEdges.begin(); itDel != mDeletedEdges.end();
371 294 : ++itDel)
372 : {
373 294 : mstEdges[itDel->first].dfDirCost = itDel->second;
374 : }
375 :
376 38 : mDeletedEdges.clear();
377 :
378 : // If the part of a new best path has been found we form a full one
379 : // and add it to the candidates array.
380 38 : if (!aoSpurPath.empty())
381 : {
382 : // + 1 so not to consider the first node in the found path,
383 : // which is already the last node in the root path
384 12 : aoRootPath.insert(aoRootPath.end(), aoSpurPath.begin() + 1,
385 18 : aoSpurPath.end());
386 : // Calculate the summary cost of the path.
387 : // TODO: get the summary cost from the Dejkstra method?
388 6 : dfSumCost = 0.0;
389 74 : for (itR = aoRootPath.begin(); itR != aoRootPath.end(); ++itR)
390 : {
391 : // TODO: check: Note, that here the current cost can not be
392 : // infinity, because every time we assign infinity costs for
393 : // edges of old paths, we anyway have the alternative edges
394 : // with non-infinity costs.
395 68 : dfSumCost += mstEdges[itR->second].dfDirCost;
396 : }
397 :
398 6 : B.insert(std::make_pair(dfSumCost, aoRootPath));
399 : }
400 : }
401 :
402 4 : if (B.empty())
403 0 : break;
404 :
405 : // The best path is the first, because the map is sorted accordingly.
406 : // Note, that here we won't clear the path candidates array and select
407 : // the best path from all of the rest paths, even from those which were
408 : // found on previous iterations. That's why we need k iterations at all.
409 : // Note, that if there were two paths with the same costs and it is the
410 : // LAST iteration the first occurred path will be added, rather than
411 : // random.
412 4 : A.push_back(B.begin()->second);
413 :
414 : // Sometimes B contains fully duplicate paths. Such duplicates have been
415 : // formed during the search of alternative for almost the same paths
416 : // which were already in A.
417 : // We allowed to add them into B so here we must delete all duplicates.
418 8 : while (!B.empty() && B.begin()->second == A.back())
419 : {
420 4 : B.erase(B.begin());
421 : }
422 : }
423 :
424 2 : return A;
425 : }
426 :
427 1 : GNMPATH GNMGraph::ConnectedComponents(const GNMVECTOR &anEmittersIDs)
428 : {
429 1 : GNMPATH anConnectedIDs;
430 :
431 1 : if (anEmittersIDs.empty())
432 : {
433 0 : CPLError(CE_Failure, CPLE_IllegalArg, "Emitters list is empty.");
434 0 : return anConnectedIDs;
435 : }
436 2 : std::set<GNMGFID> anMarkedVertIDs;
437 :
438 2 : std::queue<GNMGFID> anStartQueue;
439 1 : GNMVECTOR::const_iterator it;
440 3 : for (it = anEmittersIDs.begin(); it != anEmittersIDs.end(); ++it)
441 : {
442 2 : anStartQueue.push(*it);
443 : }
444 :
445 : // Begin the iterations of the Breadth-first search.
446 1 : TraceTargets(anStartQueue, anMarkedVertIDs, anConnectedIDs);
447 :
448 1 : return anConnectedIDs;
449 : }
450 :
451 0 : void GNMGraph::Clear()
452 : {
453 0 : m_mstVertices.clear();
454 0 : m_mstEdges.clear();
455 0 : }
456 :
457 42 : void GNMGraph::DijkstraShortestPathTree(
458 : GNMGFID nFID, const std::map<GNMGFID, GNMStdEdge> &mstEdges,
459 : std::map<GNMGFID, GNMGFID> &mnPathTree)
460 : {
461 : // Initialize all vertices in graph with infinity mark.
462 42 : double dfInfinity = std::numeric_limits<double>::infinity();
463 :
464 84 : std::map<GNMGFID, double> mMarks;
465 42 : std::map<GNMGFID, GNMStdVertex>::iterator itv;
466 1344 : for (itv = m_mstVertices.begin(); itv != m_mstVertices.end(); ++itv)
467 : {
468 1302 : mMarks[itv->first] = dfInfinity;
469 : }
470 :
471 42 : mMarks[nFID] = 0.0;
472 42 : mnPathTree[nFID] = -1;
473 :
474 : // Initialize all vertices as unseen (there are no seen vertices).
475 84 : std::set<GNMGFID> snSeen;
476 :
477 : // We use multimap to maintain the ascending order of costs and because
478 : // there can be different vertices with the equal cost.
479 84 : std::multimap<double, GNMGFID> to_see;
480 42 : std::multimap<double, GNMGFID>::iterator it;
481 42 : to_see.insert(std::pair<double, GNMGFID>(0.0, nFID));
482 : LPGNMCONSTVECTOR panOutcomeEdgeId;
483 :
484 : size_t i;
485 : GNMGFID nCurrentVertId, nCurrentEdgeId, nTargetVertId;
486 : double dfCurrentEdgeCost, dfCurrentVertMark, dfNewVertexMark;
487 42 : std::map<GNMGFID, GNMStdEdge>::const_iterator ite;
488 :
489 : // Continue iterations while there are some vertices to see.
490 388 : while (!to_see.empty())
491 : {
492 : // We must see vertices with minimal costs at first.
493 : // In multimap the first cost is the minimal.
494 346 : it = to_see.begin();
495 :
496 346 : nCurrentVertId = it->second;
497 346 : dfCurrentVertMark = it->first;
498 346 : snSeen.insert(it->second);
499 346 : to_see.erase(it);
500 :
501 : // For all neighbours for the current vertex.
502 346 : panOutcomeEdgeId = GetOutEdges(nCurrentVertId);
503 346 : if (nullptr == panOutcomeEdgeId)
504 0 : continue;
505 :
506 1078 : for (i = 0; i < panOutcomeEdgeId->size(); ++i)
507 : {
508 732 : nCurrentEdgeId = panOutcomeEdgeId->operator[](i);
509 :
510 732 : ite = mstEdges.find(nCurrentEdgeId);
511 732 : if (ite == mstEdges.end() || ite->second.bIsBlocked)
512 0 : continue;
513 :
514 : // We go in any edge from source to target so we take only
515 : // direct cost (even if an edge is bi-directed).
516 732 : dfCurrentEdgeCost = ite->second.dfDirCost;
517 :
518 : // While we see outcome edges of current vertex id we definitely
519 : // know that target vertex id will be target for current edge id.
520 732 : nTargetVertId = GetOppositVertex(nCurrentEdgeId, nCurrentVertId);
521 :
522 : // Calculate a new mark assuming the full path cost (mark of the
523 : // current vertex) to this vertex.
524 732 : dfNewVertexMark = dfCurrentVertMark + dfCurrentEdgeCost;
525 :
526 : // Update mark of the vertex if needed.
527 732 : if (snSeen.find(nTargetVertId) == snSeen.end() &&
528 1036 : dfNewVertexMark < mMarks[nTargetVertId] &&
529 304 : !CheckVertexBlocked(nTargetVertId))
530 : {
531 304 : mMarks[nTargetVertId] = dfNewVertexMark;
532 304 : mnPathTree[nTargetVertId] = nCurrentEdgeId;
533 :
534 : // The vertex with minimal cost will be inserted to the
535 : // beginning.
536 : to_see.insert(
537 304 : std::pair<double, GNMGFID>(dfNewVertexMark, nTargetVertId));
538 : }
539 : }
540 : }
541 42 : }
542 :
543 377 : LPGNMCONSTVECTOR GNMGraph::GetOutEdges(GNMGFID nFID) const
544 : {
545 : std::map<GNMGFID, GNMStdVertex>::const_iterator it =
546 377 : m_mstVertices.find(nFID);
547 377 : if (it != m_mstVertices.end())
548 377 : return &it->second.anOutEdgeFIDs;
549 0 : return nullptr;
550 : }
551 :
552 872 : GNMGFID GNMGraph::GetOppositVertex(GNMGFID nEdgeFID, GNMGFID nVertexFID) const
553 : {
554 : std::map<GNMGFID, GNMStdEdge>::const_iterator it =
555 872 : m_mstEdges.find(nEdgeFID);
556 872 : if (it != m_mstEdges.end())
557 : {
558 872 : if (nVertexFID == it->second.nSrcVertexFID)
559 : {
560 399 : return it->second.nTgtVertexFID;
561 : }
562 473 : else if (nVertexFID == it->second.nTgtVertexFID)
563 : {
564 473 : return it->second.nSrcVertexFID;
565 : }
566 : }
567 0 : return -1;
568 : }
569 :
570 8 : void GNMGraph::TraceTargets(std::queue<GNMGFID> &vertexQueue,
571 : std::set<GNMGFID> &markedVertIds,
572 : GNMPATH &connectedIds)
573 : {
574 16 : std::queue<GNMGFID> neighbours_queue;
575 :
576 : // See all given vertices except thouse that have been already seen.
577 43 : while (!vertexQueue.empty())
578 : {
579 35 : GNMGFID nCurVertID = vertexQueue.front();
580 :
581 : // There may be duplicate unmarked vertices in a current queue. Check
582 : // it.
583 35 : if (markedVertIds.find(nCurVertID) == markedVertIds.end())
584 : {
585 31 : markedVertIds.insert(nCurVertID);
586 :
587 : // See all outcome edges, add them to connected and than see the
588 : // target vertex of each edge. Add it to the queue, which will be
589 : // recursively seen the same way on the next iteration.
590 31 : LPGNMCONSTVECTOR panOutcomeEdgeIDs = GetOutEdges(nCurVertID);
591 31 : if (nullptr != panOutcomeEdgeIDs)
592 : {
593 97 : for (const GNMGFID nCurEdgeID : *panOutcomeEdgeIDs)
594 : {
595 : // ISSUE: think about to return a sequence of vertices and
596 : // edges (which is more universal), as now we are going to
597 : // return only sequence of edges.
598 66 : connectedIds.push_back(
599 66 : std::make_pair(nCurVertID, nCurEdgeID));
600 :
601 : // Get the only target vertex of this edge. If edge is
602 : // bidirected get not that vertex that with nCurVertID.
603 : GNMGFID nTargetVertID;
604 : /*
605 : std::vector<GNMGFID> target_vert_ids =
606 : _getTgtVert(cur_edge_id); std::vector<GNMGFID>::iterator
607 : itt; for (itt = target_vert_ids.begin(); itt !=
608 : target_vert_ids.end(); ++itt)
609 : {
610 : if ((*itt) != cur_vert_id)
611 : {
612 : target_vert_id = *itt;
613 : break;
614 : }
615 : }
616 : */
617 66 : nTargetVertID = GetOppositVertex(nCurEdgeID, nCurVertID);
618 :
619 : // Avoid marked or blocked vertices.
620 66 : if ((markedVertIds.find(nTargetVertID) ==
621 165 : markedVertIds.end()) &&
622 33 : (!CheckVertexBlocked(nTargetVertID)))
623 33 : neighbours_queue.push(nTargetVertID);
624 : }
625 : }
626 : }
627 :
628 35 : vertexQueue.pop();
629 : }
630 :
631 8 : if (!neighbours_queue.empty())
632 7 : TraceTargets(neighbours_queue, markedVertIds, connectedIds);
633 8 : }
634 :
635 : //! @endcond
|
