FM / extractor

/srv/osrm/osrm-backend/include/extractor/

/srv/osrm/osrm-backend/include/extractor

Name	Size	Mode	Actions
intersection/	-	0755	rm
class_data.hpp	981	0644	edit dl rm
compressed_edge_container.hpp	3336	0644	edit dl rm
compressed_node_based_graph_edge.hpp	418	0644	edit dl rm
conditional_turn_penalty.hpp	589	0644	edit dl rm
datasources.hpp	1207	0644	edit dl rm
edge_based_edge.hpp	3467	0644	edit dl rm
edge_based_graph_factory.hpp	7787	0644	edit dl rm
edge_based_node.hpp	383	0644	edit dl rm
edge_based_node_segment.hpp	2050	0644	edit dl rm
extraction_containers.hpp	3679	0644	edit dl rm
extraction_helper_functions.hpp	4827	0644	edit dl rm
extraction_node.hpp	459	0644	edit dl rm
extraction_relation.hpp	5949	0644	edit dl rm
extraction_segment.hpp	715	0644	edit dl rm
extraction_turn.hpp	4983	0644	edit dl rm
extraction_way.hpp	4268	0644	edit dl rm
extractor.hpp	5267	0644	edit dl rm
extractor_callbacks.hpp	3249	0644	edit dl rm
extractor_config.hpp	3040	0644	edit dl rm
files.hpp	24372	0644	edit dl rm
graph_compressor.hpp	1271	0644	edit dl rm
internal_extractor_edge.hpp	2642	0644	edit dl rm
intersection_bearings_container.hpp	4487	0644	edit dl rm
location_dependent_data.hpp	1797	0644	edit dl rm
maneuver_override.hpp	5456	0644	edit dl rm
maneuver_override_relation_parser.hpp	1785	0644	edit dl rm
name_table.hpp	3596	0644	edit dl rm
nbg_to_ebg.hpp	450	0644	edit dl rm
nodes_of_way.hpp	1411	0644	edit dl rm
node_based_edge.hpp	8024	0644	edit dl rm
node_based_graph_factory.hpp	5155	0644	edit dl rm
node_data_container.hpp	4558	0644	edit dl rm
node_restriction_map.hpp	2292	0644	edit dl rm
packed_osm_ids.hpp	520	0644	edit dl rm
profile_properties.hpp	5029	0644	edit dl rm
query_node.hpp	1411	0644	edit dl rm
raster_source.hpp	5002	0644	edit dl rm
restriction.hpp	1750	0644	edit dl rm
restriction_graph.hpp	4500	0644	edit dl rm
restriction_parser.hpp	1768	0644	edit dl rm
road_classification.hpp	8390	0644	edit dl rm
scripting_environment.hpp	2426	0644	edit dl rm
scripting_environment_lua.hpp	4253	0644	edit dl rm
segment_data_container.hpp	8032	0644	edit dl rm
serialization.hpp	8834	0644	edit dl rm
suffix_table.hpp	1407	0644	edit dl rm
traffic_lights.hpp	514	0644	edit dl rm
traffic_signals.hpp	656	0644	edit dl rm
travel_mode.hpp	3666	0644	edit dl rm
turn_lane_types.hpp	3754	0644	edit dl rm
turn_path.hpp	7483	0644	edit dl rm
turn_path_compressor.hpp	2220	0644	edit dl rm
turn_path_filter.hpp	669	0644	edit dl rm
way_restriction_map.hpp	3114	0644	edit dl rm

Edit: /srv/osrm/osrm-backend/include/extractor/restriction_graph.hpp (4500B)

#ifndef OSRM_EXTRACTOR_RESTRICTION_GRAPH_HPP_
#define OSRM_EXTRACTOR_RESTRICTION_GRAPH_HPP_

#include <boost/assert.hpp>

#include "util/node_based_graph.hpp"
#include "util/std_hash.hpp"
#include "util/typedefs.hpp"

#include <unordered_map>

