RoutingKit Documentation

While ContractionHierarchy optimizes for a primary weight, you can compute the length of the resulting shortest path according to secondary "extra weights" that were not used during preprocessing.

Key Concepts

• Extra Weights: These do not need to be positive; they can be integers, strings, or other types. They must support operator[] (e.g., std::vector, pointers).
• Link Function: Since extra weights can be non-numeric (like strings), you must provide a link function with the signature Weight link(Weight first, Weight second). This function defines how to combine weights along a path (e.g., addition for numbers, concatenation for strings).
• SaturatedWeightAddition: A recommended link function for numeric weights that handles overflows and underflows (e.g., capping at INT_MIN or handling inf_weight) safely.

Methods

• get_extra_weight_distance(const ExtraWeight& extra_weight, const LinkFunction& link): Computes the extra weight distance for the path found by the primary weight optimization.
• get_extra_weight_distances_to_targets(...): A many-to-many version for pinned targets.
• get_extra_weight_distances_to_sources(...): A many-to-many version for added sources.

Warning: Non-unique Shortest Paths

If multiple paths have the same primary weight but different extra weights, the behavior is undefined. The algorithm is free to pick any of the shortest paths, so the extra weight result may vary depending on which path is chosen.

auto ch = ContractionHierarchy::build(node_count, tail, head, weight);
ContractionHierarchyQuery q(ch);

q.add_source(0).add_target(3).run();

// Using numeric weights with SaturatedWeightAddition
assert(q.get_extra_weight_distance(extra_weight1, SaturatedWeightAddition()) == 20);

// Using complex types (strings) with a custom link function
assert(q.get_extra_weight_distance(extra_weight3, [](std::string l, std::string r){return l+r;}) == "foobar");

RoutingKit represents directed graphs using two primary formats: arc-lists and adjacency-arrays.

Arc-list

An arc-list is a simple structure suitable for most tasks except graph traversal. It consists of:

• node_count: The number of nodes in the graph.
• tail: A vector where tail[i] is the source node of arc i.
• head: A vector where head[i] is the destination node of arc i.
• Arc IDs: The position i in the tail and head vectors is the unique ID of the arc.
• Properties: Additional properties like geo_distance (meters), travel_time (seconds), and speed (km/h) can be stored in parallel vectors.

RoutingKit supports multi-arcs, loops, disconnected graphs, and zero-weights.

Adjacency-array

An adjacency-array is optimized for graph traversal (e.g., iterating over outgoing arcs). It consists of:

• first_out: A vector of size node_count + 1. first_out[x] is the index in head where the outgoing arcs of node x begin. first_out[x+1] is where they end.
• head: A vector containing the destination node IDs.

To iterate over outgoing arcs of node x:

for(unsigned xy=first_out[x]; xy<first_out[x+1]; ++xy){
    unsigned y = head[xy];
    // xy is the arc from node x to node y
}

// Arc-list structure
unsigned node_count;
std::vector<unsigned>tail;
std::vector<unsigned>head;

// Adjacency-array structure
std::vector<unsigned>first_out;
std::vector<unsigned>head;

When filtering elements from a large ID range (e.g., OSM node IDs) into a smaller subset, you need a way to map the original (global) IDs to their new (local) indices.

LocalIDMapper

Found in <routingkit/id_mapper.h>, LocalIDMapper is memory-efficient, requiring less than one bit per element in addition to the BitVector used for filtering.

• to_local(x): Maps a global ID to its new local index. Warning: Only call this if keep_filter.is_set(x) is true.
• to_local(x, default_value): Returns default_value if the global ID x was removed during filtering.
• is_global_id_mapped(x): Checks if the global ID x exists in the filtered set.
• local_id_count(): Returns the number of elements in the filtered set.
• global_id_count(): Returns the size of the original range.

IDMapper

IDMapper provides all the functionality of LocalIDMapper but includes an additional to_global(local_id) method to map from the small range back to the large range. This requires more memory than LocalIDMapper.

Lifecycle Warning

Both mappers store a pointer to the BitVector used to create them. You must ensure the BitVector is not destroyed while the mapper is still in use.

vector<string> names = {"Bob", "Alice", "Charlie", "Malice"};
// Create a filter: keep names where the second character is not 'a'
BitVector keep_filter = make_bit_vector(names.size(), [&](unsigned i){return names[i][1] != 'a';});

LocalIDMapper map(keep_filter);
vector<string> filtered_names = keep_element_of_vector_if(keep_filter, names);

// Mapping back to check correctness
for(unsigned i=0; i<names.size(); ++i){
    if(keep_filter.is_set(i))
        assert(filtered_names[map.to_local(i)] == names[i]); 
}

RoutingKit provides out-of-the-box functions in <routingkit/osm_profile.h> to interpret OSM tags specifically for car routing. This avoids manual tag parsing.

Phase 1 (ID Mapping)

Use is_osm_way_used_by_cars to determine if a way should be included in the graph.

Phase 2 (Graph Decoding)

Use the following functions within your callbacks:

• get_osm_way_speed: Returns speed in km/h.
• get_osm_way_name: Returns the name of the way.
• get_osm_car_direction_category: Determines directionality (OSMWayDirectionCategory).
• decode_osm_car_turn_restrictions: Processes turn restrictions within the turn_restriction_classifier callback.

// In Phase 1 callback:
bool used = is_osm_way_used_by_cars(osm_way_id, tags);

// In Phase 2 oneway_classifier:
OSMWayDirectionCategory dir = get_osm_car_direction_category(osm_way_id, tags);

// In Phase 2 turn_restriction_classifier:
decode_osm_car_turn_restrictions(osm_relation_id, member_list, tags, on_new_turn_restriction, log_message);