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/routing_base.cpp (4208B)

#include "engine/routing_algorithms/routing_base.hpp"

namespace osrm::engine::routing_algorithms
{

bool requiresForwardLoop(const PhantomNode &source, const PhantomNode &target)
{
    return source.IsValidForwardSource() && target.IsValidForwardTarget() &&
           source.forward_segment_id.id == target.forward_segment_id.id &&
           source.GetForwardWeightPlusOffset() > target.GetForwardWeightPlusOffset();
}

bool requiresBackwardLoop(const PhantomNode &source, const PhantomNode &target)
{
    return source.IsValidReverseSource() && target.IsValidReverseTarget() &&
           source.reverse_segment_id.id == target.reverse_segment_id.id &&
           source.GetReverseWeightPlusOffset() > target.GetReverseWeightPlusOffset();
}

std::vector<NodeID> getForwardLoopNodes(const PhantomEndpointCandidates &endpoint_candidates)
{
    std::vector<NodeID> res;
    for (const auto &source_phantom : endpoint_candidates.source_phantoms)
    {
        auto requires_loop =
            std::any_of(endpoint_candidates.target_phantoms.begin(),
                        endpoint_candidates.target_phantoms.end(),
                        [&](const auto &target_phantom) {
                            return requiresForwardLoop(source_phantom, target_phantom);
                        });
        if (requires_loop)
        {
            res.push_back(source_phantom.forward_segment_id.id);
        }
    }
    return res;
}

std::vector<NodeID> getForwardLoopNodes(const PhantomCandidatesToTarget &endpoint_candidates)
{
    std::vector<NodeID> res;
    for (const auto &source_phantom : endpoint_candidates.source_phantoms)
    {
        if (requiresForwardLoop(source_phantom, endpoint_candidates.target_phantom))
        {
            res.push_back(source_phantom.forward_segment_id.id);
        }
    }
    return res;
}

std::vector<NodeID> getBackwardLoopNodes(const PhantomEndpointCandidates &endpoint_candidates)
{
    std::vector<NodeID> res;
    for (const auto &source_phantom : endpoint_candidates.source_phantoms)
    {
        auto requires_loop =
            std::any_of(endpoint_candidates.target_phantoms.begin(),
                        endpoint_candidates.target_phantoms.end(),
                        [&](const auto &target_phantom) {
                            return requiresBackwardLoop(source_phantom, target_phantom);
                        });
        if (requires_loop)
        {
            res.push_back(source_phantom.reverse_segment_id.id);
        }
    }
    return res;
}

std::vector<NodeID> getBackwardLoopNodes(const PhantomCandidatesToTarget &endpoint_candidates)
{
    std::vector<NodeID> res;
    for (const auto &source_phantom : endpoint_candidates.source_phantoms)
    {
        if (requiresBackwardLoop(source_phantom, endpoint_candidates.target_phantom))
        {
            res.push_back(source_phantom.reverse_segment_id.id);
        }
    }
    return res;
}

PhantomEndpoints endpointsFromCandidates(const PhantomEndpointCandidates &candidates,
                                         const std::vector<NodeID> &path)
{
    auto source_it = std::find_if(candidates.source_phantoms.begin(),
                                  candidates.source_phantoms.end(),
                                  [&path](const auto &source_phantom) {
                                      return path.front() == source_phantom.forward_segment_id.id ||
                                             path.front() == source_phantom.reverse_segment_id.id;
                                  });
    BOOST_ASSERT(source_it != candidates.source_phantoms.end());

auto target_it = std::find_if(candidates.target_phantoms.begin(),
                                  candidates.target_phantoms.end(),
                                  [&path](const auto &target_phantom) {
                                      return path.back() == target_phantom.forward_segment_id.id ||
                                             path.back() == target_phantom.reverse_segment_id.id;
                                  });
    BOOST_ASSERT(target_it != candidates.target_phantoms.end());

return PhantomEndpoints{*source_it, *target_it};
}

} // namespace osrm::engine::routing_algorithms

#include "engine/routing_algorithms/routing_base.hpp" namespace osrm::engine::routing_algorithms { bool requiresForwardLoop(const PhantomNode &source, const PhantomNode &target) { return source.IsValidForwardSource() && target.IsValidForwardTarget() && source.forward_segment_id.id == target.forward_segment_id.id && source.GetForwardWeightPlusOffset() > target.GetForwardWeightPlusOffset(); } bool requiresBackwardLoop(const PhantomNode &source, const PhantomNode &target) { return source.IsValidReverseSource() && target.IsValidReverseTarget() && source.reverse_segment_id.id == target.reverse_segment_id.id && source.GetReverseWeightPlusOffset() > target.GetReverseWeightPlusOffset(); } std::vector getForwardLoopNodes(const PhantomEndpointCandidates &endpoint_candidates) { std::vector res; for (const auto &source_phantom : endpoint_candidates.source_phantoms) { auto requires_loop = std::any_of(endpoint_candidates.target_phantoms.begin(), endpoint_candidates.target_phantoms.end(), [&](const auto &target_phantom) { return requiresForwardLoop(source_phantom, target_phantom); }); if (requires_loop) { res.push_back(source_phantom.forward_segment_id.id); } } return res; } std::vector getForwardLoopNodes(const PhantomCandidatesToTarget &endpoint_candidates) { std::vector res; for (const auto &source_phantom : endpoint_candidates.source_phantoms) { if (requiresForwardLoop(source_phantom, endpoint_candidates.target_phantom)) { res.push_back(source_phantom.forward_segment_id.id); } } return res; } std::vector getBackwardLoopNodes(const PhantomEndpointCandidates &endpoint_candidates) { std::vector res; for (const auto &source_phantom : endpoint_candidates.source_phantoms) { auto requires_loop = std::any_of(endpoint_candidates.target_phantoms.begin(), endpoint_candidates.target_phantoms.end(), [&](const auto &target_phantom) { return requiresBackwardLoop(source_phantom, target_phantom); }); if (requires_loop) { res.push_back(source_phantom.reverse_segment_id.id); } } return res; } std::vector getBackwardLoopNodes(const PhantomCandidatesToTarget &endpoint_candidates) { std::vector res; for (const auto &source_phantom : endpoint_candidates.source_phantoms) { if (requiresBackwardLoop(source_phantom, endpoint_candidates.target_phantom)) { res.push_back(source_phantom.reverse_segment_id.id); } } return res; } PhantomEndpoints endpointsFromCandidates(const PhantomEndpointCandidates &candidates, const std::vector &path) { auto source_it = std::find_if(candidates.source_phantoms.begin(), candidates.source_phantoms.end(), [&path](const auto &source_phantom) { return path.front() == source_phantom.forward_segment_id.id || path.front() == source_phantom.reverse_segment_id.id; }); BOOST_ASSERT(source_it != candidates.source_phantoms.end()); auto target_it = std::find_if(candidates.target_phantoms.begin(), candidates.target_phantoms.end(), [&path](const auto &target_phantom) { return path.back() == target_phantom.forward_segment_id.id || path.back() == target_phantom.reverse_segment_id.id; }); BOOST_ASSERT(target_it != candidates.target_phantoms.end()); return PhantomEndpoints{*source_it, *target_it}; } } // namespace osrm::engine::routing_algorithms