namespace osrm::extractor
{

struct TurnRestriction;

namespace restriction_graph_details
{
struct transferBuilder;
struct pathBuilder;
} // namespace restriction_graph_details

struct RestrictionEdge
{
    NodeID node_based_to;
    RestrictionID target;
    bool is_transfer;
};

struct RestrictionNode
{
    size_t restrictions_begin_idx;
    size_t num_restrictions;
    size_t edges_begin_idx;
    size_t num_edges;
};

/**
 * The restriction graph is used to represent all possible restrictions within the routing graph.
 * The graph uses an edge-based node representation. Each node represents a compressed
 * node-based edge along a restriction path.
 *
 * Given a list of turn restrictions, the graph is created in multiple steps.
 *
 * INPUT
 * a -> b -> d: no_e
 * a -> b -> c: only_d
 * b -> c -> d: only_f
 * b -> c: no_g
 * e -> b -> d: no_g
 *
 * Step 1: create a disjoint union of prefix trees for all restriction paths.
 * The restriction instructions are added to the final node in its path.
 *
 * STEP 1
 * (a,b) -> (b,d,[no_e])
 *      \->(b,c,[only_d])
 *
 * (b,c,[no_g]) -> (c,d,[only_f])
 * (e,b) -> (b,d,[no_g])
 *
 * Step 2: add transfers between restriction paths that overlap.
 * We do this by traversing each restriction path, tracking where the suffix of our current path
 * matches the prefix of any other. If it does, there's opportunity to transfer to the suffix
 * restriction path *if* the transfer would not be restricted *and* that edge does not take us
 * further on our current path. Nested restrictions are also added from any of the suffix paths.
 *
 * STEP 2
 * (a,b) -> (b,d,[no_e])
 *      \->(b,c,[only_d,no_g])
 *                \
 * (b,c,[no_g]) -> \-> (c,d,[only_f])
 *
 * (e,b) -> (b,d,[no_g])
 * If a transfer applies to multiple suffix paths, we only add the edge to the largest suffix path.
 * This ensures we correctly track all overlapping paths.
 *
 *
 * Step 3: The nodes are split into
 * start nodes - compressed edges that are entry points into a restriction path.
 * via nodes - compressed edges that are intermediate steps along a restriction path.
 * Start nodes and via nodes are indexed by the compressed node-based edge for easy retrieval
 *
 * STEP 3
 * Start Node Index
 * (a,b) => (a,b)
 * (b,c) => (b,c,[no_g])
 * (e,b) => (e,b)
 *
 * Via Nodes Index
 * (b,c) => (b,c,[only_d,no_g])
 * (b,d) => (b,d,[no_e]) , (b,d,[no_g])
 * (c,d) => (c,d,[only_f])
 *
 * Duplicate Nodes:
 * There is a 1-1 mapping between restriction graph via nodes and edge-based-graph duplicate nodes.
 * This relationship is used in the creation of restrictions in the routing edge-based graph.
 * */
struct RestrictionGraph
{
    friend restriction_graph_details::pathBuilder;
    friend restriction_graph_details::transferBuilder;
    friend RestrictionGraph constructRestrictionGraph(const std::vector<TurnRestriction> &);

using EdgeRange = boost::iterator_range<std::vector<RestrictionEdge>::const_iterator>;
    using RestrictionRange =
        boost::iterator_range<std::vector<const TurnRestriction *>::const_iterator>;
    using EdgeKey = std::pair<NodeID, NodeID>;

// Helper functions for iterating over node restrictions and edges
    EdgeRange GetEdges(RestrictionID id) const;
    RestrictionRange GetRestrictions(RestrictionID id) const;

// A compressed node-based edge can only have one start node in the restriction graph.
    std::unordered_map<EdgeKey, RestrictionID> start_edge_to_node{};
    // A compressed node-based edge can have multiple via nodes in the restriction graph
    // (as the compressed edge can appear in paths with different prefixes).
    std::unordered_multimap<EdgeKey, RestrictionID> via_edge_to_node{};
    std::vector<RestrictionNode> nodes;
    // TODO: Investigate reusing DynamicGraph. Currently it requires specific attributes
    // (e.g. reversed, weight) that would not make sense for restrictions.
    std::vector<RestrictionEdge> edges;
    std::vector<const TurnRestriction *> restrictions;
    size_t num_via_nodes{};

private:
    RestrictionGraph() = default;
};

RestrictionGraph constructRestrictionGraph(const std::vector<TurnRestriction> &turn_restrictions);

} // namespace osrm::extractor

#endif // OSRM_EXTRACTOR_RESTRICTION_GRAPH_HPP_

cmd: