FM / routing_algorithms

/srv/osrm/osrm-backend/include/engine/routing_algorithms/

/srv/osrm/osrm-backend/include/engine/routing_algorithms

Name	Size	Mode	Actions
alternative_path.hpp	1104	0644	edit dl rm
direct_shortest_path.hpp	1076	0644	edit dl rm
many_to_many.hpp	3039	0644	edit dl rm
map_matching.hpp	1243	0644	edit dl rm
routing_base.hpp	17312	0644	edit dl rm
routing_base_ch.hpp	20740	0644	edit dl rm
routing_base_mld.hpp	27398	0644	edit dl rm
shortest_path.hpp	688	0644	edit dl rm
shortest_path_impl.hpp	34889	0644	edit dl rm
tile_turns.hpp	1201	0644	edit dl rm

Edit: /srv/osrm/osrm-backend/include/engine/routing_algorithms/many_to_many.hpp (3039B)

#ifndef MANY_TO_MANY_ROUTING_HPP
#define MANY_TO_MANY_ROUTING_HPP

#include "engine/algorithm.hpp"
#include "engine/datafacade.hpp"
#include "engine/search_engine_data.hpp"

#include "util/typedefs.hpp"

#include <vector>

namespace osrm::engine::routing_algorithms
{
namespace
{
struct NodeBucket
{
    NodeID middle_node;
    NodeID parent_node;
    unsigned column_index : 31; // a column in the weight/duration matrix
    unsigned from_clique_arc : 1;
    EdgeWeight weight;
    EdgeDuration duration;
    EdgeDistance distance;

NodeBucket(NodeID middle_node,
               NodeID parent_node,
               bool from_clique_arc,
               unsigned column_index,
               EdgeWeight weight,
               EdgeDuration duration,
               EdgeDistance distance)
        : middle_node(middle_node), parent_node(parent_node), column_index(column_index),
          from_clique_arc(from_clique_arc), weight(weight), duration(duration), distance(distance)
    {
    }

NodeBucket(NodeID middle_node,
               NodeID parent_node,
               unsigned column_index,
               EdgeWeight weight,
               EdgeDuration duration,
               EdgeDistance distance)
        : middle_node(middle_node), parent_node(parent_node), column_index(column_index),
          from_clique_arc(false), weight(weight), duration(duration), distance(distance)
    {
    }

// partial order comparison
    bool operator<(const NodeBucket &rhs) const
    {
        return std::tie(middle_node, column_index) < std::tie(rhs.middle_node, rhs.column_index);
    }

// functor for equal_range
    struct Compare
    {
        bool operator()(const NodeBucket &lhs, const NodeID &rhs) const
        {
            return lhs.middle_node < rhs;
        }

bool operator()(const NodeID &lhs, const NodeBucket &rhs) const
        {
            return lhs < rhs.middle_node;
        }
    };

// functor for equal_range
    struct ColumnCompare
    {
        unsigned column_idx;

ColumnCompare(unsigned column_idx) : column_idx(column_idx){};

bool operator()(const NodeBucket &lhs, const NodeID &rhs) const // lowerbound
        {
            return std::tie(lhs.middle_node, lhs.column_index) < std::tie(rhs, column_idx);
        }

bool operator()(const NodeID &lhs, const NodeBucket &rhs) const // upperbound
        {
            return std::tie(lhs, column_idx) < std::tie(rhs.middle_node, rhs.column_index);
        }
    };
};
} // namespace

template <typename Algorithm>
std::pair<std::vector<EdgeDuration>, std::vector<EdgeDistance>>
manyToManySearch(SearchEngineData<Algorithm> &engine_working_data,
                 const DataFacade<Algorithm> &facade,
                 const std::vector<PhantomNodeCandidates> &candidates_list,
                 const std::vector<std::size_t> &source_indices,
                 const std::vector<std::size_t> &target_indices,
                 const bool calculate_distance);

} // namespace osrm::engine::routing_algorithms

#endif

#ifndef MANY_TO_MANY_ROUTING_HPP #define MANY_TO_MANY_ROUTING_HPP #include "engine/algorithm.hpp" #include "engine/datafacade.hpp" #include "engine/search_engine_data.hpp" #include "util/typedefs.hpp" #include namespace osrm::engine::routing_algorithms { namespace { struct NodeBucket { NodeID middle_node; NodeID parent_node; unsigned column_index : 31; // a column in the weight/duration matrix unsigned from_clique_arc : 1; EdgeWeight weight; EdgeDuration duration; EdgeDistance distance; NodeBucket(NodeID middle_node, NodeID parent_node, bool from_clique_arc, unsigned column_index, EdgeWeight weight, EdgeDuration duration, EdgeDistance distance) : middle_node(middle_node), parent_node(parent_node), column_index(column_index), from_clique_arc(from_clique_arc), weight(weight), duration(duration), distance(distance) { } NodeBucket(NodeID middle_node, NodeID parent_node, unsigned column_index, EdgeWeight weight, EdgeDuration duration, EdgeDistance distance) : middle_node(middle_node), parent_node(parent_node), column_index(column_index), from_clique_arc(false), weight(weight), duration(duration), distance(distance) { } // partial order comparison bool operator<(const NodeBucket &rhs) const { return std::tie(middle_node, column_index) < std::tie(rhs.middle_node, rhs.column_index); } // functor for equal_range struct Compare { bool operator()(const NodeBucket &lhs, const NodeID &rhs) const { return lhs.middle_node < rhs; } bool operator()(const NodeID &lhs, const NodeBucket &rhs) const { return lhs < rhs.middle_node; } }; // functor for equal_range struct ColumnCompare { unsigned column_idx; ColumnCompare(unsigned column_idx) : column_idx(column_idx){}; bool operator()(const NodeBucket &lhs, const NodeID &rhs) const // lowerbound { return std::tie(lhs.middle_node, lhs.column_index) < std::tie(rhs, column_idx); } bool operator()(const NodeID &lhs, const NodeBucket &rhs) const // upperbound { return std::tie(lhs, column_idx) < std::tie(rhs.middle_node, rhs.column_index); } }; }; } // namespace template std::pair, std::vector> manyToManySearch(SearchEngineData &engine_working_data, const DataFacade &facade, const std::vector &candidates_list, const std::vector &source_indices, const std::vector &target_indices, const bool calculate_distance); } // namespace osrm::engine::routing_algorithms #endif