Quick start to Code - sayr777/osrm-backend GitHub Wiki

parts of code:

data_structures folder contains data structures that are the basis for calculation and storage. in the code used many abstract/interface/virtual/template data types that are used at declaration of variables but at initialization there is a more specific data type. the interesting files to start learning are:

library/osrm_impl.hpp is de-facto the main file. plugins are included there.

server/data_structures/internal_datafacade.hpp it is basically a proxy class that merges several classes together into a single class. it contains different data structures of same loaded map data to help use the data in several useful ways: rtree,graph... facade class holds the data.

EdgeDataT is EdgeData from data_structures/query_edge.hpp EdgeData has a backward node id (the first connecting point) and a forward (node id the second connecting point)

data_structures/static_rtree.hpp which is index of rectangles allows to find a point in a rectangle.

data_structures/static_graph.hpp it is an index of edges by source id. there is an array of source ids ordered by source node id. same source ids are skipped, you can know how many nodes originate from same source node, by looking at next element in this array. the current source id to next source id is a range of integer ids to query node details.

    // note the comments

    //aliases to know:

    using NodeID = unsigned int;
    using EdgeID = unsigned int;
    using EdgeWeight = int;

    static const NodeID SPECIAL_NODEID = std::numeric_limits<unsigned>::max();
    static const EdgeID SPECIAL_EDGEID = std::numeric_limits<unsigned>::max();
    static const unsigned INVALID_NAMEID = std::numeric_limits<unsigned>::max();
    static const EdgeWeight INVALID_EDGE_WEIGHT = std::numeric_limits<int>::max();

    using NodeIterator = NodeID;
    using EdgeIterator = NodeID;
    using EdgeData = EdgeDataT;
    using EdgeRange = osrm::range<EdgeIterator>;

    //StaticGraph:
 
    EdgeIterator BeginEdges(const NodeIterator n) const
    {
        return EdgeIterator(node_array.at(n).first_edge);
    }

    EdgeIterator EndEdges(const NodeIterator n) const
    {
        return EdgeIterator(node_array.at(n + 1).first_edge);
    }

    EdgeRange GetAdjacentEdgeRange(const NodeID node) const
    {
        return osrm::irange(BeginEdges(node), EndEdges(node)); 
                   //irange behaves like fake integer.  it has a '++' operator to iterate to next until range end.
                   //and != operator. 
                   //and (int) operator to returns the current position when used as integer
    }
    
    //then GetAdjacentEdgeRange function is used as:

    for (auto edge : facade->GetAdjacentEdgeRange(from))
    {
            const NodeID target = GetTarget(edge);
            const EdgeWeight weight = GetEdgeData(edge).distance;

folder routing_algorithms contains the routing algorithms

data_structures/search_engine.hpp it is basically holds classes of all routing algorithms as public variables in a single class.

template <class DataFacadeT> class SearchEngine
{
  public:
    ShortestPathRouting<DataFacadeT> shortest_path;
    AlternativeRouting<DataFacadeT> alternative_path;
    ManyToManyRouting<DataFacadeT> distance_table;
    MapMatching<DataFacadeT> map_matching;
    
    //it initializes the variables right away with facade argument in the constructor

folder routing_algorithms/routing_base.hpp contains general utility functions for routing algorithms. in general all base classes are a place for utility functions.

less interesting just to know how it works:

folder algorithms contains the path simplification algorithms and coordinate array to a compressed string encoding algorithms

folder server . the server is similar to a way that node.js most basic http server works. i.e. there is a handle request function. that is executed for each request it decides what to execute and it should return a result to the user. until it returns a result the connection hangs open.

request_handler.cpp in it the handle request function parses the query string, later encodes the json to a string to be sent.

it executes RunQuery() in library/osrm_impl.cpp which iterates over the array of registered plugins and runs on the found plugin: plugin_iterator->second->HandleRequest(route_parameters, json_result);.

include/osrm/route_parameters.hpp is a data structure that just stores all possible http url query string parameters. coordinates parameter is an array.

struct RouteParameters
{
    short zoom_level;
    bool print_instructions;
    bool alternate_route;
    bool geometry;
    bool compression;
    bool deprecatedAPI;
    bool uturn_default;
    bool classify;
    double matching_beta;
    double gps_precision;
    unsigned check_sum;
    short num_results;
    std::string service;
    std::string output_format;
    std::string jsonp_parameter;
    std::string language;
    std::vector<std::string> hints;
    std::vector<unsigned> timestamps;
    std::vector<bool> uturns;
    std::vector<FixedPointCoordinate> coordinates;