Skip to content

Latest commit

 

History

History
86 lines (67 loc) · 4.86 KB

map.osrm.ebg.md

File metadata and controls

86 lines (67 loc) · 4.86 KB

.osrm.ebg

Contains Edge-expanded Graph Edges.

List

tar -tvf nevada-latest.osrm.ebg
-rw-rw-r-- 0/0               8 1970-01-01 00:00 osrm_fingerprint.meta
-rw-rw-r-- 0/0               8 1970-01-01 00:00 /common/number_of_edge_based_nodes.meta
-rw-rw-r-- 0/0               4 1970-01-01 00:00 /common/number_of_edge_based_nodes
-rw-rw-r-- 0/0               8 1970-01-01 00:00 /common/edge_based_edge_list.meta
-rw-rw-r-- 0/0        34046304 1970-01-01 00:00 /common/edge_based_edge_list
-rw-rw-r-- 0/0               8 1970-01-01 00:00 /common/connectivity_checksum.meta
-rw-rw-r-- 0/0               4 1970-01-01 00:00 /common/connectivity_checksum

osrm_fingerprint.meta

/common/number_of_edge_based_nodes, /common/number_of_edge_based_nodes.meta

Layout

Implementation

The number_of_edge_based_nodes duplicates the nodes.meta of .osrm.ebg_nodes.

/common/edge_based_edge_list, /common/edge_based_edge_list.meta

Layout

Implementation

OSRM defines struct EdgeBasedEdge to represent edge-expanded graph edge.

struct EdgeBasedEdge
{
  public:
    struct EdgeData
    {
        // ... 

        NodeID turn_id; // ID of the edge based node (node based edge)
        EdgeWeight weight;
        EdgeDistance distance;
        EdgeWeight duration : 30;
        std::uint32_t forward : 1;
        std::uint32_t backward : 1;
    };

    // ... 

    NodeID source;
    NodeID target;
    EdgeData data;
};

The EdgeBasedEdges will be generated via generate_edge in EdgeBasedGraphFactory::GenerateEdgeExpandedEdges.
The weigt/duration/distance are calculated after process turn to get turn weight/duration.

            auto weight = boost::numeric_cast<EdgeWeight>(edge_data1.weight + weight_penalty);
            auto duration = boost::numeric_cast<EdgeWeight>(edge_data1.duration + duration_penalty);
            auto distance = boost::numeric_cast<EdgeDistance>(edge_data1.distance);

A little more specially, the turn_id is the same index to identify the TurnIndexBlocks in .osrm.turn_penalities_inex, TurnWeights in .osrm.turn_weight_penalties and TurnDurations in .osrm.turn_duration_penalties, since it simply loops the EdgeBasedEdges to set the value. The order of EdgeBasedEdges and TurnIndexBlocks are the same.

        // [Jay] same order 
        auto const transfer_data = [&](const EdgeWithData &edge_with_data) {
            m_edge_based_edge_list.push_back(edge_with_data.edge);
            turn_weight_penalties.push_back(edge_with_data.turn_weight_penalty);
            turn_duration_penalties.push_back(edge_with_data.turn_duration_penalty);
            turn_indexes_write_buffer.push_back(edge_with_data.turn_index);
        };

/common/connectivity_checksum, /common/connectivity_checksum.meta

Layout

Implementation

The connectivity_checksum is a checksum value that calculated in EdgeBasedGraphFactory::GenerateEdgeExpandedEdges when everything have been processed.