| 363 | template <typename Vertex, typename Edge, typename Weight> |
| 364 | template <typename VisitVertex, typename AdjustEdgeWeight, typename FilterStates, typename ReducedToFullLength> |
| 365 | void AStarAlgorithm<Vertex, Edge, Weight>::PropagateWave(Graph & graph, Vertex const & startVertex, |
| 366 | VisitVertex && visitVertex, |
| 367 | AdjustEdgeWeight && adjustEdgeWeight, |
| 368 | FilterStates && filterStates, |
| 369 | ReducedToFullLength && reducedToFullLength, |
| 370 | AStarAlgorithm<Vertex, Edge, Weight>::Context & context) const |
| 371 | { |
| 372 | auto const epsilon = graph.GetAStarWeightEpsilon(); |
| 373 | |
| 374 | context.Clear(); |
| 375 | |
| 376 | std::priority_queue<State, std::vector<State>, std::greater<State>> queue; |
| 377 | |
| 378 | context.SetDistance(startVertex, kZeroDistance); |
| 379 | queue.push(State(startVertex, kZeroDistance)); |
| 380 | |
| 381 | typename Graph::EdgeListT adj; |
| 382 | |
| 383 | while (!queue.empty()) |
| 384 | { |
| 385 | State const stateV = queue.top(); |
| 386 | queue.pop(); |
| 387 | |
| 388 | if (stateV.distance > context.GetDistance(stateV.vertex)) |
| 389 | continue; |
| 390 | |
| 391 | if (!visitVertex(stateV.vertex)) |
| 392 | return; |
| 393 | |
| 394 | astar::VertexData const vertexData(stateV.vertex, reducedToFullLength(stateV)); |
| 395 | graph.GetOutgoingEdgesList(vertexData, adj); |
| 396 | for (auto const & edge : adj) |
| 397 | { |
| 398 | State stateW(edge.GetTarget(), kZeroDistance); |
| 399 | if (stateV.vertex == stateW.vertex) |
| 400 | continue; |
| 401 | |
| 402 | auto const edgeWeight = adjustEdgeWeight(stateV.vertex, edge); |
| 403 | auto const newReducedDist = stateV.distance + edgeWeight; |
| 404 | |
| 405 | if (newReducedDist >= context.GetDistance(stateW.vertex) - epsilon) |
| 406 | continue; |
| 407 | |
| 408 | stateW.distance = newReducedDist; |
| 409 | |
| 410 | if (!filterStates(stateW)) |
| 411 | continue; |
| 412 | |
| 413 | context.SetDistance(stateW.vertex, newReducedDist); |
| 414 | context.SetParent(stateW.vertex, stateV.vertex); |
| 415 | queue.push(stateW); |
| 416 | } |
| 417 | } |
| 418 | } |
| 419 | |
| 420 | template <typename Vertex, typename Edge, typename Weight> |
| 421 | template <typename VisitVertex> |
no test coverage detected