diff options
author | Yuri Gorshenin <y@maps.me> | 2016-09-19 13:00:13 +0300 |
---|---|---|
committer | Yuri Gorshenin <y@maps.me> | 2016-09-19 13:28:43 +0300 |
commit | 5fa2d83e9359b8c63d0831ccd0c74caab4a2217f (patch) | |
tree | f04f2feac56909a5954a55d6a52ad8b9afcf0c9d /routing | |
parent | 11a23fe8f4a03728612a5565d6b7c4710f87fa96 (diff) |
[routing] Fixed connectivity checking code.
Diffstat (limited to 'routing')
-rw-r--r-- | routing/road_graph_router.cpp | 29 |
1 files changed, 15 insertions, 14 deletions
diff --git a/routing/road_graph_router.cpp b/routing/road_graph_router.cpp index ef8cc95587..312b466a3c 100644 --- a/routing/road_graph_router.cpp +++ b/routing/road_graph_router.cpp @@ -69,27 +69,28 @@ bool CheckGraphConnectivity(IRoadGraph const & graph, Junction const & junction, q.push(junction); set<Junction> visited; + visited.insert(junction); vector<Edge> edges; - while (!q.empty()) + while (!q.empty() && visited.size() < limit) { - Junction const node = q.front(); + Junction const u = q.front(); q.pop(); - if (visited.find(node) != visited.end()) - continue; - visited.insert(node); - - if (limit == visited.size()) - return true; - edges.clear(); - graph.GetOutgoingEdges(node, edges); - for (Edge const & e : edges) - q.push(e.GetEndJunction()); + graph.GetOutgoingEdges(u, edges); + for (Edge const & edge : edges) + { + Junction const & v = edge.GetEndJunction(); + if (visited.count(v) == 0) + { + q.push(v); + visited.insert(v); + } + } } - return false; + return visited.size() >= limit; } // Find closest candidates in the world graph @@ -109,7 +110,7 @@ void FindClosestEdges(IRoadGraph const & graph, m2::PointD const & point, for (auto const & candidate : candidates) { auto const & edge = candidate.first; - if (CheckGraphConnectivity(graph, edge.GetStartJunction(), kTestConnectivityVisitJunctionsLimit)) + if (CheckGraphConnectivity(graph, edge.GetEndJunction(), kTestConnectivityVisitJunctionsLimit)) { vicinity.emplace_back(candidate); |