| 249 | } |
| 250 | |
| 251 | bool TestIndexGraphTopology::FindPath(Vertex start, Vertex finish, double & pathWeight, vector<Edge> & pathEdges) const |
| 252 | { |
| 253 | CHECK_LESS(start, m_numVertices, ()); |
| 254 | CHECK_LESS(finish, m_numVertices, ()); |
| 255 | |
| 256 | if (start == finish) |
| 257 | { |
| 258 | pathWeight = 0.0; |
| 259 | pathEdges.clear(); |
| 260 | return true; |
| 261 | } |
| 262 | |
| 263 | auto edgeRequests = m_edgeRequests; |
| 264 | // Edges of the index graph are segments, so we need a loop at finish |
| 265 | // for the end of our path and another loop at start for the bidirectional search. |
| 266 | auto const startFeatureId = static_cast<uint32_t>(edgeRequests.size()); |
| 267 | AddDirectedEdge(edgeRequests, start, start, 0.0); |
| 268 | // |startSegment| corresponds to edge from |start| to |start| which has featureId |startFeatureId| |
| 269 | // and the only segment with segmentIdx |0|. It is a loop so direction does not matter. |
| 270 | auto const startSegment = Segment(kTestNumMwmId, startFeatureId, 0 /* segmentIdx */, true /* forward */); |
| 271 | |
| 272 | auto const finishFeatureId = static_cast<uint32_t>(edgeRequests.size()); |
| 273 | AddDirectedEdge(edgeRequests, finish, finish, 0.0); |
| 274 | // |finishSegment| corresponds to edge from |finish| to |finish| which has featureId |finishFeatureId| |
| 275 | // and the only segment with segmentIdx |0|. It is a loop so direction does not matter. |
| 276 | auto const finishSegment = Segment(kTestNumMwmId, finishFeatureId, 0 /* segmentIdx */, true /* forward */); |
| 277 | |
| 278 | Builder builder(m_numVertices); |
| 279 | builder.SetCurrentTimeGetter(m_currentTimeGetter); |
| 280 | builder.BuildGraphFromRequests(edgeRequests); |
| 281 | auto worldGraph = builder.PrepareIndexGraph(); |
| 282 | CHECK(worldGraph != nullptr, ()); |
| 283 | |
| 284 | AlgorithmForWorldGraph algorithm; |
| 285 | |
| 286 | WorldGraphForAStar graphForAStar(std::move(worldGraph)); |
| 287 | |
| 288 | AlgorithmForWorldGraph::ParamsForTests<> params(graphForAStar, startSegment, finishSegment); |
| 289 | RoutingResult<Segment, RouteWeight> routingResult; |
| 290 | auto const resultCode = algorithm.FindPathBidirectional(params, routingResult); |
| 291 | |
| 292 | // Check unidirectional AStar returns same result. |
| 293 | { |
| 294 | RoutingResult<Segment, RouteWeight> unidirectionalRoutingResult; |
| 295 | auto const unidirectionalResultCode = algorithm.FindPath(params, unidirectionalRoutingResult); |
| 296 | CHECK_EQUAL(resultCode, unidirectionalResultCode, ()); |
| 297 | CHECK(routingResult.m_distance.IsAlmostEqualForTests(unidirectionalRoutingResult.m_distance, kEpsilon), |
| 298 | ("Distances differ:", routingResult.m_distance, unidirectionalRoutingResult.m_distance)); |
| 299 | } |
| 300 | |
| 301 | if (resultCode == AlgorithmForWorldGraph::Result::NoPath) |
| 302 | return false; |
| 303 | |
| 304 | CHECK_EQUAL(resultCode, AlgorithmForWorldGraph::Result::OK, ()); |
| 305 | CHECK_GREATER_OR_EQUAL(routingResult.m_path.size(), 2, ()); |
| 306 | CHECK_EQUAL(routingResult.m_path.front(), startSegment, ()); |
| 307 | CHECK_EQUAL(routingResult.m_path.back(), finishSegment, ()); |
| 308 | |