Contract bug leading to "Impossible route between points"

[fenwuyaoji]

Issue

Hi, I used a customized OSM file with 6 ways(117024096, 866851050, 210884329, 1079725575, 1094715491, 1094715088). I just tagged way 117024096 as a toll road (toll=yes). I used default car.lua and CH algo to build an OSRM server. When I called route API without any params, it returned a route with toll:

But when I added exclude=toll, an error occurred: {"NoRoute", "Impossible route between points"}.

However, after I modified the car.lua and deleted motorway and ferry from excludable, I can get the correct result:

To check this issue, I also set all these ways as not oneway road, this issue also can be fixed. MLD is ok too. So this is a specific issue in CH algo I think. The most perhaps function is contractGraph.

I'm still checking the code but I would appreciate if any guy could help me and point out the reason.

Steps to reproduce

check the data on https://www.openstreetmap.org/#map=18/13.884394/100.650848
Please provide the steps required to reproduce your problem.

• osrm-backend version being used: commit d71e2830
• OSM extract that was processed
• Processing commands: CH processing
• Server queries
  http://localhost:5001/route/v1/driving/100.65271,13.884891;100.64929,13.882496
  http://localhost:5001/route/v1/driving/100.65271,13.884891;100.64929,13.882496?exclude=toll

Specifications

not an env-related issue.

[tallongsun]

std::vector<TestEdge> edges = {TestEdge{1, 0, 39},
                                   TestEdge{0, 5, 216},
                                   TestEdge{0, 6, 273},
                                   TestEdge{8, 5, 84},

                                   TestEdge{3, 1, 15},
                                   TestEdge{3, 2, 15},
                                   TestEdge{2, 7, 414},
                                   TestEdge{2, 8, 431},
                                   TestEdge{6, 7, 59},
                                   TestEdge{7, 4, 509},
                                   TestEdge{4, 8, 293}};
    auto reference_graph = makeGraph(edges);

    auto contracted_graph = reference_graph;

    QueryGraph query_graph;
    std::vector<std::vector<bool>> edge_filters;
    std::tie(query_graph, edge_filters) = contractExcludableGraph(
        contracted_graph, {1, 1, 1, 1, 1, 1,1,1,1},
        {{true,true,true,true,true,true,true,true,true},
         {false,true,true,true,true,false,true,true,true},
         {false,false,true,false,true,false,true,true,true},
         {true,true,true,true,true,true,true,true,true}});

    BOOST_CHECK(query_graph.FindEdge(3, 2) == SPECIAL_EDGEID);
    BOOST_CHECK(query_graph.FindEdge(7, 2) == SPECIAL_EDGEID);

have tried with above unit test code which can 100% reproduce this problem. As shown in the assertion, edge 3->2(forward) and 7->2(reverse) have been deleted after contracting. So if we wanna find a route from 3 to 7, we'll get impossible route but actually there's a route 3->2->7.
not sure if it's a behavior what ch algorithm supposed to be or a bug of ch algorithm.