Function constructRestrictionGraph

src/extractor/restriction_graph.cpp:233–274

} // namespace restriction_graph_details

RestrictionGraph constructRestrictionGraph(const std::vector<TurnRestriction> &turn_restrictions)
{
    util::UnbufferedLog log;
    log << "Constructing restriction graph on " << turn_restrictions.size() << " restrictions...";
    TIMER_START(construct_restriction_graph);

    namespace rgd = restriction_graph_details;
    RestrictionGraph rg;
    rgd::buildGraph<rgd::pathBuilder>(rg, turn_restrictions);
    rgd::buildGraph<rgd::transferBuilder>(rg, turn_restrictions);

    // Reorder nodes so that via nodes are at the front. This makes it easier to represent the
    // bijection between restriction graph via nodes and edge-based graph duplicate nodes.
    std::vector<bool> is_via_node(rg.nodes.size(), false);
    for (const auto &entry : rg.via_edge_to_node)
    {
        is_via_node[entry.second] = true;
    }
    std::vector<RestrictionID> ordering(rg.nodes.size());
    std::iota(ordering.begin(), ordering.end(), 0);
    std::partition(ordering.begin(), ordering.end(), [&](const auto i) { return is_via_node[i]; });
    // Start renumbering
    const auto permutation = util::orderingToPermutation(ordering);
    util::inplacePermutation(rg.nodes.begin(), rg.nodes.end(), permutation);
    std::for_each(rg.edges.begin(),
                  rg.edges.end(),
                  [&](auto &edge) { edge.target = permutation[edge.target]; });
    rg.num_via_nodes = std::count(is_via_node.begin(), is_via_node.end(), true);
    for (auto &entry : rg.via_edge_to_node)
    {
        entry.second = permutation[entry.second];
    }
    for (auto &entry : rg.start_edge_to_node)
    {
        entry.second = permutation[entry.second];
    }

    TIMER_STOP(construct_restriction_graph);
    log << "ok, after " << TIMER_SEC(construct_restriction_graph) << "s";

    return rg;
}

RestrictionGraph::RestrictionRange RestrictionGraph::GetRestrictions(RestrictionID id) const
{