diff options
author | Lev Dragunov <l.dragunov@corp.mail.ru> | 2015-04-22 13:35:40 +0300 |
---|---|---|
committer | Alex Zolotarev <alex@maps.me> | 2015-09-23 02:47:24 +0300 |
commit | ae2e3966d1742bb0376d35d8603564cd101b62de (patch) | |
tree | e8485df083fdc9ac05fbd321ed58de5244b2baf4 /3party/osrm | |
parent | 5ac42bd3a1e5eaafdcb29e66bd569583a2210f45 (diff) |
Our fixes to OSRM
Diffstat (limited to '3party/osrm')
36 files changed, 1359 insertions, 272 deletions
diff --git a/3party/osrm/osrm-backend/CMakeLists.txt b/3party/osrm/osrm-backend/CMakeLists.txt index 503171a599..cf671d6345 100755 --- a/3party/osrm/osrm-backend/CMakeLists.txt +++ b/3party/osrm/osrm-backend/CMakeLists.txt @@ -11,6 +11,12 @@ set(CMAKE_EXPORT_COMPILE_COMMANDS ON) include(CheckCXXCompilerFlag) include(FindPackageHandleStandardArgs) +set(OMIM_STORAGE_PATH "../../../storage/") +set(OMIM_DEBUG_PATH "${CMAKE_CURRENT_SOURCE_DIR}/../../../../omim-build-debug/out/debug") +set(OMIM_RELEASE_PATH "${CMAKE_CURRENT_SOURCE_DIR}/../../../../omim-build-release/out/release") + +set (CMAKE_RUNTIME_OUTPUT_DIRECTORY ${CMAKE_BINARY_DIR}) + list(APPEND CMAKE_MODULE_PATH "${CMAKE_CURRENT_SOURCE_DIR}/cmake") include(GetGitRevisionDescription) git_describe(GIT_DESCRIPTION) @@ -31,9 +37,11 @@ option(ENABLE_JSON_LOGGING "Adds additional JSON debug logging to the response" option(WITH_TOOLS "Build OSRM tools" OFF) option(BUILD_TOOLS "Build OSRM tools" OFF) +include_directories(${OMIM_STORAGE_PATH}/../) include_directories(${CMAKE_CURRENT_SOURCE_DIR}/include/) include_directories(${CMAKE_CURRENT_SOURCE_DIR}/third_party/) include_directories(${CMAKE_CURRENT_SOURCE_DIR}/third_party/libosmium/include/) +include_directories(${CMAKE_CURRENT_SOURCE_DIR}/../../jansson/src/) add_custom_target(FingerPrintConfigure ALL ${CMAKE_COMMAND} -DSOURCE_DIR=${CMAKE_SOURCE_DIR} @@ -41,16 +49,14 @@ add_custom_target(FingerPrintConfigure ALL COMMENT "Configuring revision fingerprint" VERBATIM) -add_custom_target(tests DEPENDS datastructure-tests algorithm-tests) -add_custom_target(benchmarks DEPENDS rtree-bench) - -set(BOOST_COMPONENTS date_time filesystem iostreams program_options regex system thread unit_test_framework) +set(BOOST_COMPONENTS date_time filesystem iostreams program_options regex system thread ) configure_file( ${CMAKE_CURRENT_SOURCE_DIR}/util/git_sha.cpp.in ${CMAKE_CURRENT_SOURCE_DIR}/util/git_sha.cpp ) file(GLOB ExtractorGlob extractor/*.cpp) +file(GLOB ExtractorGlobH extractor/*.h) file(GLOB ImporterGlob data_structures/import_edge.cpp data_structures/external_memory_node.cpp) add_library(IMPORT OBJECT ${ImporterGlob}) add_library(LOGGER OBJECT util/simple_logger.cpp) @@ -69,6 +75,7 @@ set(PrepareSources prepare.cpp ${PrepareGlob}) add_executable(osrm-prepare ${PrepareSources} $<TARGET_OBJECTS:ANGLE> $<TARGET_OBJECTS:FINGERPRINT> $<TARGET_OBJECTS:GITDESCRIPTION> $<TARGET_OBJECTS:COORDINATE> $<TARGET_OBJECTS:IMPORT> $<TARGET_OBJECTS:LOGGER> $<TARGET_OBJECTS:RESTRICTION> $<TARGET_OBJECTS:EXCEPTION> $<TARGET_OBJECTS:MERCATOR>) file(GLOB ServerGlob server/*.cpp) +file(GLOB RoutingAlgs RoutingAlgorithms/*.h) file(GLOB DescriptorGlob descriptors/*.cpp) file(GLOB DatastructureGlob data_structures/search_engine_data.cpp data_structures/route_parameters.cpp util/bearing.cpp) list(REMOVE_ITEM DatastructureGlob data_structures/Coordinate.cpp) @@ -76,9 +83,12 @@ file(GLOB CoordinateGlob data_structures/coordinate*.cpp) file(GLOB AlgorithmGlob algorithms/*.cpp) file(GLOB HttpGlob server/http/*.cpp) file(GLOB LibOSRMGlob library/*.cpp) -file(GLOB DataStructureTestsGlob unit_tests/data_structures/*.cpp data_structures/hilbert_value.cpp) file(GLOB AlgorithmTestsGlob unit_tests/algorithms/*.cpp) +file(GLOB MapsMeSources mapsme/*.cpp) +file(GLOB MapsMeHeaders mapsme/*.h) +file(GLOB MapsMeGenerator "${OMIM_STORAGE_PATH}/country.cpp" "${OMIM_STORAGE_PATH}/country_decl.cpp" "${OMIM_STORAGE_PATH}/country_info.cpp") + set( OSRMSources ${LibOSRMGlob} @@ -86,6 +96,7 @@ set( ${DatastructureGlob} ${AlgorithmGlob} ${HttpGlob} + ${MapsMeGenerator} ) add_library(COORDINATE OBJECT ${CoordinateGlob}) @@ -99,13 +110,7 @@ set_target_properties(FINGERPRINT PROPERTIES LINKER_LANGUAGE CXX) add_executable(osrm-routed routed.cpp ${ServerGlob} $<TARGET_OBJECTS:EXCEPTION>) add_executable(osrm-datastore datastore.cpp $<TARGET_OBJECTS:COORDINATE> $<TARGET_OBJECTS:FINGERPRINT> $<TARGET_OBJECTS:GITDESCRIPTION> $<TARGET_OBJECTS:LOGGER> $<TARGET_OBJECTS:EXCEPTION> $<TARGET_OBJECTS:MERCATOR>) - -# Unit tests -add_executable(datastructure-tests EXCLUDE_FROM_ALL unit_tests/datastructure_tests.cpp ${DataStructureTestsGlob} $<TARGET_OBJECTS:COORDINATE> $<TARGET_OBJECTS:LOGGER> $<TARGET_OBJECTS:PHANTOMNODE> $<TARGET_OBJECTS:EXCEPTION> $<TARGET_OBJECTS:MERCATOR>) -add_executable(algorithm-tests EXCLUDE_FROM_ALL unit_tests/algorithm_tests.cpp ${AlgorithmTestsGlob} $<TARGET_OBJECTS:COORDINATE> $<TARGET_OBJECTS:LOGGER> $<TARGET_OBJECTS:PHANTOMNODE> $<TARGET_OBJECTS:EXCEPTION>) - -# Benchmarks -add_executable(rtree-bench EXCLUDE_FROM_ALL benchmarks/static_rtree.cpp $<TARGET_OBJECTS:COORDINATE> $<TARGET_OBJECTS:LOGGER> $<TARGET_OBJECTS:PHANTOMNODE> $<TARGET_OBJECTS:EXCEPTION> $<TARGET_OBJECTS:MERCATOR>) +add_executable(osrm-mapsme ${MapsMeSources} ${MapsMeHeaders} "${CMAKE_SOURCE_DIR}/../../succinct/rs_bit_vector.cpp") # Check the release mode if(NOT CMAKE_BUILD_TYPE MATCHES Debug) @@ -125,8 +130,8 @@ if(CMAKE_BUILD_TYPE MATCHES Release) set(LTO_FLAGS "") check_cxx_compiler_flag("-flto" LTO_AVAILABLE) if(LTO_AVAILABLE) - set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -flto") - set(CHECK_LTO_SRC "int main(){return 0;}") + #set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -flto") + #set(CHECK_LTO_SRC "int main(){return 0;}") check_cxx_source_compiles("${CHECK_LTO_SRC}" LTO_WORKS) if(LTO_WORKS) message(STATUS "LTO working") @@ -145,15 +150,11 @@ if(CMAKE_BUILD_TYPE MATCHES Release) endif() endif() -if(NOT WIN32) - add_definitions(-DBOOST_TEST_DYN_LINK) -endif() - # Configuring compilers if(${CMAKE_CXX_COMPILER_ID} STREQUAL "Clang") # using Clang # -Weverything -Wno-c++98-compat -Wno-shadow -Wno-exit-time-destructors - set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wall -Wunreachable-code -pedantic -fPIC") + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wall -Wunreachable-code -fPIC") elseif(${CMAKE_CXX_COMPILER_ID} STREQUAL "GNU") set(COLOR_FLAG "-fdiagnostics-color=auto") check_cxx_compiler_flag("-fdiagnostics-color=auto" HAS_COLOR_FLAG) @@ -161,11 +162,12 @@ elseif(${CMAKE_CXX_COMPILER_ID} STREQUAL "GNU") set(COLOR_FLAG "") endif() # using GCC - set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wall -pedantic -fPIC ${COLOR_FLAG}") + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wall -fPIC ${COLOR_FLAG}") if(WIN32) # using mingw add_definitions(-D_USE_MATH_DEFINES) # define M_PI, M_1_PI etc. add_definitions(-DWIN32) set(OPTIONAL_SOCKET_LIBS ws2_32 wsock32) + set(OPTIONAL_OMP_LIB gomp) endif() elseif(${CMAKE_CXX_COMPILER_ID} STREQUAL "Intel") # using Intel C++ @@ -219,20 +221,37 @@ include_directories(${Boost_INCLUDE_DIRS}) target_link_libraries(OSRM ${Boost_LIBRARIES}) target_link_libraries(osrm-extract ${Boost_LIBRARIES}) target_link_libraries(osrm-prepare ${Boost_LIBRARIES}) -target_link_libraries(osrm-routed ${Boost_LIBRARIES} ${OPTIONAL_SOCKET_LIBS} OSRM) +target_link_libraries(osrm-routed ${Boost_LIBRARIES} ${OPTIONAL_SOCKET_LIBS} OSRM + debug "${OMIM_DEBUG_PATH}/libcoding.a" + "${OMIM_DEBUG_PATH}/libbase.a" + "${OMIM_DEBUG_PATH}/libgeometry.a" + "${OMIM_DEBUG_PATH}/libindexer.a" + "${OMIM_DEBUG_PATH}/libjansson.a" + general "${OMIM_RELEASE_PATH}/libcoding.a" + "${OMIM_RELEASE_PATH}/libgeometry.a" + "${OMIM_RELEASE_PATH}/libindexer.a" + "${OMIM_RELEASE_PATH}/libjansson.a" + "${OMIM_RELEASE_PATH}/libbase.a" +) target_link_libraries(osrm-datastore ${Boost_LIBRARIES}) -target_link_libraries(datastructure-tests ${Boost_LIBRARIES}) -target_link_libraries(algorithm-tests ${Boost_LIBRARIES} ${OPTIONAL_SOCKET_LIBS} OSRM) -target_link_libraries(rtree-bench ${Boost_LIBRARIES}) + +target_link_libraries(osrm-mapsme ${Boost_LIBRARIES} OSRM + debug "${OMIM_DEBUG_PATH}/libcoding.a" + "${OMIM_DEBUG_PATH}/libbase.a" + "${OMIM_DEBUG_PATH}/librouting.a" + "${OMIM_DEBUG_PATH}/libgeometry.a" + "${OMIM_DEBUG_PATH}/libindexer.a" + general "${OMIM_RELEASE_PATH}/libcoding.a" + "${OMIM_RELEASE_PATH}/libbase.a" + "${OMIM_RELEASE_PATH}/librouting.a" + "${OMIM_RELEASE_PATH}/libgeometry.a" + "${OMIM_RELEASE_PATH}/libindexer.a") find_package(Threads REQUIRED) -target_link_libraries(osrm-extract ${CMAKE_THREAD_LIBS_INIT}) +target_link_libraries(osrm-extract ${CMAKE_THREAD_LIBS_INIT} ${OPTIONAL_OMP_LIB}) target_link_libraries(osrm-datastore ${CMAKE_THREAD_LIBS_INIT}) -target_link_libraries(osrm-prepare ${CMAKE_THREAD_LIBS_INIT}) +#target_link_libraries(osrm-prepare ${CMAKE_THREAD_LIBS_INIT}) target_link_libraries(OSRM ${CMAKE_THREAD_LIBS_INIT}) -target_link_libraries(datastructure-tests ${CMAKE_THREAD_LIBS_INIT}) -target_link_libraries(algorithm-tests ${CMAKE_THREAD_LIBS_INIT}) -target_link_libraries(rtree-bench ${CMAKE_THREAD_LIBS_INIT}) find_package(TBB REQUIRED) if(WIN32 AND CMAKE_BUILD_TYPE MATCHES Debug) @@ -242,9 +261,6 @@ target_link_libraries(osrm-datastore ${TBB_LIBRARIES}) target_link_libraries(osrm-extract ${TBB_LIBRARIES}) target_link_libraries(osrm-prepare ${TBB_LIBRARIES}) target_link_libraries(osrm-routed ${TBB_LIBRARIES}) -target_link_libraries(datastructure-tests ${TBB_LIBRARIES}) -target_link_libraries(algorithm-tests ${TBB_LIBRARIES}) -target_link_libraries(rtree-bench ${TBB_LIBRARIES}) include_directories(${TBB_INCLUDE_DIR}) find_package( Luabind REQUIRED ) @@ -318,28 +334,9 @@ if(WITH_TOOLS OR BUILD_TOOLS) else() message(FATAL_ERROR "libgdal and/or development headers not found") endif() - add_executable(osrm-cli tools/simpleclient.cpp $<TARGET_OBJECTS:EXCEPTION> $<TARGET_OBJECTS:LOGGER> $<TARGET_OBJECTS:COORDINATE>) - target_link_libraries(osrm-cli ${Boost_LIBRARIES} ${OPTIONAL_SOCKET_LIBS} OSRM) - target_link_libraries(osrm-cli ${TBB_LIBRARIES}) - add_executable(osrm-io-benchmark tools/io-benchmark.cpp $<TARGET_OBJECTS:EXCEPTION> $<TARGET_OBJECTS:GITDESCRIPTION> $<TARGET_OBJECTS:LOGGER>) - target_link_libraries(osrm-io-benchmark ${Boost_LIBRARIES}) - add_executable(osrm-unlock-all tools/unlock_all_mutexes.cpp $<TARGET_OBJECTS:GITDESCRIPTION> $<TARGET_OBJECTS:LOGGER> $<TARGET_OBJECTS:EXCEPTION>) - target_link_libraries(osrm-unlock-all ${Boost_LIBRARIES} ${CMAKE_THREAD_LIBS_INIT}) - if(UNIX AND NOT APPLE) + if(UNIX AND NOT APPLE) target_link_libraries(osrm-unlock-all rt) endif() - add_executable(osrm-check-hsgr tools/check-hsgr.cpp $<TARGET_OBJECTS:FINGERPRINT> $<TARGET_OBJECTS:EXCEPTION> $<TARGET_OBJECTS:LOGGER>) - target_link_libraries(osrm-check-hsgr ${Boost_LIBRARIES}) - add_executable(osrm-springclean tools/springclean.cpp $<TARGET_OBJECTS:FINGERPRINT> $<TARGET_OBJECTS:LOGGER> $<TARGET_OBJECTS:GITDESCRIPTION> $<TARGET_OBJECTS:EXCEPTION>) - target_link_libraries(osrm-springclean ${Boost_LIBRARIES}) - add_executable(osrm-graph-compare tools/graph_compare.cpp $<TARGET_OBJECTS:FINGERPRINT> $<TARGET_OBJECTS:IMPORT> $<TARGET_OBJECTS:COORDINATE> $<TARGET_OBJECTS:LOGGER> $<TARGET_OBJECTS:RESTRICTION> $<TARGET_OBJECTS:EXCEPTION> $<TARGET_OBJECTS:MERCATOR>) - target_link_libraries(osrm-graph-compare ${Boost_LIBRARIES} ${TBB_LIBRARIES}) - - install(TARGETS osrm-cli DESTINATION bin) - install(TARGETS osrm-io-benchmark DESTINATION bin) - install(TARGETS osrm-unlock-all DESTINATION bin) - install(TARGETS osrm-check-hsgr DESTINATION bin) - install(TARGETS osrm-springclean DESTINATION bin) endif() file(GLOB InstallGlob include/osrm/*.hpp library/osrm.hpp) @@ -353,13 +350,6 @@ set_property(TARGET osrm-prepare PROPERTY INSTALL_RPATH_USE_LINK_PATH TRUE) set_property(TARGET osrm-datastore PROPERTY INSTALL_RPATH_USE_LINK_PATH TRUE) set_property(TARGET osrm-routed PROPERTY INSTALL_RPATH_USE_LINK_PATH TRUE) -install(FILES ${InstallGlob} DESTINATION include/osrm) -install(FILES ${VariantGlob} DESTINATION include/variant) -install(TARGETS osrm-extract DESTINATION bin) -install(TARGETS osrm-prepare DESTINATION bin) -install(TARGETS osrm-datastore DESTINATION bin) -install(TARGETS osrm-routed DESTINATION bin) -install(TARGETS OSRM DESTINATION lib) list(GET Boost_LIBRARIES 1 BOOST_LIBRARY_FIRST) get_filename_component(BOOST_LIBRARY_LISTING "${BOOST_LIBRARY_FIRST}" PATH) set(BOOST_LIBRARY_LISTING "-L${BOOST_LIBRARY_LISTING}") diff --git a/3party/osrm/osrm-backend/contractor/edge_based_graph_factory.cpp b/3party/osrm/osrm-backend/contractor/edge_based_graph_factory.cpp index 268bb9f8d0..4d6d0156cc 100755 --- a/3party/osrm/osrm-backend/contractor/edge_based_graph_factory.cpp +++ b/3party/osrm/osrm-backend/contractor/edge_based_graph_factory.cpp @@ -42,6 +42,7 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. EdgeBasedGraphFactory::EdgeBasedGraphFactory( const std::shared_ptr<NodeBasedDynamicGraph> &node_based_graph, + const std::shared_ptr<NodeBasedDynamicGraph> &node_based_graph_origin, std::unique_ptr<RestrictionMap> restriction_map, std::vector<NodeID> &barrier_node_list, std::vector<NodeID> &traffic_light_node_list, @@ -50,6 +51,7 @@ EdgeBasedGraphFactory::EdgeBasedGraphFactory( : speed_profile(speed_profile), m_number_of_edge_based_nodes(std::numeric_limits<unsigned>::max()), m_node_info_list(node_info_list), m_node_based_graph(node_based_graph), + m_node_based_graph_origin(node_based_graph_origin), m_restriction_map(std::move(restriction_map)), max_id(0), removed_node_count(0) { // insert into unordered sets for fast lookup @@ -77,6 +79,11 @@ void EdgeBasedGraphFactory::GetEdgeBasedNodes(std::vector<EdgeBasedNode> &nodes) nodes.swap(m_edge_based_node_list); } +void EdgeBasedGraphFactory::GetEdgeBasedNodeData(osrm::NodeDataVectorT &data) +{ + data.swap(m_edge_based_node_data); +} + void EdgeBasedGraphFactory::InsertEdgeBasedNode(const NodeID node_u, const NodeID node_v, const unsigned component_id) @@ -165,6 +172,7 @@ void EdgeBasedGraphFactory::InsertEdgeBasedNode(const NodeID node_u, // build edges m_edge_based_node_list.emplace_back( + forward_data.way_id, reverse_data.way_id, forward_data.edgeBasedNodeID, reverse_data.edgeBasedNodeID, current_edge_source_coordinate_id, current_edge_target_coordinate_id, forward_data.nameID, forward_geometry[i].second, @@ -210,6 +218,7 @@ void EdgeBasedGraphFactory::InsertEdgeBasedNode(const NodeID node_u, reverse_data.edgeBasedNodeID != SPECIAL_NODEID); m_edge_based_node_list.emplace_back( + forward_data.way_id, reverse_data.way_id, forward_data.edgeBasedNodeID, reverse_data.edgeBasedNodeID, node_u, node_v, forward_data.nameID, forward_data.distance, reverse_data.distance, 0, 0, SPECIAL_EDGEID, component_id, 0, forward_data.travel_mode, reverse_data.travel_mode); @@ -250,6 +259,10 @@ void EdgeBasedGraphFactory::Run(const std::string &original_edge_data_filename, GenerateEdgeExpandedEdges(original_edge_data_filename, lua_state); TIMER_STOP(generate_edges); + TIMER_START(generate_node_data); + GenerateEdgeBasedNodeData(); + TIMER_STOP(generate_node_data); + m_geometry_compressor.SerializeInternalVector(geometry_filename); SimpleLogger().Write() << "Timing statistics for edge-expanded graph:"; @@ -257,6 +270,7 @@ void EdgeBasedGraphFactory::Run(const std::string &original_edge_data_filename, SimpleLogger().Write() << "Renumbering edges: " << TIMER_SEC(renumber) << "s"; SimpleLogger().Write() << "Generating nodes: " << TIMER_SEC(generate_nodes) << "s"; SimpleLogger().Write() << "Generating edges: " << TIMER_SEC(generate_edges) << "s"; + SimpleLogger().Write() << "Generating node data: " << TIMER_SEC(generate_node_data) << "s"; } void EdgeBasedGraphFactory::CompressGeometry() @@ -430,6 +444,105 @@ void EdgeBasedGraphFactory::RenumberEdges() m_number_of_edge_based_nodes = numbered_edges_count; } +void EdgeBasedGraphFactory::GenerateEdgeBasedNodeData() +{ + BOOST_ASSERT(m_node_based_graph->GetNumberOfNodes() == m_node_based_graph_origin->GetNumberOfNodes()); + + m_edge_based_node_data.resize(m_number_of_edge_based_nodes); + std::vector<bool> found; + found.resize(m_number_of_edge_based_nodes, false); + + for (NodeID current_node = 0; current_node < m_node_based_graph->GetNumberOfNodes(); + ++current_node) + { + for (EdgeID current_edge : m_node_based_graph->GetAdjacentEdgeRange(current_node)) + { + EdgeData & edge_data = m_node_based_graph->GetEdgeData(current_edge); + if (!edge_data.forward) + { + continue; + } + + NodeID target = m_node_based_graph->GetTarget(current_edge); + + osrm::NodeData data; + if (m_geometry_compressor.HasEntryForID(current_edge)) + { + const std::vector<GeometryCompressor::CompressedNode> & via_nodes = m_geometry_compressor.GetBucketReference(current_edge); + assert(via_nodes.size() > 0); + std::vector< std::pair< NodeID, FixedPointCoordinate > > nodes; + if (via_nodes.front().first != current_node) + nodes.emplace_back(current_node, FixedPointCoordinate(m_node_info_list[current_node].lat, m_node_info_list[current_node].lon)); + for (auto n : via_nodes) + nodes.emplace_back(n.first, FixedPointCoordinate(m_node_info_list[n.first].lat, m_node_info_list[n.first].lon)); + if (via_nodes.back().first != target) + nodes.emplace_back(target, FixedPointCoordinate(m_node_info_list[target].lat, m_node_info_list[target].lon)); + + for (uint32_t i = 1; i < nodes.size(); ++i) + { + auto n1 = nodes[i - 1]; + auto n2 = nodes[i]; + + if (n1.first == n2.first) + { + SimpleLogger().Write() << "Error: Equal values " << n1.first << " and " << n2.first; + SimpleLogger().Write() << "i: "<< i << " nodes: " << nodes.size(); + throw std::exception(); + } + + EdgeID e = m_node_based_graph_origin->FindEdge(n1.first, n2.first); + if (e == SPECIAL_EDGEID) + { + SimpleLogger().Write() << "Error: Can't find edge between nodes " << n1.first << " and " << n2.first; + continue; + } + + EdgeData &ed = m_node_based_graph_origin->GetEdgeData(e); + + data.AddSegment(ed.way_id, + m_node_info_list[n1.first].lat / COORDINATE_PRECISION, + m_node_info_list[n1.first].lon / COORDINATE_PRECISION, + m_node_info_list[n2.first].lat / COORDINATE_PRECISION, + m_node_info_list[n2.first].lon / COORDINATE_PRECISION); + } + + } else + { + data.AddSegment(edge_data.way_id, + m_node_info_list[current_node].lat / COORDINATE_PRECISION, + m_node_info_list[current_node].lon / COORDINATE_PRECISION, + m_node_info_list[target].lat / COORDINATE_PRECISION, + m_node_info_list[target].lon / COORDINATE_PRECISION); + } + + if (found[edge_data.edgeBasedNodeID]) + { + if (m_edge_based_node_data[edge_data.edgeBasedNodeID] != data) + { + std::cout << "Error!" << std::endl; + throw std::exception(); + } + } else + { + found[edge_data.edgeBasedNodeID] = true; + m_edge_based_node_data[edge_data.edgeBasedNodeID] = data; + } + } + } + + for (auto v : found) + { + if (!v) + { + std::cout << "Error2" << std::endl; + throw std::exception(); + } + } + + SimpleLogger().Write() << "Edge based node data count: " << m_edge_based_node_data.size(); +} + + /** * Creates the nodes in the edge expanded graph from edges in the node-based graph. */ diff --git a/3party/osrm/osrm-backend/contractor/edge_based_graph_factory.hpp b/3party/osrm/osrm-backend/contractor/edge_based_graph_factory.hpp index 95b65babc4..665f287bd1 100755 --- a/3party/osrm/osrm-backend/contractor/edge_based_graph_factory.hpp +++ b/3party/osrm/osrm-backend/contractor/edge_based_graph_factory.hpp @@ -39,6 +39,7 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #include "../data_structures/turn_instructions.hpp" #include "../data_structures/node_based_graph.hpp" #include "../data_structures/restriction_map.hpp" +#include "../data_structures/edge_based_node_data.hpp" #include <algorithm> #include <iosfwd> @@ -60,6 +61,7 @@ class EdgeBasedGraphFactory struct SpeedProfileProperties; explicit EdgeBasedGraphFactory(const std::shared_ptr<NodeBasedDynamicGraph> &node_based_graph, + const std::shared_ptr<NodeBasedDynamicGraph> &node_based_graph_origin, std::unique_ptr<RestrictionMap> restricion_map, std::vector<NodeID> &barrier_node_list, std::vector<NodeID> &traffic_light_node_list, @@ -74,6 +76,8 @@ class EdgeBasedGraphFactory void GetEdgeBasedNodes(std::vector<EdgeBasedNode> &nodes); + void GetEdgeBasedNodeData(osrm::NodeDataVectorT &data); + TurnInstruction AnalyzeTurn(const NodeID u, const NodeID v, const NodeID w, const double angle) const; int GetTurnPenalty(double angle, lua_State *lua_state) const; @@ -102,15 +106,18 @@ class EdgeBasedGraphFactory DeallocatingVector<EdgeBasedEdge> m_edge_based_edge_list; std::shared_ptr<NodeBasedDynamicGraph> m_node_based_graph; + std::shared_ptr<NodeBasedDynamicGraph> m_node_based_graph_origin; std::unordered_set<NodeID> m_barrier_nodes; std::unordered_set<NodeID> m_traffic_lights; std::unique_ptr<RestrictionMap> m_restriction_map; + std::vector<osrm::NodeData> m_edge_based_node_data; GeometryCompressor m_geometry_compressor; void CompressGeometry(); void RenumberEdges(); + void GenerateEdgeBasedNodeData(); void GenerateEdgeExpandedNodes(); void GenerateEdgeExpandedEdges(const std::string &original_edge_data_filename, lua_State *lua_state); diff --git a/3party/osrm/osrm-backend/contractor/processing_chain.cpp b/3party/osrm/osrm-backend/contractor/processing_chain.cpp index ccff7fd093..d05de7a64d 100755 --- a/3party/osrm/osrm-backend/contractor/processing_chain.cpp +++ b/3party/osrm/osrm-backend/contractor/processing_chain.cpp @@ -117,6 +117,7 @@ int Prepare::Process(int argc, char *argv[]) graph_out = input_path.string() + ".hsgr"; rtree_nodes_path = input_path.string() + ".ramIndex"; rtree_leafs_path = input_path.string() + ".fileIndex"; + node_data_filename = input_path.string() + ".nodeData"; /*** Setup Scripting Environment ***/ // Create a new lua state @@ -135,7 +136,7 @@ int Prepare::Process(int argc, char *argv[]) #ifdef WIN32 #pragma message("Memory consumption on Windows can be higher due to different bit packing") #else - static_assert(sizeof(ImportEdge) == 20, + static_assert(sizeof(ImportEdge) == 24, "changing ImportEdge type has influence on memory consumption!"); #endif NodeID number_of_node_based_nodes = readBinaryOSRMGraphFromStream( @@ -356,9 +357,10 @@ bool Prepare::ParseArguments(int argc, char *argv[]) // hidden options, will be allowed both on command line and in config file, but will not be // shown to the user + std::string string_input_path; boost::program_options::options_description hidden_options("Hidden options"); hidden_options.add_options()( - "input,i", boost::program_options::value<boost::filesystem::path>(&input_path), + "input,i", boost::program_options::value<std::string>(&string_input_path), "Input file in .osm, .osm.bz2 or .osm.pbf format"); // positional option @@ -417,6 +419,7 @@ bool Prepare::ParseArguments(int argc, char *argv[]) return false; } + input_path = boost::filesystem::path(string_input_path); return true; } @@ -501,8 +504,12 @@ Prepare::BuildEdgeExpandedGraph(lua_State *lua_state, NodeBasedDynamicGraphFromImportEdges(number_of_node_based_nodes, edge_list); std::unique_ptr<RestrictionMap> restriction_map = osrm::make_unique<RestrictionMap>(restriction_list); + + std::shared_ptr<NodeBasedDynamicGraph> node_based_graph_origin = + NodeBasedDynamicGraphFromImportEdges(number_of_node_based_nodes, edge_list); + std::shared_ptr<EdgeBasedGraphFactory> edge_based_graph_factory = - std::make_shared<EdgeBasedGraphFactory>(node_based_graph, std::move(restriction_map), + std::make_shared<EdgeBasedGraphFactory>(node_based_graph, node_based_graph_origin, std::move(restriction_map), barrier_node_list, traffic_light_list, internal_to_external_node_map, speed_profile); edge_list.clear(); @@ -529,6 +536,14 @@ Prepare::BuildEdgeExpandedGraph(lua_State *lua_state, edge_based_graph_factory->GetEdgeBasedEdges(edge_based_edge_list); edge_based_graph_factory->GetEdgeBasedNodes(node_based_edge_list); + // serialize node data + osrm::NodeDataVectorT data; + edge_based_graph_factory->GetEdgeBasedNodeData(data); + + SimpleLogger().Write() << "Serialize node data"; + + osrm::SaveNodeDataToFile(node_data_filename, data); + edge_based_graph_factory.reset(); node_based_graph.reset(); @@ -559,9 +574,9 @@ void Prepare::WriteNodeMapping() Saves info to files: '.ramIndex' and '.fileIndex'. */ -void Prepare::BuildRTree(std::vector<EdgeBasedNode> &node_based_edge_list) +void Prepare::BuildRTree(std::vector<EdgeBasedNode> &node_based_node_list) { SimpleLogger().Write() << "building r-tree ..."; - StaticRTree<EdgeBasedNode>(node_based_edge_list, rtree_nodes_path.c_str(), + StaticRTree<EdgeBasedNode>(node_based_node_list, rtree_nodes_path.c_str(), rtree_leafs_path.c_str(), internal_to_external_node_map); } diff --git a/3party/osrm/osrm-backend/contractor/processing_chain.hpp b/3party/osrm/osrm-backend/contractor/processing_chain.hpp index 933213a4c0..088bf3e04c 100755 --- a/3party/osrm/osrm-backend/contractor/processing_chain.hpp +++ b/3party/osrm/osrm-backend/contractor/processing_chain.hpp @@ -90,6 +90,7 @@ class Prepare std::string graph_out; std::string rtree_nodes_path; std::string rtree_leafs_path; + std::string node_data_filename; }; #endif // PROCESSING_CHAIN_HPP diff --git a/3party/osrm/osrm-backend/data_structures/coordinate.cpp b/3party/osrm/osrm-backend/data_structures/coordinate.cpp index df3abe44ae..a4344c923d 100755 --- a/3party/osrm/osrm-backend/data_structures/coordinate.cpp +++ b/3party/osrm/osrm-backend/data_structures/coordinate.cpp @@ -27,14 +27,8 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #include "coordinate_calculation.hpp" -#ifndef NDEBUG -#include "../util/simple_logger.hpp" -#endif #include <osrm/coordinate.hpp> -#ifndef NDEBUG -#include <bitset> -#endif #include <iostream> #include <limits> @@ -45,20 +39,6 @@ FixedPointCoordinate::FixedPointCoordinate() FixedPointCoordinate::FixedPointCoordinate(int lat, int lon) : lat(lat), lon(lon) { -#ifndef NDEBUG - if (0 != (std::abs(lat) >> 30)) - { - std::bitset<32> y_coordinate_vector(lat); - SimpleLogger().Write(logDEBUG) << "broken lat: " << lat - << ", bits: " << y_coordinate_vector; - } - if (0 != (std::abs(lon) >> 30)) - { - std::bitset<32> x_coordinate_vector(lon); - SimpleLogger().Write(logDEBUG) << "broken lon: " << lon - << ", bits: " << x_coordinate_vector; - } -#endif } bool FixedPointCoordinate::is_valid() const diff --git a/3party/osrm/osrm-backend/data_structures/edge_based_node.hpp b/3party/osrm/osrm-backend/data_structures/edge_based_node.hpp index 72a585a139..42578f668d 100755 --- a/3party/osrm/osrm-backend/data_structures/edge_based_node.hpp +++ b/3party/osrm/osrm-backend/data_structures/edge_based_node.hpp @@ -33,14 +33,15 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #include <boost/assert.hpp> -#include <osrm/coordinate.hpp> +#include "../include/osrm/coordinate.hpp" #include <limits> struct EdgeBasedNode { EdgeBasedNode() - : forward_edge_based_node_id(SPECIAL_NODEID), reverse_edge_based_node_id(SPECIAL_NODEID), + : forward_way_id(-1), reverse_way_id(-1), + forward_edge_based_node_id(SPECIAL_NODEID), reverse_edge_based_node_id(SPECIAL_NODEID), u(SPECIAL_NODEID), v(SPECIAL_NODEID), name_id(0), forward_weight(INVALID_EDGE_WEIGHT >> 1), reverse_weight(INVALID_EDGE_WEIGHT >> 1), forward_offset(0), reverse_offset(0), packed_geometry_id(SPECIAL_EDGEID), @@ -50,7 +51,10 @@ struct EdgeBasedNode { } - explicit EdgeBasedNode(NodeID forward_edge_based_node_id, + explicit EdgeBasedNode( + unsigned forward_way_id, + unsigned reverse_way_id, + NodeID forward_edge_based_node_id, NodeID reverse_edge_based_node_id, NodeID u, NodeID v, @@ -64,7 +68,8 @@ struct EdgeBasedNode unsigned short fwd_segment_position, TravelMode forward_travel_mode, TravelMode backward_travel_mode) - : forward_edge_based_node_id(forward_edge_based_node_id), + : forward_way_id(forward_way_id), reverse_way_id(reverse_way_id), + forward_edge_based_node_id(forward_edge_based_node_id), reverse_edge_based_node_id(reverse_edge_based_node_id), u(u), v(v), name_id(name_id), forward_weight(forward_weight), reverse_weight(reverse_weight), forward_offset(forward_offset), reverse_offset(reverse_offset), @@ -104,6 +109,8 @@ struct EdgeBasedNode unsigned short fwd_segment_position; // segment id in a compressed geometry TravelMode forward_travel_mode : 4; TravelMode backward_travel_mode : 4; + unsigned forward_way_id; + unsigned reverse_way_id; }; #endif // EDGE_BASED_NODE_HPP diff --git a/3party/osrm/osrm-backend/data_structures/edge_based_node_data.hpp b/3party/osrm/osrm-backend/data_structures/edge_based_node_data.hpp new file mode 100644 index 0000000000..dbcadfe01b --- /dev/null +++ b/3party/osrm/osrm-backend/data_structures/edge_based_node_data.hpp @@ -0,0 +1,123 @@ +#pragma once + +#include <stdint.h> +#include <vector> +#include <fstream> + + +namespace osrm +{ + +struct NodeData +{ +#pragma pack (push, 1) + struct SegmentInfo + { + uint64_t wayId; + double lat1, lon1, lat2, lon2; + + SegmentInfo() + : wayId(-1), lat1(-10000), lon1(-10000), lat2(-10000), lon2(-10000) + { + } + + SegmentInfo(uint64_t wayId, double lat1, double lon1, double lat2, double lon2) + : wayId(wayId), lat1(lat1), lon1(lon1), lat2(lat2), lon2(lon2) + { + } + + bool operator != (SegmentInfo const & other) const + { + return wayId != other.wayId || lat1 != other.lat1 || lon1 != other.lon1 || + lat2 != other.lat2 || lon2 != other.lon2; + } + }; +#pragma pack (pop) + + typedef std::vector<SegmentInfo> SegmentInfoVectorT; + SegmentInfoVectorT m_segments; + + NodeData() + { + } + + NodeData(SegmentInfoVectorT & vec) + { + m_segments.swap(vec); + } + + bool operator == (NodeData const & other) const + { + if (m_segments.size() != other.m_segments.size()) + return false; + + for (uint32_t i = 0; i < m_segments.size(); ++i) + if (m_segments[i] != other.m_segments[i]) + return false; + + return true; + } + + bool operator != (NodeData const & other) const + { + return !(*this == other); + } + + void AddSegment(uint64_t wayId, double lat1, double lon1, double lat2, double lon2) + { + m_segments.emplace_back(wayId, lat1, lon1, lat2, lon2); + } + + void SetSegments(SegmentInfoVectorT & segments) + { + m_segments.swap(segments); + } +}; + + +typedef std::vector<NodeData> NodeDataVectorT; + +inline bool SaveNodeDataToFile(std::string const & filename, NodeDataVectorT const & data) +{ + std::ofstream stream; + stream.open(filename); + if (!stream.is_open()) + return false; + + uint32_t count = data.size(); + stream.write((char*)&count, sizeof(count)); + for (auto d : data) + { + uint32_t pc = d.m_segments.size(); + stream.write((char*)&pc, sizeof(pc)); + stream.write((char*)d.m_segments.data(), sizeof(NodeData::SegmentInfo) * pc); + } + stream.close(); + return true; +} + +inline bool LoadNodeDataFromFile(std::string const & filename, NodeDataVectorT & data) +{ + std::ifstream stream; + stream.open(filename); + if (!stream.is_open()) + return false; + + uint32_t count = 0; + stream.read((char*)&count, sizeof(count)); + for (uint32_t i = 0; i < count; ++i) + { + uint32_t pc; + stream.read((char*)&pc, sizeof(pc)); + NodeData::SegmentInfoVectorT segments; + segments.resize(pc); + stream.read((char*)segments.data(), sizeof(NodeData::SegmentInfo) * pc); + + data.emplace_back(segments); + } + stream.close(); + + return true; +} + +} diff --git a/3party/osrm/osrm-backend/data_structures/import_edge.cpp b/3party/osrm/osrm-backend/data_structures/import_edge.cpp index f41b066b1a..947ebb0546 100755 --- a/3party/osrm/osrm-backend/data_structures/import_edge.cpp +++ b/3party/osrm/osrm-backend/data_structures/import_edge.cpp @@ -47,7 +47,8 @@ bool NodeBasedEdge::operator<(const NodeBasedEdge &other) const return source < other.source; } -NodeBasedEdge::NodeBasedEdge(NodeID source, +NodeBasedEdge::NodeBasedEdge(unsigned way_id, + NodeID source, NodeID target, NodeID name_id, EdgeWeight weight, @@ -58,7 +59,7 @@ NodeBasedEdge::NodeBasedEdge(NodeID source, bool access_restricted, TravelMode travel_mode, bool is_split) - : source(source), target(target), name_id(name_id), weight(weight), forward(forward), + : way_id(way_id), source(source), target(target), name_id(name_id), weight(weight), forward(forward), backward(backward), roundabout(roundabout), in_tiny_cc(in_tiny_cc), access_restricted(access_restricted), is_split(is_split), travel_mode(travel_mode) { diff --git a/3party/osrm/osrm-backend/data_structures/import_edge.hpp b/3party/osrm/osrm-backend/data_structures/import_edge.hpp index f422de116f..7175bd0574 100755 --- a/3party/osrm/osrm-backend/data_structures/import_edge.hpp +++ b/3party/osrm/osrm-backend/data_structures/import_edge.hpp @@ -35,7 +35,8 @@ struct NodeBasedEdge { bool operator<(const NodeBasedEdge &e) const; - explicit NodeBasedEdge(NodeID source, + explicit NodeBasedEdge(unsigned way_id, + NodeID source, NodeID target, NodeID name_id, EdgeWeight weight, @@ -47,6 +48,7 @@ struct NodeBasedEdge TravelMode travel_mode, bool is_split); + unsigned way_id; NodeID source; NodeID target; NodeID name_id; diff --git a/3party/osrm/osrm-backend/data_structures/node_based_graph.hpp b/3party/osrm/osrm-backend/data_structures/node_based_graph.hpp index 54e07a7ec6..b074d2dd38 100755 --- a/3party/osrm/osrm-backend/data_structures/node_based_graph.hpp +++ b/3party/osrm/osrm-backend/data_structures/node_based_graph.hpp @@ -39,13 +39,14 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. struct NodeBasedEdgeData { NodeBasedEdgeData() - : distance(INVALID_EDGE_WEIGHT), edgeBasedNodeID(SPECIAL_NODEID), + : way_id(-1), distance(INVALID_EDGE_WEIGHT), edgeBasedNodeID(SPECIAL_NODEID), nameID(std::numeric_limits<unsigned>::max()), isAccessRestricted(false), shortcut(false), forward(false), backward(false), roundabout(false), ignore_in_grid(false), travel_mode(TRAVEL_MODE_INACCESSIBLE) { } + unsigned way_id; int distance; unsigned edgeBasedNodeID; unsigned nameID; @@ -85,7 +86,7 @@ using SimpleNodeBasedDynamicGraph = DynamicGraph<SimpleEdgeData>; inline std::shared_ptr<NodeBasedDynamicGraph> NodeBasedDynamicGraphFromImportEdges(int number_of_nodes, std::vector<ImportEdge> &input_edge_list) { - static_assert(sizeof(NodeBasedEdgeData) == 16, + static_assert(sizeof(NodeBasedEdgeData) == 20, "changing node based edge data size changes memory consumption"); DeallocatingVector<NodeBasedDynamicGraph::InputEdge> edges_list; @@ -107,6 +108,8 @@ NodeBasedDynamicGraphFromImportEdges(int number_of_nodes, std::vector<ImportEdge edge.data.forward = import_edge.backward; } + edge.data.way_id = import_edge.way_id; + if (edge.source == edge.target) { continue; @@ -202,7 +205,7 @@ template <class SimpleEdgeT> inline std::shared_ptr<SimpleNodeBasedDynamicGraph> SimpleNodeBasedDynamicGraphFromEdges(int number_of_nodes, std::vector<SimpleEdgeT> &input_edge_list) { - static_assert(sizeof(NodeBasedEdgeData) == 16, + static_assert(sizeof(NodeBasedEdgeData) == 20, "changing node based edge data size changes memory consumption"); tbb::parallel_sort(input_edge_list.begin(), input_edge_list.end()); diff --git a/3party/osrm/osrm-backend/data_structures/phantom_node.hpp b/3party/osrm/osrm-backend/data_structures/phantom_node.hpp index b048eb7f21..2f5725d72e 100755 --- a/3party/osrm/osrm-backend/data_structures/phantom_node.hpp +++ b/3party/osrm/osrm-backend/data_structures/phantom_node.hpp @@ -31,7 +31,7 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #include "travel_mode.hpp" #include "../typedefs.h" -#include <osrm/coordinate.hpp> +#include "../include/osrm/coordinate.hpp" #include <iostream> #include <utility> diff --git a/3party/osrm/osrm-backend/data_structures/query_node.hpp b/3party/osrm/osrm-backend/data_structures/query_node.hpp index f3e9904765..54b9a2612f 100755 --- a/3party/osrm/osrm-backend/data_structures/query_node.hpp +++ b/3party/osrm/osrm-backend/data_structures/query_node.hpp @@ -32,7 +32,7 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #include <boost/assert.hpp> -#include <osrm/coordinate.hpp> +#include "../include/osrm/coordinate.hpp" #include <limits> diff --git a/3party/osrm/osrm-backend/data_structures/search_engine_data.hpp b/3party/osrm/osrm-backend/data_structures/search_engine_data.hpp index 8c1c1619e0..b63910df25 100755 --- a/3party/osrm/osrm-backend/data_structures/search_engine_data.hpp +++ b/3party/osrm/osrm-backend/data_structures/search_engine_data.hpp @@ -28,7 +28,7 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #ifndef SEARCH_ENGINE_DATA_HPP #define SEARCH_ENGINE_DATA_HPP -#include <boost/thread/tss.hpp> +#include <boost/scoped_ptr.hpp> #include "../typedefs.h" #include "binary_heap.hpp" @@ -42,7 +42,7 @@ struct HeapData struct SearchEngineData { using QueryHeap = BinaryHeap<NodeID, NodeID, int, HeapData, UnorderedMapStorage<NodeID, int>>; - using SearchEngineHeapPtr = boost::thread_specific_ptr<QueryHeap>; + using SearchEngineHeapPtr = boost::scoped_ptr<QueryHeap>; static SearchEngineHeapPtr forward_heap_1; static SearchEngineHeapPtr reverse_heap_1; diff --git a/3party/osrm/osrm-backend/data_structures/static_rtree.hpp b/3party/osrm/osrm-backend/data_structures/static_rtree.hpp index f219a64755..5822bdf724 100755 --- a/3party/osrm/osrm-backend/data_structures/static_rtree.hpp +++ b/3party/osrm/osrm-backend/data_structures/static_rtree.hpp @@ -52,9 +52,6 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #include <boost/filesystem/fstream.hpp> #include <boost/thread.hpp> -#include <tbb/parallel_for.h> -#include <tbb/parallel_sort.h> - #include <variant/variant.hpp> #include <algorithm> @@ -360,39 +357,28 @@ class StaticRTree HilbertCode get_hilbert_number; // generate auxiliary vector of hilbert-values - tbb::parallel_for( - tbb::blocked_range<uint64_t>(0, m_element_count), - [&input_data_vector, &input_wrapper_vector, &get_hilbert_number, &coordinate_list]( - const tbb::blocked_range<uint64_t> &range) - { - for (uint64_t element_counter = range.begin(); element_counter != range.end(); - ++element_counter) - { - WrappedInputElement ¤t_wrapper = input_wrapper_vector[element_counter]; - current_wrapper.m_array_index = element_counter; - - EdgeDataT const ¤t_element = input_data_vector[element_counter]; - - // Get Hilbert-Value for centroid in mercartor projection - FixedPointCoordinate current_centroid = EdgeDataT::Centroid( - FixedPointCoordinate(coordinate_list.at(current_element.u).lat, - coordinate_list.at(current_element.u).lon), - FixedPointCoordinate(coordinate_list.at(current_element.v).lat, - coordinate_list.at(current_element.v).lon)); - current_centroid.lat = - COORDINATE_PRECISION * - mercator::lat2y(current_centroid.lat / COORDINATE_PRECISION); - - current_wrapper.m_hilbert_value = get_hilbert_number(current_centroid); - } - }); + for (uint64_t element_counter = 0; element_counter != m_element_count; ++element_counter) + { + WrappedInputElement ¤t_wrapper = input_wrapper_vector[element_counter]; + current_wrapper.m_array_index = element_counter; + EdgeDataT const ¤t_element = input_data_vector[element_counter]; + // Get Hilbert-Value for centroid in mercartor projection + FixedPointCoordinate current_centroid = EdgeDataT::Centroid( + FixedPointCoordinate(coordinate_list.at(current_element.u).lat, + coordinate_list.at(current_element.u).lon), + FixedPointCoordinate(coordinate_list.at(current_element.v).lat, + coordinate_list.at(current_element.v).lon)); + current_centroid.lat = + COORDINATE_PRECISION * mercator::lat2y(current_centroid.lat / COORDINATE_PRECISION); + current_wrapper.m_hilbert_value = get_hilbert_number(current_centroid); + } // open leaf file boost::filesystem::ofstream leaf_node_file(leaf_node_filename, std::ios::binary); leaf_node_file.write((char *)&m_element_count, sizeof(uint64_t)); // sort the hilbert-value representatives - tbb::parallel_sort(input_wrapper_vector.begin(), input_wrapper_vector.end()); + sort(input_wrapper_vector.begin(), input_wrapper_vector.end()); std::vector<TreeNode> tree_nodes_in_level; // pack M elements into leaf node and write to leaf file @@ -473,20 +459,17 @@ class StaticRTree std::reverse(m_search_tree.begin(), m_search_tree.end()); uint32_t search_tree_size = m_search_tree.size(); - tbb::parallel_for(tbb::blocked_range<uint32_t>(0, search_tree_size), - [this, &search_tree_size](const tbb::blocked_range<uint32_t> &range) - { - for (uint32_t i = range.begin(); i != range.end(); ++i) - { - TreeNode ¤t_tree_node = this->m_search_tree[i]; - for (uint32_t j = 0; j < current_tree_node.child_count; ++j) - { - const uint32_t old_id = current_tree_node.children[j]; - const uint32_t new_id = search_tree_size - old_id - 1; - current_tree_node.children[j] = new_id; - } - } - }); + + for (uint32_t i = 0; i != search_tree_size; ++i) + { + TreeNode ¤t_tree_node = this->m_search_tree[i]; + for (uint32_t j = 0; j < current_tree_node.child_count; ++j) + { + const uint32_t old_id = current_tree_node.children[j]; + const uint32_t new_id = search_tree_size - old_id - 1; + current_tree_node.children[j] = new_id; + } + } // open tree file boost::filesystem::ofstream tree_node_file(tree_node_filename, std::ios::binary); @@ -660,7 +643,7 @@ class StaticRTree input_coordinate.lon / COORDINATE_PRECISION}; // upper bound pruning technique - upper_bound<float> pruning_bound(max_number_of_phantom_nodes); + osrm_algo::upper_bound<float> pruning_bound(max_number_of_phantom_nodes); // initialize queue with root element std::priority_queue<IncrementalQueryCandidate> traversal_queue; @@ -816,7 +799,7 @@ class StaticRTree input_coordinate.lon / COORDINATE_PRECISION}; // upper bound pruning technique - upper_bound<float> pruning_bound(max_number_of_phantom_nodes); + osrm_algo::upper_bound<float> pruning_bound(max_number_of_phantom_nodes); // initialize queue with root element std::priority_queue<IncrementalQueryCandidate> traversal_queue; diff --git a/3party/osrm/osrm-backend/data_structures/upper_bound.hpp b/3party/osrm/osrm-backend/data_structures/upper_bound.hpp index 80695f2c51..0de82c4070 100755 --- a/3party/osrm/osrm-backend/data_structures/upper_bound.hpp +++ b/3party/osrm/osrm-backend/data_structures/upper_bound.hpp @@ -38,6 +38,9 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. // if size > k then remove element // get() always yields a bound to the k smallest element in the stream +namespace osrm_algo +{ + template <typename key_type> class upper_bound { private: @@ -73,5 +76,5 @@ template <typename key_type> class upper_bound std::priority_queue<key_type, std::vector<key_type>, std::less<key_type>> queue; const std::size_t size; }; - +} #endif // LOWER_BOUND_HPP diff --git a/3party/osrm/osrm-backend/extractor/extraction_containers.cpp b/3party/osrm/osrm-backend/extractor/extraction_containers.cpp index 8c484eb814..ab265452bd 100755 --- a/3party/osrm/osrm-backend/extractor/extraction_containers.cpp +++ b/3party/osrm/osrm-backend/extractor/extraction_containers.cpp @@ -335,6 +335,7 @@ void ExtractionContainers::PrepareData(const std::string &output_file_name, const bool yes = true; const bool no = false; + file_out_stream.write((char *)&edge_iterator->way_id, sizeof(unsigned)); file_out_stream.write((char *)&edge_iterator->start, sizeof(unsigned)); file_out_stream.write((char *)&edge_iterator->target, sizeof(unsigned)); file_out_stream.write((char *)&integer_distance, sizeof(int)); diff --git a/3party/osrm/osrm-backend/extractor/extractor_callbacks.cpp b/3party/osrm/osrm-backend/extractor/extractor_callbacks.cpp index 224468b060..8f3b3de8ca 100755 --- a/3party/osrm/osrm-backend/extractor/extractor_callbacks.cpp +++ b/3party/osrm/osrm-backend/extractor/extractor_callbacks.cpp @@ -137,6 +137,7 @@ void ExtractorCallbacks::ProcessWay(const osmium::Way &input_way, const Extracti // SimpleLogger().Write() << "adding edge (" << first_node.ref() << "," << // last_node.ref() << "), fwd speed: " << parsed_way.forward_speed; external_memory.all_edges_list.push_back(InternalExtractorEdge( + (EdgeID)input_way.id(), first_node.ref(), last_node.ref(), ((split_edge || TRAVEL_MODE_INACCESSIBLE == parsed_way.backward_travel_mode) ? ExtractionWay::oneway @@ -181,6 +182,7 @@ void ExtractorCallbacks::ProcessWay(const osmium::Way &input_way, const Extracti // SimpleLogger().Write() << "adding edge (" << last_node.ref() << "," << // first_node.ref() << "), bwd speed: " << parsed_way.backward_speed; external_memory.all_edges_list.push_back(InternalExtractorEdge( + (EdgeID)input_way.id(), last_node.ref(), first_node.ref(), ExtractionWay::oneway, parsed_way.backward_speed, name_id, parsed_way.roundabout, parsed_way.ignore_in_grid, (0 < parsed_way.duration), parsed_way.is_access_restricted, diff --git a/3party/osrm/osrm-backend/extractor/extractor_options.cpp b/3party/osrm/osrm-backend/extractor/extractor_options.cpp index 9ae5cd4c10..23f9530880 100755 --- a/3party/osrm/osrm-backend/extractor/extractor_options.cpp +++ b/3party/osrm/osrm-backend/extractor/extractor_options.cpp @@ -59,9 +59,10 @@ ExtractorOptions::ParseArguments(int argc, char *argv[], ExtractorConfig &extrac // hidden options, will be allowed both on command line and in config file, but will not be // shown to the user + std::string string_input_path; boost::program_options::options_description hidden_options("Hidden options"); - hidden_options.add_options()("input,i", boost::program_options::value<boost::filesystem::path>( - &extractor_config.input_path), + hidden_options.add_options()("input,i", boost::program_options::value<std::string>( + &string_input_path), "Input file in .osm, .osm.bz2 or .osm.pbf format"); // positional option @@ -127,6 +128,8 @@ ExtractorOptions::ParseArguments(int argc, char *argv[], ExtractorConfig &extrac return return_code::fail; } + extractor_config.input_path = string_input_path; + return return_code::ok; } diff --git a/3party/osrm/osrm-backend/extractor/internal_extractor_edge.hpp b/3party/osrm/osrm-backend/extractor/internal_extractor_edge.hpp index 27e1af146f..852c935826 100755 --- a/3party/osrm/osrm-backend/extractor/internal_extractor_edge.hpp +++ b/3party/osrm/osrm-backend/extractor/internal_extractor_edge.hpp @@ -38,13 +38,14 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. struct InternalExtractorEdge { InternalExtractorEdge() - : start(0), target(0), speed(0), name_id(0), direction(0), is_roundabout(false), + : way_id(0), start(0), target(0), speed(0), name_id(0), direction(0), is_roundabout(false), is_in_tiny_cc(false), is_duration_set(false), is_access_restricted(false), is_split(false), travel_mode(TRAVEL_MODE_INACCESSIBLE) { } - explicit InternalExtractorEdge(NodeID start, + explicit InternalExtractorEdge(unsigned id, + NodeID start, NodeID target, short direction, double speed, @@ -55,7 +56,7 @@ struct InternalExtractorEdge bool is_access_restricted, TravelMode travel_mode, bool is_split) - : start(start), target(target), speed(speed), name_id(name_id), direction(direction), + : way_id(id), start(start), target(target), speed(speed), name_id(name_id), direction(direction), is_roundabout(is_roundabout), is_in_tiny_cc(is_in_tiny_cc), is_duration_set(is_duration_set), is_access_restricted(is_access_restricted), is_split(is_split), travel_mode(travel_mode) @@ -65,15 +66,16 @@ struct InternalExtractorEdge // necessary static util functions for stxxl's sorting static InternalExtractorEdge min_value() { - return InternalExtractorEdge(0, 0, 0, 0, 0, false, false, false, false, + return InternalExtractorEdge(0, 0, 0, 0, 0, 0, false, false, false, false, TRAVEL_MODE_INACCESSIBLE, false); } static InternalExtractorEdge max_value() { - return InternalExtractorEdge(SPECIAL_NODEID, SPECIAL_NODEID, 0, 0, 0, false, false, false, + return InternalExtractorEdge(SPECIAL_NODEID, SPECIAL_NODEID, SPECIAL_NODEID, 0, 0, 0, false, false, false, false, TRAVEL_MODE_INACCESSIBLE, false); } + unsigned way_id; NodeID start; NodeID target; double speed; diff --git a/3party/osrm/osrm-backend/library/osrm_impl.cpp b/3party/osrm/osrm-backend/library/osrm_impl.cpp index 5bb58d1749..b96c4d0a3b 100755 --- a/3party/osrm/osrm-backend/library/osrm_impl.cpp +++ b/3party/osrm/osrm-backend/library/osrm_impl.cpp @@ -42,6 +42,7 @@ class named_mutex; #include "../plugins/nearest.hpp" #include "../plugins/timestamp.hpp" #include "../plugins/viaroute.hpp" +#include "../plugins/MapsMePlugin.hpp" #include "../plugins/match.hpp" #include "../server/data_structures/datafacade_base.hpp" #include "../server/data_structures/internal_datafacade.hpp" @@ -86,6 +87,8 @@ OSRM_impl::OSRM_impl(libosrm_config &lib_config) query_data_facade, lib_config.max_locations_map_matching)); RegisterPlugin(new TimestampPlugin<BaseDataFacade<QueryEdge::EdgeData>>(query_data_facade)); RegisterPlugin(new ViaRoutePlugin<BaseDataFacade<QueryEdge::EdgeData>>(query_data_facade)); + //RegisterPlugin(new MapsMePlugin<BaseDataFacade<QueryEdge::EdgeData>>( + // query_data_facade, server_paths["borders"].string(), server_paths["enodesdata"].string())); } OSRM_impl::~OSRM_impl() diff --git a/3party/osrm/osrm-backend/mapsme/converter.cpp b/3party/osrm/osrm-backend/mapsme/converter.cpp new file mode 100644 index 0000000000..2062f2d5b0 --- /dev/null +++ b/3party/osrm/osrm-backend/mapsme/converter.cpp @@ -0,0 +1,389 @@ +#include "converter.hpp" + +#include "../server/data_structures/internal_datafacade.hpp" + +#include <iostream> + + +#include "../../../../base/bits.hpp" +#include "../../../../base/logging.hpp" +#include "../../../../base/scope_guard.hpp" + +#include "../../../../coding/matrix_traversal.hpp" +#include "../../../../coding/internal/file_data.hpp" + +#include "../../../../routing/osrm_data_facade.hpp" + +#include "../../../succinct/elias_fano.hpp" +#include "../../../succinct/elias_fano_compressed_list.hpp" +#include "../../../succinct/gamma_vector.hpp" +#include "../../../succinct/rs_bit_vector.hpp" +#include "../../../succinct/mapper.hpp" + + +namespace mapsme +{ + +typedef pair<NodeID, QueryEdge::EdgeData> EdgeOsrmT; + +struct EdgeLess +{ + bool operator () (EdgeOsrmT const & e1, EdgeOsrmT const & e2) const + { + if (e1.first != e2.first) + return e1.first < e2.first; + + QueryEdge::EdgeData const & d1 = e1.second; + QueryEdge::EdgeData const & d2 = e2.second; + + if (d1.distance != d2.distance) + return d1.distance < d2.distance; + + if (d1.shortcut != d2.shortcut) + return d1.shortcut < d2.shortcut; + + if (d1.forward != d2.forward) + return d1.forward < d2.forward; + + if (d1.backward != d2.backward) + return e1.second.backward < d2.backward; + + if (d1.id != d2.id) + return d1.id < d2.id; + + return false; + } +}; + +void PrintStatus(bool b) +{ + std::cout << (b ? "[Ok]" : "[Fail]") << std::endl; +} + +string EdgeDataToString(EdgeOsrmT const & d) +{ + stringstream ss; + ss << "[" << d.first << ", " << d.second.distance << ", " << d.second.shortcut << ", " << d.second.forward << ", " + << d.second.backward << ", " << d.second.id << "]"; + return ss.str(); +} + + + +void GenerateRoutingIndex(const std::string & fPath) +{ + ServerPaths server_paths; + + server_paths["hsgrdata"] = boost::filesystem::path(fPath + ".hsgr"); + server_paths["ramindex"] = boost::filesystem::path(fPath + ".ramIndex"); + server_paths["fileindex"] = boost::filesystem::path(fPath + ".fileIndex"); + server_paths["geometries"] = boost::filesystem::path(fPath + ".geometry"); + server_paths["nodesdata"] = boost::filesystem::path(fPath + ".nodes"); + server_paths["edgesdata"] = boost::filesystem::path(fPath + ".edges"); + server_paths["namesdata"] = boost::filesystem::path(fPath + ".names"); + server_paths["timestamp"] = boost::filesystem::path(fPath + ".timestamp"); + + std::cout << "Create internal data facade for file: " << fPath << "..."; + InternalDataFacade<QueryEdge::EdgeData> facade(server_paths); + PrintStatus(true); + + uint32_t const nodeCount = facade.GetNumberOfNodes(); + + std::vector<uint64_t> edges; + std::vector<uint32_t> edgesData; + std::vector<bool> shortcuts; + std::vector<uint64_t> edgeId; + + std::cout << "Repack graph..." << std::endl; + + typedef pair<uint64_t, QueryEdge::EdgeData> EdgeInfoT; + typedef vector<EdgeInfoT> EdgeInfoVecT; + + uint64_t copiedEdges = 0, ignoredEdges = 0; + for (uint32_t node = 0; node < nodeCount; ++node) + { + EdgeInfoVecT edgesInfo; + for (auto edge : facade.GetAdjacentEdgeRange(node)) + { + uint64_t target = facade.GetTarget(edge); + auto const & data = facade.GetEdgeData(edge); + + edgesInfo.push_back(EdgeInfoT(target, data)); + } + + sort(edgesInfo.begin(), edgesInfo.end(), [](EdgeInfoT const & a, EdgeInfoT const & b) + { + if (a.first != b.first) + return a.first < b.first; + + if (a.second.forward != b.second.forward) + return a.second.forward > b.second.forward; + + return a.second.id < b.second.id; + }); + + uint64_t lastTarget = 0; + for (auto edge : edgesInfo) + { + uint64_t const target = edge.first; + auto const & data = edge.second; + + if (target < lastTarget) + LOG(LCRITICAL, ("Invalid order of target nodes", target, lastTarget)); + + lastTarget = target; + assert(data.forward || data.backward); + + auto addDataFn = [&](bool b) + { + uint64_t const e = TraverseMatrixInRowOrder<uint64_t>(nodeCount, node, target, b); + + auto compressId = [&](uint64_t id) + { + return bits::ZigZagEncode(int64_t(node) - int64_t(id)); + }; + + if (!edges.empty()) + CHECK_GREATER_OR_EQUAL(e, edges.back(), ()); + + if (!edges.empty() && (edges.back() == e)) + { + LOG(LWARNING, ("Invalid order of edges", e, edges.back(), nodeCount, node, target, b)); + CHECK(data.shortcut == shortcuts.back(), ()); + + auto const last = edgesData.back(); + if (static_cast<uint32_t>(data.distance) <= last) + { + if (!edgeId.empty() && data.shortcut) + { + CHECK(shortcuts.back(), ()); + unsigned oldId = node - bits::ZigZagDecode(edgeId.back()); + + if (static_cast<uint32_t>(data.distance) == last) + edgeId.back() = compressId(min(oldId, data.id)); + else + edgeId.back() = compressId(data.id); + } + + edgesData.back() = data.distance; + } + + ++ignoredEdges; + return; + } + + edges.push_back(e); + edgesData.push_back(data.distance); + shortcuts.push_back(data.shortcut); + + if (data.shortcut) + edgeId.push_back(compressId(data.id)); + }; + + if (data.forward && data.backward) + { + addDataFn(false); + addDataFn(true); + copiedEdges++; + } + else + addDataFn(data.backward); + } + } + + std::cout << "Edges count: " << edgeId.size() << std::endl; + PrintStatus(true); + + std::cout << "Sort edges..."; + std::sort(edges.begin(), edges.end()); + PrintStatus(true); + + std::cout << "Edges count: " << edges.size() << std::endl; + std::cout << "Nodes count: " << nodeCount << std::endl; + + std::cout << "--- Save matrix" << std::endl; + succinct::elias_fano::elias_fano_builder builder(edges.back(), edges.size()); + for (auto e : edges) + builder.push_back(e); + succinct::elias_fano matrix(&builder); + + std::string fileName = fPath + "." + ROUTING_MATRIX_FILE_TAG; + std::ofstream fout(fileName, std::ios::binary); + fout.write((const char*)&nodeCount, sizeof(nodeCount)); + succinct::mapper::freeze(matrix, fout); + fout.close(); + + std::cout << "--- Save edge data" << std::endl; + succinct::elias_fano_compressed_list edgeVector(edgesData); + fileName = fPath + "." + ROUTING_EDGEDATA_FILE_TAG; + succinct::mapper::freeze(edgeVector, fileName.c_str()); + + succinct::elias_fano_compressed_list edgeIdVector(edgeId); + fileName = fPath + "." + ROUTING_EDGEID_FILE_TAG; + succinct::mapper::freeze(edgeIdVector, fileName.c_str()); + + std::cout << "--- Save edge shortcuts" << std::endl; + succinct::rs_bit_vector shortcutsVector(shortcuts); + fileName = fPath + "." + ROUTING_SHORTCUTS_FILE_TAG; + succinct::mapper::freeze(shortcutsVector, fileName.c_str()); + + if (edgeId.size() != shortcutsVector.num_ones()) + LOG(LCRITICAL, ("Invalid data")); + + std::cout << "--- Test packed data" << std::endl; + std::string path = fPath + ".test"; + + { + FilesContainerW routingCont(path); + + auto appendFile = [&] (string const & tag) + { + string const fileName = fPath + "." + tag; + routingCont.Write(fileName, tag); + }; + + appendFile(ROUTING_SHORTCUTS_FILE_TAG); + appendFile(ROUTING_EDGEDATA_FILE_TAG); + appendFile(ROUTING_MATRIX_FILE_TAG); + appendFile(ROUTING_EDGEID_FILE_TAG); + + routingCont.Finish(); + } + + MY_SCOPE_GUARD(testFileGuard, bind(&my::DeleteFileX, cref(path))); + + FilesMappingContainer container; + container.Open(path); + typedef routing::OsrmDataFacade<QueryEdge::EdgeData> DataFacadeT; + DataFacadeT facadeNew; + facadeNew.Load(container); + + uint64_t edgesCount = facadeNew.GetNumberOfEdges() - copiedEdges + ignoredEdges; + std::cout << "Check node count " << facade.GetNumberOfNodes() << " == " << facadeNew.GetNumberOfNodes() << "..." << std::endl; + CHECK_EQUAL(facade.GetNumberOfNodes(), facadeNew.GetNumberOfNodes(), ()); + std::cout << "Check edges count " << facade.GetNumberOfEdges() << " == " << edgesCount << "..." << std::endl; + CHECK_EQUAL(facade.GetNumberOfEdges(), edgesCount, ()); + + std::cout << "Check edges data ..."; + bool error = false; + + assert(facade.GetNumberOfEdges() == facadeNew.GetNumberOfEdges()); + for (uint32_t i = 0; i < facade.GetNumberOfNodes(); ++i) + { + // get all edges from osrm datafacade and store just minimal weights for duplicates + vector<EdgeOsrmT> edgesOsrm; + for (auto e : facade.GetAdjacentEdgeRange(i)) + edgesOsrm.push_back(EdgeOsrmT(facade.GetTarget(e), facade.GetEdgeData(e))); + + sort(edgesOsrm.begin(), edgesOsrm.end(), [](EdgeOsrmT const & a, EdgeOsrmT const & b) + { + if (a.first != b.first) + return a.first < b.first; + + QueryEdge::EdgeData const & d1 = a.second; + QueryEdge::EdgeData const & d2 = b.second; + + if (d1.forward != d2.forward) + return d1.forward < d2.forward; + + if (d1.backward != d2.backward) + return d1.backward < d2.backward; + + if (d1.distance != d2.distance) + return d1.distance < d2.distance; + + return d1.id < d2.id; + }); + + for (size_t k = 1; k < edgesOsrm.size();) + { + auto const & e1 = edgesOsrm[k - 1]; + auto const & e2 = edgesOsrm[k]; + + if (e1.first != e2.first || + e1.second.forward != e2.second.forward || + e1.second.backward != e2.second.backward) + { + ++k; + continue; + } + + if (e1.second.distance > e2.second.distance) + edgesOsrm.erase(edgesOsrm.begin() + k - 1); + else + edgesOsrm.erase(edgesOsrm.begin() + k); + } + + vector<EdgeOsrmT> v1, v2; + for (auto e : edgesOsrm) + { + QueryEdge::EdgeData d = e.second; + if (d.forward && d.backward) + { + d.backward = false; + v1.push_back(EdgeOsrmT(e.first, d)); + d.forward = false; + d.backward = true; + } + + v1.push_back(EdgeOsrmT(e.first, d)); + } + + for (auto e : facadeNew.GetAdjacentEdgeRange(i)) + v2.push_back(EdgeOsrmT(facadeNew.GetTarget(e), facadeNew.GetEdgeData(e, i))); + + if (v1.size() != v2.size()) + { + auto printV = [](vector<EdgeOsrmT> const & v, stringstream & ss) + { + for (auto i : v) + ss << EdgeDataToString(i) << std::endl; + }; + + sort(v1.begin(), v1.end(), EdgeLess()); + sort(v2.begin(), v2.end(), EdgeLess()); + + stringstream ss; + ss << "File name: " << fPath << std::endl; + ss << "Not equal edges count for node: " << i << std::endl; + ss << "v1: " << v1.size() << " v2: " << v2.size() << std::endl; + ss << "--- v1 ---" << std::endl; + printV(v1, ss); + ss << "--- v2 ---" << std::endl; + printV(v2, ss); + + LOG(LCRITICAL, (ss.str())); + } + + sort(v1.begin(), v1.end(), EdgeLess()); + sort(v2.begin(), v2.end(), EdgeLess()); + + // compare vectors + for (size_t k = 0; k < v1.size(); ++k) + { + EdgeOsrmT const & e1 = v1[k]; + EdgeOsrmT const & e2 = v2[k]; + + QueryEdge::EdgeData const & d1 = e1.second; + QueryEdge::EdgeData const & d2 = e2.second; + + if (e1.first != e2.first || + d1.backward != d2.backward || + d1.forward != d2.forward || + d1.distance != d2.distance || + (d1.id != d2.id && (d1.shortcut || d2.shortcut)) || + d1.shortcut != d2.shortcut) + { + std::cout << "--- " << std::endl; + for (size_t j = 0; j < v1.size(); ++j) + std::cout << EdgeDataToString(v1[j]) << " - " << EdgeDataToString(v2[j]) << std::endl; + + LOG(LCRITICAL, ("File:", fPath, "Node:", i, EdgeDataToString(e1), EdgeDataToString(e2))); + } + } + + } + PrintStatus(!error); +} + +} diff --git a/3party/osrm/osrm-backend/mapsme/converter.hpp b/3party/osrm/osrm-backend/mapsme/converter.hpp new file mode 100644 index 0000000000..25ab53aaf5 --- /dev/null +++ b/3party/osrm/osrm-backend/mapsme/converter.hpp @@ -0,0 +1,13 @@ +#pragma once + +#include <string> + +#include "../data_structures/query_edge.hpp" + +namespace mapsme +{ + + +void GenerateRoutingIndex(const std::string & fPath); + +} diff --git a/3party/osrm/osrm-backend/mapsme/main.cpp b/3party/osrm/osrm-backend/mapsme/main.cpp new file mode 100644 index 0000000000..5d626a9e61 --- /dev/null +++ b/3party/osrm/osrm-backend/mapsme/main.cpp @@ -0,0 +1,29 @@ +#include <stdlib.h> + +#include <iostream> +#include <boost/program_options.hpp> +#include "converter.hpp" + +int main(int argc, char **argv) +{ + + boost::program_options::options_description descr; + + descr.add_options() + ("help", "h") + ("input,i", boost::program_options::value<std::string>(), "Path to input osrm file (belarus.osrm)"); + + boost::program_options::variables_map vm; + boost::program_options::store(boost::program_options::command_line_parser(argc, argv).options(descr).run(), vm); + boost::program_options::notify(vm); + if (vm.count("help") || !vm.count("input")) + { + std::cout << descr; + return 0; + } + + + mapsme::GenerateRoutingIndex(vm["input"].as<std::string>()); + + return 0; +} diff --git a/3party/osrm/osrm-backend/plugins/MapsMePlugin.hpp b/3party/osrm/osrm-backend/plugins/MapsMePlugin.hpp new file mode 100644 index 0000000000..a826a08f4d --- /dev/null +++ b/3party/osrm/osrm-backend/plugins/MapsMePlugin.hpp @@ -0,0 +1,193 @@ +#pragma once + +#include "plugin_base.hpp" + +/* +#include "../algorithms/object_encoder.h" +#include "../DataStructures/EdgeBasedNodeData.h" +#include "../DataStructures/JSONContainer.h" +#include "../DataStructures/QueryEdge.h" +#include "../DataStructures/SearchEngine.h" +#include "../Descriptors/BaseDescriptor.h" +#include "../Util/make_unique.hpp" +#include "../Util/StringUtil.h" +#include "../Util/TimingUtil.h" +#include <algorithm> +#include <memory> +#include <unordered_map> +#include <string> +#include <vector> + +#include "../../../../base/string_utils.hpp" +#include "../../../../coding/file_container.hpp" +#include "../../../../coding/read_write_utils.hpp" +#include "../../../../defines.hpp" +#include "../../../../geometry/region2d.hpp" +#include "../../../../indexer/geometry_serialization.hpp" +#include "../../../../indexer/mercator.hpp" +#include "../../../../storage/country_decl.hpp" +#include "../../../../storage/country_polygon.hpp" + +template <class DataFacadeT> class MapsMePlugin final : public BasePlugin +{ + class GetByPoint + { + m2::PointD const &m_pt; + std::vector<std::vector<m2::RegionD>> const &m_regions; + + public: + size_t m_res; + + GetByPoint(std::vector<std::vector<m2::RegionD>> const ®ions, m2::PointD const &pt) + : m_pt(pt), m_regions(regions), m_res(-1) + { + } + + /// @param[in] id Index in m_countries. + /// @return false If point is in country. + bool operator()(size_t id) + { + auto it = + find_if(m_regions[id].begin(), m_regions[id].end(), [&](m2::RegionD const ®ion) + { return region.Contains(m_pt);}); + if (it == m_regions[id].end()) + return true; + m_res = id; + return false; + } + }; + + public: + explicit MapsMePlugin(DataFacadeT *facade, std::string const &baseDir, std::string const & nodeDataFile) + : m_descriptorString("mapsme"), m_facade(facade), + m_reader(baseDir + '/' + PACKED_POLYGONS_FILE) + { + if (!osrm::LoadNodeDataFromFile(nodeDataFile, m_nodeData)) + { + SimpleLogger().Write(logDEBUG) << "Can't load node data"; + return; + } + ReaderSource<ModelReaderPtr> src(m_reader.GetReader(PACKED_POLYGONS_INFO_TAG)); + rw::Read(src, m_countries); + m_regions.resize(m_countries.size()); + for (size_t i = 0; i < m_countries.size(); ++i) + { + // load regions from file + ReaderSource<ModelReaderPtr> src(m_reader.GetReader(strings::to_string(i))); + + uint32_t const count = ReadVarUint<uint32_t>(src); + for (size_t j = 0; j < count; ++j) + { + vector<m2::PointD> points; + serial::LoadOuterPath(src, serial::CodingParams(), points); + + m_regions[i].emplace_back(move(m2::RegionD(points.begin(), points.end()))); + } + } + m_searchEngine = osrm::make_unique<SearchEngine<DataFacadeT>>(facade); + } + + template <class ToDo> void ForEachCountry(m2::PointD const &pt, ToDo &toDo) const + { + for (size_t i = 0; i < m_countries.size(); ++i) + if (m_countries[i].m_rect.IsPointInside(pt)) + if (!toDo(i)) + return; + } + + virtual ~MapsMePlugin() {} + + const std::string GetDescriptor() const final { return m_descriptorString; } + + void HandleRequest(const RouteParameters &route_parameters, http::Reply &reply) final + { + // check number of parameters + if (2 > route_parameters.coordinates.size()) + { + reply = http::Reply::StockReply(http::Reply::badRequest); + return; + } + + RawRouteData raw_route; + raw_route.check_sum = m_facade->GetCheckSum(); + + if (std::any_of(begin(route_parameters.coordinates), end(route_parameters.coordinates), + [&](FixedPointCoordinate coordinate) + { + return !coordinate.isValid(); + })) + { + reply = http::Reply::StockReply(http::Reply::badRequest); + return; + } + + for (const FixedPointCoordinate &coordinate : route_parameters.coordinates) + { + raw_route.raw_via_node_coordinates.emplace_back(coordinate); + } + + std::vector<PhantomNode> phantom_node_vector(raw_route.raw_via_node_coordinates.size()); + const bool checksum_OK = (route_parameters.check_sum == raw_route.check_sum); + + for (unsigned i = 0; i < raw_route.raw_via_node_coordinates.size(); ++i) + { + m_facade->FindPhantomNodeForCoordinate(raw_route.raw_via_node_coordinates[i], + phantom_node_vector[i], + route_parameters.zoom_level); + } + + PhantomNodes current_phantom_node_pair; + for (unsigned i = 0; i < phantom_node_vector.size() - 1; ++i) + { + current_phantom_node_pair.source_phantom = phantom_node_vector[i]; + current_phantom_node_pair.target_phantom = phantom_node_vector[i + 1]; + raw_route.segment_end_coordinates.emplace_back(current_phantom_node_pair); + } + + m_searchEngine->alternative_path(raw_route.segment_end_coordinates.front(), raw_route); + + if (INVALID_EDGE_WEIGHT == raw_route.shortest_path_length) + { + SimpleLogger().Write(logDEBUG) << "Error occurred, single path not found"; + } + reply.status = http::Reply::ok; + + // Get mwm names + set<string> usedMwms; + + for (auto i : osrm::irange<std::size_t>(0, raw_route.unpacked_path_segments.size())) + { + size_t const n = raw_route.unpacked_path_segments[i].size(); + for (size_t j = 0; j < n; ++j) + { + PathData const &path_data = raw_route.unpacked_path_segments[i][j]; + auto const & data = m_nodeData[path_data.node]; + if (data.m_segments.empty()) + continue; + auto const & seg = data.m_segments.front(); + m2::PointD pt = MercatorBounds::FromLatLon(seg.lat1, seg.lon1); + GetByPoint doGet(m_regions, pt); + ForEachCountry(pt, doGet); + + if (doGet.m_res != -1) + usedMwms.insert(m_countries[doGet.m_res].m_name); + } + } + + JSON::Object json_object; + JSON::Array json_array; + json_array.values.insert(json_array.values.begin(), usedMwms.begin(), usedMwms.end()); + json_object.values["used_mwms"] = json_array; + JSON::render(reply.content, json_object); + } + + private: + std::unique_ptr<SearchEngine<DataFacadeT>> m_searchEngine; + std::vector<storage::CountryDef> m_countries; + std::vector<std::vector<m2::RegionD>> m_regions; + std::string m_descriptorString; + DataFacadeT * m_facade; + FilesContainerR m_reader; + osrm::NodeDataVectorT m_nodeData; +};*/ + diff --git a/3party/osrm/osrm-backend/routing_algorithms/many_to_many.hpp b/3party/osrm/osrm-backend/routing_algorithms/many_to_many.hpp index 2388804718..6528229001 100755 --- a/3party/osrm/osrm-backend/routing_algorithms/many_to_many.hpp +++ b/3party/osrm/osrm-backend/routing_algorithms/many_to_many.hpp @@ -208,7 +208,7 @@ class ManyToManyRouting final { for (auto edge : super::facade->GetAdjacentEdgeRange(node)) { - const auto &data = super::facade->GetEdgeData(edge); + const auto &data = super::facade->GetEdgeData(edge, node); const bool direction_flag = (forward_direction ? data.forward : data.backward); if (direction_flag) { @@ -241,7 +241,7 @@ class ManyToManyRouting final { for (auto edge : super::facade->GetAdjacentEdgeRange(node)) { - const auto &data = super::facade->GetEdgeData(edge); + const auto &data = super::facade->GetEdgeData(edge, node); const bool reverse_flag = ((!forward_direction) ? data.forward : data.backward); if (reverse_flag) { diff --git a/3party/osrm/osrm-backend/routing_algorithms/n_to_m_many_to_many.hpp b/3party/osrm/osrm-backend/routing_algorithms/n_to_m_many_to_many.hpp new file mode 100644 index 0000000000..e3001b9021 --- /dev/null +++ b/3party/osrm/osrm-backend/routing_algorithms/n_to_m_many_to_many.hpp @@ -0,0 +1,268 @@ +/* + +Copyright (c) 2014, Project OSRM, Dennis Luxen, others +All rights reserved. + +Redistribution and use in source and binary forms, with or without modification, +are permitted provided that the following conditions are met: + +Redistributions of source code must retain the above copyright notice, this list +of conditions and the following disclaimer. +Redistributions in binary form must reproduce the above copyright notice, this +list of conditions and the following disclaimer in the documentation and/or +other materials provided with the distribution. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR +ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES +(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; +LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON +ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +*/ + +#ifndef NMMANY_TO_MANY_ROUTING_H +#define NMMANY_TO_MANY_ROUTING_H + +#include "routing_base.hpp" +#include "../data_structures/search_engine_data.hpp" +#include "../typedefs.h" + +#include "many_to_many.hpp" + +#include <boost/assert.hpp> + +#include <limits> +#include <memory> +#include <unordered_map> +#include <vector> + +template <class DataFacadeT> class NMManyToManyRouting final + : public BasicRoutingInterface<DataFacadeT, NMManyToManyRouting<DataFacadeT>> +{ + using super = BasicRoutingInterface<DataFacadeT, NMManyToManyRouting<DataFacadeT>>; + using QueryHeap = SearchEngineData::QueryHeap; + SearchEngineData &engine_working_data; + + struct NodeBucket + { + unsigned target_id; // essentially a row in the distance matrix + EdgeWeight distance; + NodeBucket(const unsigned target_id, const EdgeWeight distance) + : target_id(target_id), distance(distance) + { + } + }; + using SearchSpaceWithBuckets = std::unordered_map<NodeID, std::vector<NodeBucket>>; + + public: + NMManyToManyRouting(DataFacadeT *facade, SearchEngineData &engine_working_data) + : super(facade), engine_working_data(engine_working_data) + { + } + + std::shared_ptr<std::vector<EdgeWeight>> operator()(const PhantomNodeArray &phantom_sources_nodes_array, + const PhantomNodeArray &phantom_targets_nodes_array) const + { + const unsigned number_of_sources = static_cast<unsigned>(phantom_sources_nodes_array.size()); + const unsigned number_of_targets = static_cast<unsigned>(phantom_targets_nodes_array.size()); + std::shared_ptr<std::vector<EdgeWeight>> result_table = + std::make_shared<std::vector<EdgeWeight>>(number_of_sources * number_of_targets, + std::numeric_limits<EdgeWeight>::max()); + + engine_working_data.InitializeOrClearFirstThreadLocalStorage( + super::facade->GetNumberOfNodes()); + + QueryHeap &query_heap = *(engine_working_data.forward_heap_1); + + SearchSpaceWithBuckets search_space_with_buckets; + + unsigned target_id = 0; + for (const std::vector<PhantomNode> &phantom_node_vector : phantom_targets_nodes_array) + { + query_heap.Clear(); + // insert target(s) at distance 0 + + for (const PhantomNode &phantom_node : phantom_node_vector) + { + if (SPECIAL_NODEID != phantom_node.forward_node_id) + { + query_heap.Insert(phantom_node.forward_node_id, + phantom_node.GetForwardWeightPlusOffset(), + phantom_node.forward_node_id); + } + if (SPECIAL_NODEID != phantom_node.reverse_node_id) + { + query_heap.Insert(phantom_node.reverse_node_id, + phantom_node.GetReverseWeightPlusOffset(), + phantom_node.reverse_node_id); + } + } + + // explore search space + while (!query_heap.Empty()) + { + BackwardRoutingStep(target_id, query_heap, search_space_with_buckets); + } + + ++target_id; + } + + // for each source do forward search + unsigned source_id = 0; + for (const std::vector<PhantomNode> &phantom_node_vector : phantom_sources_nodes_array) + { + query_heap.Clear(); + for (const PhantomNode &phantom_node : phantom_node_vector) + { + // insert sources at distance 0 + if (SPECIAL_NODEID != phantom_node.forward_node_id) + { + query_heap.Insert(phantom_node.forward_node_id, + -phantom_node.GetForwardWeightPlusOffset(), + phantom_node.forward_node_id); + } + if (SPECIAL_NODEID != phantom_node.reverse_node_id) + { + query_heap.Insert(phantom_node.reverse_node_id, + -phantom_node.GetReverseWeightPlusOffset(), + phantom_node.reverse_node_id); + } + } + + // explore search space + while (!query_heap.Empty()) + { + ForwardRoutingStep(source_id, + number_of_targets, + query_heap, + search_space_with_buckets, + result_table); + + } + + ++source_id; + } + //BOOST_ASSERT(source_id == target_id); + return result_table; + } + + void ForwardRoutingStep(const unsigned source_id, + const unsigned number_of_locations, + QueryHeap &query_heap, + const SearchSpaceWithBuckets &search_space_with_buckets, + std::shared_ptr<std::vector<EdgeWeight>> result_table) const + { + const NodeID node = query_heap.DeleteMin(); + const int source_distance = query_heap.GetKey(node); + + // check if each encountered node has an entry + const auto bucket_iterator = search_space_with_buckets.find(node); + // iterate bucket if there exists one + if (bucket_iterator != search_space_with_buckets.end()) + { + const std::vector<NodeBucket> &bucket_list = bucket_iterator->second; + for (const NodeBucket ¤t_bucket : bucket_list) + { + // get target id from bucket entry + const unsigned target_id = current_bucket.target_id; + const int target_distance = current_bucket.distance; + const EdgeWeight current_distance = + (*result_table)[source_id * number_of_locations + target_id]; + // check if new distance is better + const EdgeWeight new_distance = source_distance + target_distance; + if (new_distance >= 0 && new_distance < current_distance) + { + (*result_table)[source_id * number_of_locations + target_id] = + (source_distance + target_distance); + } + } + } + if (StallAtNode<true>(node, source_distance, query_heap)) + { + return; + } + RelaxOutgoingEdges<true>(node, source_distance, query_heap); + } + + void BackwardRoutingStep(const unsigned target_id, + QueryHeap &query_heap, + SearchSpaceWithBuckets &search_space_with_buckets) const + { + const NodeID node = query_heap.DeleteMin(); + const int target_distance = query_heap.GetKey(node); + + // store settled nodes in search space bucket + search_space_with_buckets[node].emplace_back(target_id, target_distance); + + if (StallAtNode<false>(node, target_distance, query_heap)) + { + return; + } + + RelaxOutgoingEdges<false>(node, target_distance, query_heap); + } + + template <bool forward_direction> + inline void + RelaxOutgoingEdges(const NodeID node, const EdgeWeight distance, QueryHeap &query_heap) const + { + for (auto edge : super::facade->GetAdjacentEdgeRange(node)) + { + const auto &data = super::facade->GetEdgeData(edge, node); + const bool direction_flag = (forward_direction ? data.forward : data.backward); + if (direction_flag) + { + const NodeID to = super::facade->GetTarget(edge); + const int edge_weight = data.distance; + + BOOST_ASSERT_MSG(edge_weight > 0, "edge_weight invalid"); + const int to_distance = distance + edge_weight; + + // New Node discovered -> Add to Heap + Node Info Storage + if (!query_heap.WasInserted(to)) + { + query_heap.Insert(to, to_distance, node); + } + // Found a shorter Path -> Update distance + else if (to_distance < query_heap.GetKey(to)) + { + // new parent + query_heap.GetData(to).parent = node; + query_heap.DecreaseKey(to, to_distance); + } + } + } + } + + // Stalling + template <bool forward_direction> + inline bool StallAtNode(const NodeID node, const EdgeWeight distance, QueryHeap &query_heap) + const + { + for (auto edge : super::facade->GetAdjacentEdgeRange(node)) + { + const auto &data = super::facade->GetEdgeData(edge, node); + const bool reverse_flag = ((!forward_direction) ? data.forward : data.backward); + if (reverse_flag) + { + const NodeID to = super::facade->GetTarget(edge); + const int edge_weight = data.distance; + BOOST_ASSERT_MSG(edge_weight > 0, "edge_weight invalid"); + if (query_heap.WasInserted(to)) + { + if (query_heap.GetKey(to) + edge_weight < distance) + { + return true; + } + } + } + } + return false; + } +}; +#endif diff --git a/3party/osrm/osrm-backend/routing_algorithms/routing_base.hpp b/3party/osrm/osrm-backend/routing_algorithms/routing_base.hpp index 52c16a77ee..4b5b483567 100755 --- a/3party/osrm/osrm-backend/routing_algorithms/routing_base.hpp +++ b/3party/osrm/osrm-backend/routing_algorithms/routing_base.hpp @@ -101,7 +101,7 @@ template <class DataFacadeT, class Derived> class BasicRoutingInterface // Stalling for (const auto edge : facade->GetAdjacentEdgeRange(node)) { - const EdgeData &data = facade->GetEdgeData(edge); + const EdgeData &data = facade->GetEdgeData(edge, node); const bool reverse_flag = ((!forward_direction) ? data.forward : data.backward); if (reverse_flag) { @@ -122,7 +122,7 @@ template <class DataFacadeT, class Derived> class BasicRoutingInterface for (const auto edge : facade->GetAdjacentEdgeRange(node)) { - const EdgeData &data = facade->GetEdgeData(edge); + const EdgeData &data = facade->GetEdgeData(edge, node); bool forward_directionFlag = (forward_direction ? data.forward : data.backward); if (forward_directionFlag) { @@ -153,10 +153,10 @@ template <class DataFacadeT, class Derived> class BasicRoutingInterface const PhantomNodes &phantom_node_pair, std::vector<PathData> &unpacked_path) const { - const bool start_traversed_in_reverse = - (packed_path.front() != phantom_node_pair.source_phantom.forward_node_id); - const bool target_traversed_in_reverse = - (packed_path.back() != phantom_node_pair.target_phantom.forward_node_id); + //const bool start_traversed_in_reverse = + // (packed_path.front() != phantom_node_pair.source_phantom.forward_node_id); + //const bool target_traversed_in_reverse = + // (packed_path.back() != phantom_node_pair.target_phantom.forward_node_id); const unsigned packed_path_size = static_cast<unsigned>(packed_path.size()); std::stack<std::pair<NodeID, NodeID>> recursion_stack; @@ -167,6 +167,7 @@ template <class DataFacadeT, class Derived> class BasicRoutingInterface recursion_stack.emplace(packed_path[i - 1], packed_path[i]); } + unpacked_path.emplace_back(packed_path[0], INVALID_EDGE_WEIGHT, TurnInstruction::NoTurn, INVALID_EDGE_WEIGHT, TRAVEL_MODE_INACCESSIBLE); std::pair<NodeID, NodeID> edge; while (!recursion_stack.empty()) { @@ -183,14 +184,17 @@ template <class DataFacadeT, class Derived> class BasicRoutingInterface // facade->FindEdge does not suffice here in case of shortcuts. // The above explanation unclear? Think! EdgeID smaller_edge_id = SPECIAL_EDGEID; + NodeID smaller_node_id = SPECIAL_NODEID; int edge_weight = std::numeric_limits<EdgeWeight>::max(); for (const auto edge_id : facade->GetAdjacentEdgeRange(edge.first)) { - const int weight = facade->GetEdgeData(edge_id).distance; + auto const & edgeData = facade->GetEdgeData(edge_id, edge.first); + const int weight = edgeData.distance; if ((facade->GetTarget(edge_id) == edge.second) && (weight < edge_weight) && - facade->GetEdgeData(edge_id).forward) + edgeData.forward) { smaller_edge_id = edge_id; + smaller_node_id = edge.first; edge_weight = weight; } } @@ -206,18 +210,20 @@ template <class DataFacadeT, class Derived> class BasicRoutingInterface { for (const auto edge_id : facade->GetAdjacentEdgeRange(edge.second)) { - const int weight = facade->GetEdgeData(edge_id).distance; + auto const & edgeData = facade->GetEdgeData(edge_id, edge.second); + const int weight = edgeData.distance; if ((facade->GetTarget(edge_id) == edge.first) && (weight < edge_weight) && - facade->GetEdgeData(edge_id).backward) + edgeData.backward) { smaller_edge_id = edge_id; edge_weight = weight; + smaller_node_id = edge.second; } } } BOOST_ASSERT_MSG(edge_weight != INVALID_EDGE_WEIGHT, "edge id invalid"); - const EdgeData &ed = facade->GetEdgeData(smaller_edge_id); + const EdgeData &ed = facade->GetEdgeData(smaller_edge_id, smaller_node_id); if (ed.shortcut) { // unpack const NodeID middle_node_id = ed.id; @@ -227,87 +233,11 @@ template <class DataFacadeT, class Derived> class BasicRoutingInterface } else { - BOOST_ASSERT_MSG(!ed.shortcut, "original edge flagged as shortcut"); - unsigned name_index = facade->GetNameIndexFromEdgeID(ed.id); - const TurnInstruction turn_instruction = facade->GetTurnInstructionForEdgeID(ed.id); const TravelMode travel_mode = facade->GetTravelModeForEdgeID(ed.id); - if (!facade->EdgeIsCompressed(ed.id)) - { - BOOST_ASSERT(!facade->EdgeIsCompressed(ed.id)); - unpacked_path.emplace_back(facade->GetGeometryIndexForEdgeID(ed.id), name_index, - turn_instruction, ed.distance, travel_mode); - } - else - { - std::vector<unsigned> id_vector; - facade->GetUncompressedGeometry(facade->GetGeometryIndexForEdgeID(ed.id), - id_vector); - - const std::size_t start_index = - (unpacked_path.empty() - ? ((start_traversed_in_reverse) - ? id_vector.size() - - phantom_node_pair.source_phantom.fwd_segment_position - 1 - : phantom_node_pair.source_phantom.fwd_segment_position) - : 0); - const std::size_t end_index = id_vector.size(); - - BOOST_ASSERT(start_index >= 0); - BOOST_ASSERT(start_index <= end_index); - for (std::size_t i = start_index; i < end_index; ++i) - { - unpacked_path.emplace_back(id_vector[i], name_index, - TurnInstruction::NoTurn, 0, travel_mode); - } - unpacked_path.back().turn_instruction = turn_instruction; - unpacked_path.back().segment_duration = ed.distance; - } - } - } - if (SPECIAL_EDGEID != phantom_node_pair.target_phantom.packed_geometry_id) - { - std::vector<unsigned> id_vector; - facade->GetUncompressedGeometry(phantom_node_pair.target_phantom.packed_geometry_id, - id_vector); - const bool is_local_path = (phantom_node_pair.source_phantom.packed_geometry_id == - phantom_node_pair.target_phantom.packed_geometry_id) && - unpacked_path.empty(); - - std::size_t start_index = 0; - if (is_local_path) - { - start_index = phantom_node_pair.source_phantom.fwd_segment_position; - if (target_traversed_in_reverse) - { - start_index = - id_vector.size() - phantom_node_pair.source_phantom.fwd_segment_position; - } - } - - std::size_t end_index = phantom_node_pair.target_phantom.fwd_segment_position; - if (target_traversed_in_reverse) - { - std::reverse(id_vector.begin(), id_vector.end()); - end_index = - id_vector.size() - phantom_node_pair.target_phantom.fwd_segment_position; - } - - if (start_index > end_index) - { - start_index = std::min(start_index, id_vector.size() - 1); - } - - for (std::size_t i = start_index; i != end_index; (start_index < end_index ? ++i : --i)) - { - BOOST_ASSERT(i < id_vector.size()); - BOOST_ASSERT(phantom_node_pair.target_phantom.forward_travel_mode > 0); - unpacked_path.emplace_back( - PathData{id_vector[i], - phantom_node_pair.target_phantom.name_id, + unpacked_path.emplace_back(edge.second, INVALID_EDGE_WEIGHT, TurnInstruction::NoTurn, - 0, - phantom_node_pair.target_phantom.forward_travel_mode}); + ed.distance, travel_mode); } } @@ -344,14 +274,17 @@ template <class DataFacadeT, class Derived> class BasicRoutingInterface recursion_stack.pop(); EdgeID smaller_edge_id = SPECIAL_EDGEID; + NodeID smaller_node_id = SPECIAL_NODEID; int edge_weight = std::numeric_limits<EdgeWeight>::max(); for (const auto edge_id : facade->GetAdjacentEdgeRange(edge.first)) { - const int weight = facade->GetEdgeData(edge_id).distance; + auto const & edgeData = facade->GetEdgeData(edge_id, edge.first); + const int weight = edgeData.distance; if ((facade->GetTarget(edge_id) == edge.second) && (weight < edge_weight) && - facade->GetEdgeData(edge_id).forward) + edgeData.forward) { smaller_edge_id = edge_id; + smaller_node_id = edge.first; edge_weight = weight; } } @@ -360,11 +293,13 @@ template <class DataFacadeT, class Derived> class BasicRoutingInterface { for (const auto edge_id : facade->GetAdjacentEdgeRange(edge.second)) { - const int weight = facade->GetEdgeData(edge_id).distance; - if ((facade->GetTarget(edge_id) == edge.first) && (weight < edge_weight) && - facade->GetEdgeData(edge_id).backward) + auto const & edgeData = facade->GetEdgeData(edge_id, edge.second); + const int weight = edgeData.distance; + if ((facade->GetTarget(edge_id) == edge.first) && (weight < edge_weight) && + edgeData.backward) { smaller_edge_id = edge_id; + smaller_node_id = edge.second; edge_weight = weight; } } @@ -372,7 +307,7 @@ template <class DataFacadeT, class Derived> class BasicRoutingInterface BOOST_ASSERT_MSG(edge_weight != std::numeric_limits<EdgeWeight>::max(), "edge weight invalid"); - const EdgeData &ed = facade->GetEdgeData(smaller_edge_id); + const EdgeData &ed = facade->GetEdgeData(smaller_edge_id, smaller_node_id); if (ed.shortcut) { // unpack const NodeID middle_node_id = ed.id; diff --git a/3party/osrm/osrm-backend/server/data_structures/datafacade_base.hpp b/3party/osrm/osrm-backend/server/data_structures/datafacade_base.hpp index 20d0430576..d7e00581ae 100755 --- a/3party/osrm/osrm-backend/server/data_structures/datafacade_base.hpp +++ b/3party/osrm/osrm-backend/server/data_structures/datafacade_base.hpp @@ -39,7 +39,7 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #include "../../util/string_util.hpp" #include "../../typedefs.h" -#include <osrm/coordinate.hpp> +#include "../../include/osrm/coordinate.hpp" #include <string> @@ -64,6 +64,8 @@ template <class EdgeDataT> class BaseDataFacade virtual const EdgeDataT &GetEdgeData(const EdgeID e) const = 0; + virtual EdgeDataT GetEdgeData(const EdgeID e, const NodeID n) = 0; + virtual EdgeID BeginEdges(const NodeID n) const = 0; virtual EdgeID EndEdges(const NodeID n) const = 0; diff --git a/3party/osrm/osrm-backend/server/data_structures/internal_datafacade.hpp b/3party/osrm/osrm-backend/server/data_structures/internal_datafacade.hpp index 823ac3329b..25bc54ee79 100755 --- a/3party/osrm/osrm-backend/server/data_structures/internal_datafacade.hpp +++ b/3party/osrm/osrm-backend/server/data_structures/internal_datafacade.hpp @@ -327,6 +327,11 @@ template <class EdgeDataT> class InternalDataFacade final : public BaseDataFacad return m_query_graph->GetEdgeData(e); } + EdgeDataT GetEdgeData(const EdgeID e, const NodeID n) override final + { + return m_query_graph->GetEdgeData(e); + } + EdgeID BeginEdges(const NodeID n) const override final { return m_query_graph->BeginEdges(n); } EdgeID EndEdges(const NodeID n) const override final { return m_query_graph->EndEdges(n); } diff --git a/3party/osrm/osrm-backend/server/data_structures/shared_datafacade.hpp b/3party/osrm/osrm-backend/server/data_structures/shared_datafacade.hpp index b156423160..bd93a8b6ef 100755 --- a/3party/osrm/osrm-backend/server/data_structures/shared_datafacade.hpp +++ b/3party/osrm/osrm-backend/server/data_structures/shared_datafacade.hpp @@ -299,6 +299,11 @@ template <class EdgeDataT> class SharedDataFacade final : public BaseDataFacade< return m_query_graph->GetEdgeData(e); } + EdgeDataT GetEdgeData(const EdgeID e, const NodeID n) override final + { + return m_query_graph->GetEdgeData(e); + } + EdgeID BeginEdges(const NodeID n) const override final { return m_query_graph->BeginEdges(n); } EdgeID EndEdges(const NodeID n) const override final { return m_query_graph->EndEdges(n); } diff --git a/3party/osrm/osrm-backend/util/fingerprint_impl.hpp b/3party/osrm/osrm-backend/util/fingerprint_impl.hpp index 1a528267b5..e9097e4735 100755 --- a/3party/osrm/osrm-backend/util/fingerprint_impl.hpp +++ b/3party/osrm/osrm-backend/util/fingerprint_impl.hpp @@ -36,9 +36,9 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #define HAS64BITS 0 #define MD5PREPARE "b04b5d82a15a1f412e3dd3f8d054b0cc" -#define MD5RTREE "92ac7e134019fdad361a15d6da036584" -#define MD5GRAPH "409a612147d22797f5b4c1bdb809b8c9" -#define MD5OBJECTS "4c258d9311a7e1f1d5305ab73180bd92" +#define MD5RTREE "4cd15b5a6ae32818b38ba5ad0b7fa18a" +#define MD5GRAPH "f4a42ddc44689019e1794b4db9809de1" +#define MD5OBJECTS "2782e122d4052c4ba1dd8ca62fac930d" FingerPrint::FingerPrint() : magic_number(1297240911) { diff --git a/3party/osrm/osrm-backend/util/git_sha.cpp b/3party/osrm/osrm-backend/util/git_sha.cpp index 9d0e91da02..64f9fec271 100755 --- a/3party/osrm/osrm-backend/util/git_sha.cpp +++ b/3party/osrm/osrm-backend/util/git_sha.cpp @@ -27,5 +27,5 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #include "git_sha.hpp" -#define GIT_DESCRIPTION "HEAD-HASH-NOTFOUND" +#define GIT_DESCRIPTION "android-431-210-g6ea7ced" char g_GIT_DESCRIPTION[] = GIT_DESCRIPTION; diff --git a/3party/osrm/osrm-backend/util/graph_loader.hpp b/3party/osrm/osrm-backend/util/graph_loader.hpp index d741334baf..e32696d1e1 100755 --- a/3party/osrm/osrm-backend/util/graph_loader.hpp +++ b/3party/osrm/osrm-backend/util/graph_loader.hpp @@ -41,8 +41,6 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #include <boost/filesystem.hpp> #include <boost/filesystem/fstream.hpp> -#include <tbb/parallel_sort.h> - #include <cmath> #include <algorithm> @@ -134,6 +132,7 @@ NodeID read_undirected_osrm_stream(std::istream &input_stream, short dir; // direction (0 = open, 1 = forward, 2+ = open) bool is_roundabout, ignore_in_grid, is_access_restricted, is_split; TravelMode travel_mode; + unsigned way_id; EdgeID m; input_stream.read(reinterpret_cast<char *>(&m), sizeof(unsigned)); @@ -142,6 +141,7 @@ NodeID read_undirected_osrm_stream(std::istream &input_stream, for (EdgeID i = 0; i < m; ++i) { + input_stream.read(reinterpret_cast<char *>(&way_id), sizeof(unsigned)); input_stream.read(reinterpret_cast<char *>(&source), sizeof(unsigned)); input_stream.read(reinterpret_cast<char *>(&target), sizeof(unsigned)); input_stream.read(reinterpret_cast<char *>(&length), sizeof(int)); @@ -201,7 +201,7 @@ NodeID read_undirected_osrm_stream(std::istream &input_stream, } ext_to_int_id_map.clear(); - tbb::parallel_sort(edge_list.begin(), edge_list.end()); + sort(edge_list.begin(), edge_list.end()); // for (unsigned i = 1; i < edge_list.size(); ++i) // { @@ -350,6 +350,7 @@ NodeID readBinaryOSRMGraphFromStream(std::istream &input_stream, NodeID source, target; unsigned nameID; int length; + unsigned way_id; short dir; // direction (0 = open, 1 = forward, 2+ = open) bool is_roundabout, ignore_in_grid, is_access_restricted, is_split; TravelMode travel_mode; @@ -361,6 +362,7 @@ NodeID readBinaryOSRMGraphFromStream(std::istream &input_stream, for (EdgeID i = 0; i < m; ++i) { + input_stream.read(reinterpret_cast<char *>(&way_id), sizeof(unsigned)); input_stream.read(reinterpret_cast<char *>(&source), sizeof(unsigned)); input_stream.read(reinterpret_cast<char *>(&target), sizeof(unsigned)); input_stream.read(reinterpret_cast<char *>(&length), sizeof(int)); @@ -416,12 +418,12 @@ NodeID readBinaryOSRMGraphFromStream(std::istream &input_stream, std::swap(forward, backward); } - edge_list.emplace_back(source, target, nameID, weight, forward, backward, is_roundabout, + edge_list.emplace_back(way_id, source, target, nameID, weight, forward, backward, is_roundabout, ignore_in_grid, is_access_restricted, travel_mode, is_split); } ext_to_int_id_map.clear(); - tbb::parallel_sort(edge_list.begin(), edge_list.end()); + std::sort(edge_list.begin(), edge_list.end()); for (unsigned i = 1; i < edge_list.size(); ++i) { diff --git a/3party/osrm/osrm-backend/util/routed_options.hpp b/3party/osrm/osrm-backend/util/routed_options.hpp index 046ab71b31..1797938a74 100755 --- a/3party/osrm/osrm-backend/util/routed_options.hpp +++ b/3party/osrm/osrm-backend/util/routed_options.hpp @@ -59,6 +59,8 @@ inline void populate_base_path(ServerPaths &server_paths) BOOST_ASSERT(server_paths.find("hsgrdata") != server_paths.end()); server_paths["nodesdata"] = base_string + ".nodes"; BOOST_ASSERT(server_paths.find("nodesdata") != server_paths.end()); + server_paths["enodesdata"] = base_string + ".nodeData"; + BOOST_ASSERT(server_paths.find("nodesdata") != server_paths.end()); server_paths["edgesdata"] = base_string + ".edges"; BOOST_ASSERT(server_paths.find("edgesdata") != server_paths.end()); server_paths["geometries"] = base_string + ".geometry"; @@ -191,6 +193,9 @@ inline unsigned GenerateServerProgramOptions(const int argc, "shared-memory,s", boost::program_options::value<bool>(&use_shared_memory)->implicit_value(true), "Load data from shared memory")( + "borders", + boost::program_options::value<boost::filesystem::path>(&paths["borders"]), + "Borders folder")( "max-table-size,m", boost::program_options::value<int>(&max_locations_distance_table)->default_value(100), "Max. locations supported in distance table query")( diff --git a/3party/osrm/osrm.pro b/3party/osrm/osrm.pro index 100de097b4..5172a7aaec 100644 --- a/3party/osrm/osrm.pro +++ b/3party/osrm/osrm.pro @@ -9,23 +9,25 @@ ROOT_DIR = ../.. include($$ROOT_DIR/common.pri) DEFINES *= BOOST_ERROR_CODE_HEADER_ONLY -INCLUDEPATH *= osrm-backend/Include +INCLUDEPATH *= osrm-backend/include \ + osrm-backend/third_party SOURCES += \ - osrm-backend/Algorithms/DouglasPeucker.cpp \ - osrm-backend/Algorithms/PolylineCompressor.cpp \ +# osrm-backend/Algorithms/DouglasPeucker.cpp \ +# osrm-backend/Algorithms/PolylineCompressor.cpp \ # Contractor/EdgeBasedGraphFactory.cpp \ # Contractor/GeometryCompressor.cpp \ # Contractor/TemporaryStorage.cpp \ # datastore.cpp \ - osrm-backend/DataStructures/Coordinate.cpp \ + osrm-backend/data_structures/coordinate.cpp \ # DataStructures/HilbertValue.cpp \ # DataStructures/ImportEdge.cpp \ # DataStructures/ImportNode.cpp \ # DataStructures/RestrictionMap.cpp \ - osrm-backend/DataStructures/RouteParameters.cpp \ - osrm-backend/DataStructures/SearchEngineData.cpp \ - osrm-backend/Descriptors/DescriptionFactory.cpp \ +# osrm-backend/DataStructures/RouteParameters.cpp \ + osrm-backend/data_structures/search_engine_data.cpp \ + osrm-backend/data_structures/phantom_node.cpp \ +# osrm-backend/Descriptors/DescriptionFactory.cpp \ # osrm-backend/Util/FingerPrint.cpp \ # Extractor/BaseParser.cpp \ # Extractor/ExtractionContainers.cpp \ @@ -51,9 +53,9 @@ SOURCES += \ boost_stub.cpp \ HEADERS += \ - osrm-backend/osrm/Include/Coordinate.h \ - osrm-backend/DataStructures/SearchEngineData.h \ - osrm-backend/DataStructures/RouteParameters.h \ - osrm-backend/Algorithms/DouglasPeucker.h \ - osrm-backend/Descriptors/DescriptionFactory.h \ - osrm-backend/Util/FingerPrint.h \ + osrm-backend/osrm/include/coordinate.h \ +# osrm-backend/DataStructures/SearchEngineData.h \ +# osrm-backend/DataStructures/RouteParameters.h \ +# osrm-backend/Algorithms/DouglasPeucker.h \ +# osrm-backend/Descriptors/DescriptionFactory.h \ +# osrm-backend/Util/FingerPrint.h \ |