FM / routing_algorithms

/srv/osrm/osrm-backend/src/engine/routing_algorithms/

/srv/osrm/osrm-backend/src/engine/routing_algorithms

Name	Size	Mode	Actions
alternative_path_ch.cpp	37069	0644	edit dl rm
alternative_path_mld.cpp	40746	0644	edit dl rm
direct_shortest_path.cpp	4228	0644	edit dl rm
many_to_many_ch.cpp	10706	0644	edit dl rm
many_to_many_mld.cpp	31588	0644	edit dl rm
map_matching.cpp	18498	0644	edit dl rm
routing_base.cpp	4208	0644	edit dl rm
routing_base_ch.cpp	8462	0644	edit dl rm
shortest_path.cpp	920	0644	edit dl rm
tile_turns.cpp	11939	0644	edit dl rm

Edit: /srv/osrm/osrm-backend/src/engine/routing_algorithms/direct_shortest_path.cpp (4228B)

namespace osrm::engine::routing_algorithms
{

/// This is a stripped down version of the general shortest path algorithm.
/// The general algorithm always computes two queries for each leg. This is only
/// necessary in case of vias, where the directions of the start node is constrained
/// by the previous route.
/// This variation is only an optimization for graphs with slow queries, for example
/// not fully contracted graphs.
template <>
InternalRouteResult directShortestPathSearch(SearchEngineData<ch::Algorithm> &engine_working_data,
                                             const DataFacade<ch::Algorithm> &facade,
                                             const PhantomEndpointCandidates &endpoint_candidates)
{
    engine_working_data.InitializeOrClearFirstThreadLocalStorage(facade.GetNumberOfNodes());
    auto &forward_heap = *engine_working_data.forward_heap_1;
    auto &reverse_heap = *engine_working_data.reverse_heap_1;
    forward_heap.Clear();
    reverse_heap.Clear();

EdgeWeight weight = INVALID_EDGE_WEIGHT;
    std::vector<NodeID> packed_leg;
    insertNodesInHeaps(forward_heap, reverse_heap, endpoint_candidates);

search(engine_working_data,
           facade,
           forward_heap,
           reverse_heap,
           weight,
           packed_leg,
           {},
           {},
           endpoint_candidates);

std::vector<NodeID> unpacked_nodes;
    std::vector<EdgeID> unpacked_edges;

if (!packed_leg.empty())
    {
        unpacked_nodes.reserve(packed_leg.size());
        unpacked_edges.reserve(packed_leg.size());
        unpacked_nodes.push_back(packed_leg.front());
        ch::unpackPath(facade,
                       packed_leg.begin(),
                       packed_leg.end(),
                       [&unpacked_nodes, &unpacked_edges](std::pair<NodeID, NodeID> &edge,
                                                          const auto &edge_id) {
                           BOOST_ASSERT(edge.first == unpacked_nodes.back());
                           unpacked_nodes.push_back(edge.second);
                           unpacked_edges.push_back(edge_id);
                       });
    }

return extractRoute(facade, weight, endpoint_candidates, unpacked_nodes, unpacked_edges);
}

template <>
InternalRouteResult directShortestPathSearch(SearchEngineData<mld::Algorithm> &engine_working_data,
                                             const DataFacade<mld::Algorithm> &facade,
                                             const PhantomEndpointCandidates &endpoint_candidates)
{
    engine_working_data.InitializeOrClearFirstThreadLocalStorage(facade.GetNumberOfNodes(),
                                                                 facade.GetMaxBorderNodeID() + 1);
    auto &forward_heap = *engine_working_data.forward_heap_1;
    auto &reverse_heap = *engine_working_data.reverse_heap_1;
    insertNodesInHeaps(forward_heap, reverse_heap, endpoint_candidates);

// TODO: when structured bindings will be allowed change to
    // auto [weight, source_node, target_node, unpacked_edges] = ...
    EdgeWeight weight = INVALID_EDGE_WEIGHT;
    std::vector<NodeID> unpacked_nodes;
    std::vector<EdgeID> unpacked_edges;
    std::tie(weight, unpacked_nodes, unpacked_edges) = mld::search(engine_working_data,
                                                                   facade,
                                                                   forward_heap,
                                                                   reverse_heap,
                                                                   {},
                                                                   {},
                                                                   INVALID_EDGE_WEIGHT,
                                                                   endpoint_candidates);

return extractRoute(facade, weight, endpoint_candidates, unpacked_nodes, unpacked_edges);
}

} // namespace osrm::engine::routing_algorithms

#include "engine/routing_algorithms/direct_shortest_path.hpp" #include "engine/routing_algorithms/routing_base.hpp" #include "engine/routing_algorithms/routing_base_ch.hpp" #include "engine/routing_algorithms/routing_base_mld.hpp" namespace osrm::engine::routing_algorithms { /// This is a stripped down version of the general shortest path algorithm. /// The general algorithm always computes two queries for each leg. This is only /// necessary in case of vias, where the directions of the start node is constrained /// by the previous route. /// This variation is only an optimization for graphs with slow queries, for example /// not fully contracted graphs. template <> InternalRouteResult directShortestPathSearch(SearchEngineData &engine_working_data, const DataFacade &facade, const PhantomEndpointCandidates &endpoint_candidates) { engine_working_data.InitializeOrClearFirstThreadLocalStorage(facade.GetNumberOfNodes()); auto &forward_heap = *engine_working_data.forward_heap_1; auto &reverse_heap = *engine_working_data.reverse_heap_1; forward_heap.Clear(); reverse_heap.Clear(); EdgeWeight weight = INVALID_EDGE_WEIGHT; std::vector packed_leg; insertNodesInHeaps(forward_heap, reverse_heap, endpoint_candidates); search(engine_working_data, facade, forward_heap, reverse_heap, weight, packed_leg, {}, {}, endpoint_candidates); std::vector unpacked_nodes; std::vector unpacked_edges; if (!packed_leg.empty()) { unpacked_nodes.reserve(packed_leg.size()); unpacked_edges.reserve(packed_leg.size()); unpacked_nodes.push_back(packed_leg.front()); ch::unpackPath(facade, packed_leg.begin(), packed_leg.end(), [&unpacked_nodes, &unpacked_edges](std::pair &edge, const auto &edge_id) { BOOST_ASSERT(edge.first == unpacked_nodes.back()); unpacked_nodes.push_back(edge.second); unpacked_edges.push_back(edge_id); }); } return extractRoute(facade, weight, endpoint_candidates, unpacked_nodes, unpacked_edges); } template <> InternalRouteResult directShortestPathSearch(SearchEngineData &engine_working_data, const DataFacade &facade, const PhantomEndpointCandidates &endpoint_candidates) { engine_working_data.InitializeOrClearFirstThreadLocalStorage(facade.GetNumberOfNodes(), facade.GetMaxBorderNodeID() + 1); auto &forward_heap = *engine_working_data.forward_heap_1; auto &reverse_heap = *engine_working_data.reverse_heap_1; insertNodesInHeaps(forward_heap, reverse_heap, endpoint_candidates); // TODO: when structured bindings will be allowed change to // auto [weight, source_node, target_node, unpacked_edges] = ... EdgeWeight weight = INVALID_EDGE_WEIGHT; std::vector unpacked_nodes; std::vector unpacked_edges; std::tie(weight, unpacked_nodes, unpacked_edges) = mld::search(engine_working_data, facade, forward_heap, reverse_heap, {}, {}, INVALID_EDGE_WEIGHT, endpoint_candidates); return extractRoute(facade, weight, endpoint_candidates, unpacked_nodes, unpacked_edges); } } // namespace osrm::engine::routing_algorithms