[windows | example.cpp] MLD route algorithm always returns no path while CH returns path #5872
Description
I compiled the windows version with reference to https://github.com/Project-OSRM/osrm-backend/wiki/Windows-Compilation.
The test environment is the visual studio 2019 community .
The data uses the china-latest.osm.pbf downloaded from the official website and the default car.profile that comes with the program. The other values are the default.
Run osrm-extract and osrm-contract, and then use the CH algorithm in example.cpp can get the path. Save the data required by CH to a folder separately.
Run osrm-extract, osrm-partition, and osrm-customize in sequence to get the data needed by MLD. But using the MLD algorithm in example.cpp always returns status error.
I doubt if there is a problem with the osrm-partition, as there are data in the leve3 and level4, But empty in the statistic output.
The running results and example.cpp are as follows：
D:\newmap_build\osrm-backend\build\Release>osrm-extract D:\newmap_build\osrm-backend\osmdata\china-latest.osm.pbf -p D:\newmap_build\osrm-backend\profiles\car.lua
[info] Parsed 0 location-dependent features with 0 GeoJSON polygons�[0m
[info] Using script D:\newmap_build\osrm-backend\profiles\car.lua�[0m
[info] Input file: china-latest.osm.pbf�[0m
[info] Profile: car.lua�[0m
[info] Threads: 8�[0m
[info] Parsing in progress..�[0m
[info] input file generated by osmium/1.8.0�[0m
[info] timestamp: 2020-09-06T20:42:02Z�[0m
[info] Using profile api version 4�[0m
[info] Found 3 turn restriction tags:�[0m
[info] motorcar�[0m
[info] motor_vehicle�[0m
[info] vehicle�[0m
[info] Parse relations ...�[0m
[info] Parse ways and nodes ...�[0m
[info] Using profile api version 4�[0m
[info] Using profile api version 4�[0m
[info] Using profile api version 4�[0m
[info] Using profile api version 4�[0m
[info] Using profile api version 4�[0m
[info] Using profile api version 4�[0m
[info] Using profile api version 4�[0m
[info] Parsing finished after 177.607 seconds�[0m
[info] Raw input contains 91020685 nodes, 6962242 ways, and 11526 relations, 8498 restrictions�[0m
[info] Sorting used nodes ... ok, after 2.34935s�[0m
[info] Erasing duplicate nodes ... ok, after 0.249316s�[0m
[info] Sorting all nodes ... ok, after 0.167437s�[0m
[info] Building node id map ... ok, after 1.06389s�[0m
[info] Confirming/Writing used nodes ... ok, after 9.25175s�[0m
[info] Writing barrier nodes ... ok, after 0s�[0m
[info] Writing traffic light nodes ... ok, after 0s�[0m
[info] Processed 37134908 nodes�[0m
[info] Sorting edges by start ... ok, after 4.3514s�[0m
[info] Setting start coords ... ok, after 12.4638s�[0m
[info] Sorting edges by target ... ok, after 4.01986s�[0m
[info] Computing edge weights ... ok, after 24.8413s�[0m
[info] Sorting edges by renumbered start ... ok, after 4.66812s�[0m
[info] Writing used edges ... ok, after 16.6207s -- Processed 38848767 edges�[0m
[info] Writing way meta-data ... ok, after 0.107016s -- Metadata contains << 3157974 entries.�[0m
[info] Sorting used ways ... ok, after 0.005562s�[0m
[info] Collecting start/end information on 0 maneuver overrides...ok, after 0.151458s�[0m
[info] Collecting start/end information on 0 maneuver overrides...ok, after 0s�[0m
[info] Collecting start/end information on 8498 restrictions...ok, after 0.29022s�[0m
[info] Collecting start/end information on 8498 restrictions...ok, after 0.022269s�[0m
[info] writing street name index ... ok, after 0.046881s�[0m
[info] extraction finished after 260.573s�[0m
[info] Generating edge-expanded graph representation�[0m
[info] . 10% . 20% . 30% . 40% . 50% . 60% . 70% . 80% . 90% . 100%�[0m
[info] Node compression ratio: 0.124136�[0m
[info] Edge compression ratio: 0.162755�[0m
[info] graph compression removed 3041290 annotations of 3157974 in 32.5947 seconds�[0m
[info] Find segregated edges in node-based graph ...�[0m
[info] ok, after 52.9639s�[0m
[info] Segregated edges count = 475451�[0m
[info] Writing nodes for nodes-based and edges-based graphs ...�[0m
�[33m[warn] Clipped 16 segment weights to 4194302�[0m
[info] Geometry successfully removed:
compressed edges: 12645400
compressed geometries: 77711718
longest chain length: 4865
cmpr ratio: 0.162722
avg chain length: 6.14545�[0m
[info] Generating edge expanded nodes ... �[0m
[info] . 10% . 20% . 30% . 40% . 50% . 60% . 70% . 80% . 90% . 100%�[0m
[info] Expanding via-way turn restrictions ... �[0m
[info] . 10% . 20% . 30% . 40% . 50% . 60% . 70% . 80% . 90% . 100%�[0m
[info] Generated 11011881 nodes (847 of which are duplicates) and 38847811 segments in edge-expanded graph�[0m
[info] Generating edge-expanded edges �[0m
[info] �[33m[warn] Turn is a u turn but not turning to the first connected edge of the intersection. Node ID: 1393233, OSM link: http://www.openstreetmap.org/?zoom=18&mlat=39.86658&mlon=116.233854�[0m
. 10% . 20% �[33m[warn] Turn is a u turn but not turning to the first connected edge of the intersection. Node ID: 7480460, OSM link: http://www.openstreetmap.org/?zoom=18&mlat=43.823451&mlon=90.296722�[0m
. 30% �[33m[warn] Turn is a u turn but not turning to the first connected edge of the intersection. Node ID: 12857084, OSM link: http://www.openstreetmap.org/?zoom=18&mlat=28.034628&mlon=120.590075�[0m
. 40% �[33m[warn] Turn is a u turn but not turning to the first connected edge of the intersection. Node ID: 15973893, OSM link: http://www.openstreetmap.org/?zoom=18&mlat=32.143062&mlon=115.061189�[0m
.�[33m[warn] Turn is a u turn but not turning to the first connected edge of the intersection. Node ID: 17840227, OSM link: http://www.openstreetmap.org/?zoom=18&mlat=22.598895&mlon=113.20451�[0m
50% . 60% �[33m[warn] Turn is a u turn but not turning to the first connected edge of the intersection. Node ID: 23827676, OSM link: http://www.openstreetmap.org/?zoom=18&mlat=22.807058&mlon=113.284883�[0m
�[33m[warn] Turn is a u turn but not turning to the first connected edge of the intersection. Node ID: 23827676, OSM link: http://www.openstreetmap.org/?zoom=18&mlat=22.807058&mlon=113.284883�[0m
�[33m[warn] Turn is a u turn but not turning to the first connected edge of the intersection. Node ID: 23827676, OSM link: http://www.openstreetmap.org/?zoom=18&mlat=22.807058&mlon=113.284883�[0m
. 70% . 80% . 90% .�[33m[warn] Turn is a u turn but not turning to the first connected edge of the intersection. Node ID: 36298063, OSM link: http://www.openstreetmap.org/?zoom=18&mlat=30.42826&mlon=104.053162�[0m
�[0m
[info] Sorting and writing 0 maneuver overrides...�[0m
[info] done.�[0m
[info] Renumbering turns�[0m
[info] Writing 0 conditional turn penalties...�[0m
[info] Generated 38847811 edge based node segments�[0m
[info] Node-based graph contains 10960726 edges�[0m
[info] Edge-expanded graph ...�[0m
[info] contains 22050874 edges�[0m
[info] Timing statistics for edge-expanded graph:�[0m
[info] Renumbering edges: 2.06041s�[0m
[info] Generating nodes: 15.1192s�[0m
[info] Generating edges: 93.8751s�[0m
[info] Generating guidance turns �[0m
[info] . 10% . 20% . 30% . 40% . 50% . 60% . 70% . 80% . 90% .�[0m
[info] done.�[0m
[info] Created 164 entry classes and 48126 Bearing Classes�[0m
[info] Handled: 807 of 9538 lanes: 8.46089 %.�[0m
[info] Assigned 24175006 turn instruction types:�[0m
[info] new name: 494306 (2.04%)�[0m
[info] continue: 952035 (3.94%)�[0m
[info] turn: 10622228 (43.94%)�[0m
[info] merge: 60019 (0.25%)�[0m
[info] on ramp: 36509 (0.15%)�[0m
[info] off ramp: 49920 (0.21%)�[0m
[info] fork: 147548 (0.61%)�[0m
[info] end of road: 3397210 (14.05%)�[0m
[info] notification: 1639 (0.01%)�[0m
[info] enter roundabout: 11694 (0.05%)�[0m
[info] enter and exit roundabout: 1662 (0.01%)�[0m
[info] enter rotary: 712 (0.00%)�[0m
[info] enter and exit rotary: 77 (0.00%)�[0m
[info] enter roundabout turn: 2222 (0.01%)�[0m
[info] enter and exit roundabout turn: 3 (0.00%)�[0m
[info] (noturn): 434331 (1.80%)�[0m
[info] (suppressed): 7908551 (32.71%)�[0m
[info] roundabout: 1582 (0.01%)�[0m
[info] exit roundabout: 14001 (0.06%)�[0m
[info] rotary: 61 (0.00%)�[0m
[info] exit rotary: 852 (0.00%)�[0m
[info] roundabout turn: 2 (0.00%)�[0m
[info] exit roundabout turn: 2249 (0.01%)�[0m
[info] (stay on roundabout): 16424 (0.07%)�[0m
[info] (sliproad): 19169 (0.08%)�[0m
[info] Assigned 24175006 turn instruction modifiers:�[0m
[info] uturn: 920507 (3.81%)�[0m
[info] sharp right: 393485 (1.63%)�[0m
[info] right: 6846947 (28.32%)�[0m
[info] slight right: 564320 (2.33%)�[0m
[info] straight: 8197727 (33.91%)�[0m
[info] slight left: 511721 (2.12%)�[0m
[info] left: 6332456 (26.19%)�[0m
[info] sharp left: 407843 (1.69%)�[0m
[info] Guidance turn annotations took 112.621s�[0m
[info] Writing Intersection Classification Data�[0m
[info] ok, after 1.86455s�[0m
[info] Writing Turns and Lane Data...�[0m
[info] ok, after 1.01208s�[0m
[info] Saving edge-based node weights to file.�[0m
[info] Done writing. (1.33172)�[0m
[info] Computing strictly connected components ...�[0m
[info] Found 60347 SCC (4 large, 60343 small)�[0m
[info] SCC run took: 8.73105s�[0m
[info] Building r-tree ...�[0m
[info] Constructing r-tree of 38847811 segments build on-top of 37134908 coordinates�[0m
[info] finished r-tree construction in 19.565 seconds�[0m
[info] Writing edge-based-graph edges ... �[0m
[info] ok, after 2.99117s�[0m
[info] Processed 22050874 edges�[0m
[info] Expansion: 67467 nodes/sec and 20006 edges/sec�[0m
[info] To prepare the data for routing, run: ./osrm-contract "D:\newmap_build\osrm-backend\osmdata\china-latest.osrm"�[0m
[info] RAM: peak bytes used: <not implemented on Windows>�[0m
D:\newmap_build\osrm-backend\build\Release>osrm-partition D:\newmap_build\osrm-backend\osmdata\china-latest.osrm
[info] Computing recursive bisection�[0m
[info] Loaded compressed node based graph: 12645330 edges, 37134908 nodes�[0m
[info] running partition: 128 1.2 0.25 10 1000 # max_cell_size balance boundary cuts small_component_size�[0m
[info] Found 32547752 SCC (3 large, 32547749 small)�[0m
[info] SCC run took: 21.3511s�[0m
[info] Full bisection done in 630.834s�[0m
[info] Loaded node based graph to edge based graph mapping�[0m
[info] Loaded edge based graph for mapping partition ids: 44068296 edges, 11011881 nodes�[0m
[info] Fixed 4351 unconnected nodes�[0m
[info] Edge-based-graph annotation:�[0m
[info] level 1 #cells 54189 bit size 16�[0m
[info] level 2 #cells 4099 bit size 13�[0m
[info] level 3 #cells 261 bit size 9�[0m
[info] level 4 #cells 9 bit size 4�[0m
[info] Renumbered data in 56.3506 seconds�[0m
[info] MultiLevelPartition constructed in 6.80561 seconds�[0m
[info] CellStorage constructed in 13.1338 seconds�[0m
[info] MLD data writing took 8.88436 seconds�[0m
[info] Cells statistics per level�[0m
[info] Level 1 #cells 54189 #boundary nodes 1219272, sources: avg. 14, destinations: avg. 20, entries: 20108550 (160868400 bytes)�[0m
[info] Level 2 #cells 4099 #boundary nodes 206067, sources: avg. 33, destinations: avg. 43, entries: 7121596 (56972768 bytes)�[0m
[info] Level 3 #cells 0 #boundary nodes 0, sources: avg. 0, destinations: avg. 0, entries: 0 (0 bytes)�[0m
[info] Level 4 #cells 0 #boundary nodes 0, sources: avg. 0, destinations: avg. 0, entries: 0 (0 bytes)�[0m
[info] Bisection took 876.08 seconds.�[0m
[info] RAM: peak bytes used: <not implemented on Windows>�[0m
D:\newmap_build\osrm-backend\build\Release>osrm-customize D:\newmap_build\osrm-backend\osmdata\china-latest.osrm
[info] Loaded edge based graph: 44068296 edges, 11011881 nodes�[0m
[info] Loading partition data took 114.343 seconds�[0m
[info] Cells customization took 167.473 seconds�[0m
[info] Cells statistics per level�[0m
[info] Level 1 #cells 54189 #boundary nodes 1219272, sources: avg. 14, destinations: avg. 20, entries: 20108550 (160868400 bytes)�[0m
[info] Level 2 #cells 4099 #boundary nodes 206067, sources: avg. 33, destinations: avg. 43, entries: 7121596 (56972768 bytes)�[0m
[info] Level 3 #cells 0 #boundary nodes 0, sources: avg. 0, destinations: avg. 0, entries: 0 (0 bytes)�[0m
[info] Level 4 #cells 0 #boundary nodes 0, sources: avg. 0, destinations: avg. 0, entries: 0 (0 bytes)�[0m
[info] Unreachable nodes statistics per level�[0m
�[33m[warn] Level 1 unreachable boundary nodes per cell: 0.00699404 sources, 0.00350625 destinations�[0m
�[33m[warn] Level 2 unreachable boundary nodes per cell: 0.0243962 sources, 0.00951452 destinations�[0m
[info] Unreachable nodes statistics per level�[0m
�[33m[warn] Level 1 unreachable boundary nodes per cell: 0.0651424 sources, 0.0515787 destinations�[0m
�[33m[warn] Level 2 unreachable boundary nodes per cell: 0.377409 sources, 0.295194 destinations�[0m
[info] Unreachable nodes statistics per level�[0m
�[33m[warn] Level 1 unreachable boundary nodes per cell: 0.592537 sources, 0.394951 destinations�[0m
�[33m[warn] Level 2 unreachable boundary nodes per cell: 3.33935 sources, 2.08441 destinations�[0m
[info] Unreachable nodes statistics per level�[0m
�[33m[warn] Level 1 unreachable boundary nodes per cell: 0.0102973 sources, 0.00839654 destinations�[0m
�[33m[warn] Level 2 unreachable boundary nodes per cell: 0.0502562 sources, 0.044645 destinations�[0m
[info] MLD customization writing took 16.8711 seconds�[0m
[info] Graph writing took 70.2627 seconds�[0m
[info] RAM: peak bytes used: <not implemented on Windows>�[0m
example.cpp code here:
int main(int argc, const char *argv[])
{
TIMER_START(run);
/*if (argc < 2)
{
std::cerr << "Usage: " << argv[0] << " data.osrm\n";
return EXIT_FAILURE;
}*/
using namespace osrm;
// Configure based on a .osrm base path, and no datasets in shared mem from osrm-datastore
EngineConfig config;
config.storage_config = {"D:/newmap_build/osrm-backend/osmdata/china-latest.osrm"};
config.use_shared_memory = false;
// We support two routing speed up techniques:
// - Contraction Hierarchies (CH): requires extract+contract pre-processing
// - Multi-Level Dijkstra (MLD): requires extract+partition+customize pre-processing
//
//config.algorithm = EngineConfig::Algorithm::CH;
config.algorithm = EngineConfig::Algorithm::MLD;
// Routing machine with several services (such as Route, Table, Nearest, Trip, Match)
const OSRM osrm{config};
// The following shows how to use the Route service; configure this service
RouteParameters params;
params.geometries = osrm::engine::api::RouteParameters::GeometriesType::GeoJSON;
// Route in monaco
params.coordinates.push_back(
{util::FloatLongitude{125.501}, util::FloatLatitude{45.796}});
params.coordinates.push_back(
{util::FloatLongitude{119.304}, util::FloatLatitude{40.064}});
// Response is in JSON format
engine::api::ResultT result = json::Object();
// Execute routing request, this does the heavy lifting
const auto status = osrm.Route(params, result);
auto &json_result = result.get<json::Object>();
std::vector<char> out;
util::json::render(out, json_result);
std::string output(out.begin(), out.end());
std::cout << output << std::endl;
if (status == Status::Ok)
{
auto &routes = json_result.values["routes"].get<json::Array>();
// Let's just use the first route
auto &route = routes.values.at(0).get<json::Object>();
const auto distance = route.values["distance"].get<json::Number>().value;
const auto duration = route.values["duration"].get<json::Number>().value;
// Warn users if extract does not contain the default coordinates from above
if (distance == 0 || duration == 0)
{
std::cout << "Note: distance or duration is zero. ";
std::cout << "You are probably doing a query outside of the OSM extract.\n\n";
}
std::cout << "Distance: " << distance << " meter\n";
std::cout << "Duration: " << duration << " seconds\n";
TIMER_STOP(run);
std::cout << "find route took " << TIMER_SEC(run) << " seconds";
return EXIT_SUCCESS;
}
else if (status == Status::Error)
{
const auto code = json_result.values["code"].get<json::String>().value;
const auto message = json_result.values["message"].get<json::String>().value;
std::cout << "Code: " << code << "\n";
std::cout << "Message: " << code << "\n";
TIMER_STOP(run);
std::cout << "find route took " << TIMER_SEC(run) << " seconds";
return EXIT_FAILURE;
}
}
the MLD algorithm running result：
{"code":"NoRoute","message":"No route found between points"}
Code: NoRoute
Message: NoRoute