diff options
author | Denis Koronchik <denis@mapswithme.com> | 2014-10-08 20:01:39 +0400 |
---|---|---|
committer | Alex Zolotarev <alex@maps.me> | 2015-09-23 02:30:24 +0300 |
commit | 46958c0ba8290f1248717b3291bc1bebf35acf5c (patch) | |
tree | e58302e63edb511fbb72b57f677aa4dd83a472ef /3party/osrm | |
parent | b1d44e9b33e918f04eee07fbbe81b81723d01935 (diff) |
[osrm][routing] Improve compression of edge id’s data
Diffstat (limited to '3party/osrm')
4 files changed, 102 insertions, 45 deletions
diff --git a/3party/osrm/osrm-backend/RoutingAlgorithms/BasicRoutingInterface.h b/3party/osrm/osrm-backend/RoutingAlgorithms/BasicRoutingInterface.h index f830d2717a..90d8ae58ec 100644 --- a/3party/osrm/osrm-backend/RoutingAlgorithms/BasicRoutingInterface.h +++ b/3party/osrm/osrm-backend/RoutingAlgorithms/BasicRoutingInterface.h @@ -98,7 +98,7 @@ template <class DataFacadeT> 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) { @@ -119,7 +119,7 @@ template <class DataFacadeT> 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) { @@ -181,14 +181,16 @@ template <class DataFacadeT> 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; + const int weight = facade->GetEdgeData(edge_id, edge.first).distance; if ((facade->GetTarget(edge_id) == edge.second) && (weight < edge_weight) && - facade->GetEdgeData(edge_id).forward) + facade->GetEdgeData(edge_id, edge.first).forward) { smaller_edge_id = edge_id; + smaller_node_id = edge.first; edge_weight = weight; } } @@ -204,18 +206,19 @@ template <class DataFacadeT> class BasicRoutingInterface { for (const auto edge_id : facade->GetAdjacentEdgeRange(edge.second)) { - const int weight = facade->GetEdgeData(edge_id).distance; + const int weight = facade->GetEdgeData(edge_id, edge.second).distance; if ((facade->GetTarget(edge_id) == edge.first) && (weight < edge_weight) && - facade->GetEdgeData(edge_id).backward) + facade->GetEdgeData(edge_id, edge.second).backward) { smaller_edge_id = edge_id; + smaller_node_id = edge.second; edge_weight = weight; } } } 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; @@ -344,14 +347,16 @@ template <class DataFacadeT> 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; + const int weight = facade->GetEdgeData(edge_id, edge.first).distance; if ((facade->GetTarget(edge_id) == edge.second) && (weight < edge_weight) && - facade->GetEdgeData(edge_id).forward) + facade->GetEdgeData(edge_id, edge.first).forward) { smaller_edge_id = edge_id; + smaller_node_id = edge.first; edge_weight = weight; } } @@ -360,18 +365,19 @@ template <class DataFacadeT> class BasicRoutingInterface { for (const auto edge_id : facade->GetAdjacentEdgeRange(edge.second)) { - const int weight = facade->GetEdgeData(edge_id).distance; + const int weight = facade->GetEdgeData(edge_id, edge.second).distance; if ((facade->GetTarget(edge_id) == edge.first) && (weight < edge_weight) && - facade->GetEdgeData(edge_id).backward) + facade->GetEdgeData(edge_id, edge.second).backward) { smaller_edge_id = edge_id; + smaller_node_id = edge.second; edge_weight = weight; } } } 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/DataStructures/BaseDataFacade.h b/3party/osrm/osrm-backend/Server/DataStructures/BaseDataFacade.h index e0113c6fe6..0869cdc307 100644 --- a/3party/osrm/osrm-backend/Server/DataStructures/BaseDataFacade.h +++ b/3party/osrm/osrm-backend/Server/DataStructures/BaseDataFacade.h @@ -64,6 +64,8 @@ template <class EdgeDataT> class BaseDataFacade virtual EdgeDataT &GetEdgeData(const EdgeID e) = 0; + virtual EdgeDataT &GetEdgeData(const EdgeID e, NodeID node) { static EdgeDataT edge; return edge; } + // virtual const EdgeDataT &GetEdgeData( const EdgeID e ) const = 0; virtual EdgeID BeginEdges(const NodeID n) const = 0; diff --git a/3party/osrm/osrm-backend/mapsme/CMakeLists.txt b/3party/osrm/osrm-backend/mapsme/CMakeLists.txt index ab4df3944c..09fe32e968 100644 --- a/3party/osrm/osrm-backend/mapsme/CMakeLists.txt +++ b/3party/osrm/osrm-backend/mapsme/CMakeLists.txt @@ -1,5 +1,12 @@ file(GLOB_RECURSE SOURCES "*.cpp") file(GLOB_RECURSE HEADERS "*.hpp") -add_executable(osrm-mapsme ${SOURCES} ${HEADERS}) -target_link_libraries(osrm-mapsme ${Boost_LIBRARIES} FINGERPRINT GITDESCRIPTION COORDLIB) + +set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -DNDEBUG") + +add_executable(osrm-mapsme ${SOURCES} ${HEADERS} "${CMAKE_SOURCE_DIR}/../../succinct/rs_bit_vector.cpp") +target_link_libraries(osrm-mapsme ${Boost_LIBRARIES} FINGERPRINT GITDESCRIPTION COORDLIB + debug "${CMAKE_SOURCE_DIR}/../../../../omim-build-debug/out/debug/libcoding.a" + "${CMAKE_SOURCE_DIR}/../../../../omim-build-debug/out/debug/libbase.a" + general "${CMAKE_SOURCE_DIR}/../../../../omim-build-release/out/release/libcoding.a" + "${CMAKE_SOURCE_DIR}/../../../../omim-build-release/out/release/libbase.a") diff --git a/3party/osrm/osrm-backend/mapsme/converter.cpp b/3party/osrm/osrm-backend/mapsme/converter.cpp index dc67df2243..2f77c0ce18 100644 --- a/3party/osrm/osrm-backend/mapsme/converter.cpp +++ b/3party/osrm/osrm-backend/mapsme/converter.cpp @@ -6,7 +6,10 @@ #include "../DataStructures/QueryEdge.h" #include "../../../../coding/matrix_traversal.hpp" -//#include "../../../../routing/osrm_data_facade.hpp" +#include "../../../../coding/internal/file_data.hpp" +#include "../../../../base/bits.hpp" +#include "../../../../base/logging.hpp" +#include "../../../../routing/osrm_data_facade.hpp" #include "../../../succinct/elias_fano.hpp" #include "../../../succinct/elias_fano_compressed_list.hpp" @@ -71,7 +74,11 @@ void Converter::run(const std::string & name) edges.push_back(TraverseMatrixInRowOrder<uint64_t>(nodeCount, node, target, data.backward)); edgesData.push_back(d); shortcuts.push_back(data.shortcut); - edgeId.push_back(data.id); + + int id1 = data.id; + int id2 = node; + + edgeId.push_back(bits::ZigZagEncode(id2 - id1)); } } std::cout << "Edges count: " << edgeId.size() << std::endl; @@ -109,42 +116,42 @@ void Converter::run(const std::string & name) succinct::mapper::freeze(shortcutsVector, fileName.c_str()); /// @todo Restore this checking. Now data facade depends on mwm libraries. - /* + std::cout << "--- Test packed data" << std::endl; - routing::OsrmDataFacade<QueryEdge::EdgeData> facadeNew(name); + std::string fPath = name + ".mwm"; + + { + FilesContainerW routingCont(fPath); + + auto appendFile = [&] (string const & tag) + { + string const fileName = name + "." + tag; + LOG(LINFO, ("Append file", fileName, "with tag", 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(); + } + + + FilesMappingContainer container; + container.Open(fPath); + typedef routing::OsrmDataFacade<QueryEdge::EdgeData> DataFacadeT; + DataFacadeT facadeNew; + facadeNew.Load(container); std::cout << "Check node count " << facade.GetNumberOfNodes() << " == " << facadeNew.GetNumberOfNodes() << "..."; PrintStatus(facade.GetNumberOfNodes() == facadeNew.GetNumberOfNodes()); std::cout << "Check edges count " << facade.GetNumberOfEdges() << " == " << facadeNew.GetNumberOfEdges() << "..."; PrintStatus(facade.GetNumberOfEdges() == facadeNew.GetNumberOfEdges()); - std::cout << "Check edges data ..."; - bool error = false; - assert(facade.GetNumberOfEdges() == facadeNew.GetNumberOfEdges()); - for (uint32_t e = 0; e < facade.GetNumberOfEdges(); ++e) - { - QueryEdge::EdgeData d1 = facade.GetEdgeData(e); - QueryEdge::EdgeData d2 = facadeNew.GetEdgeData(e); - - if (d1.backward != d2.backward || - d1.forward != d2.forward || - d1.distance != d2.distance || - d1.id != d2.id || - d1.shortcut != d2.shortcut) - { - std::cout << "Edge num: " << e << std::endl; - std::cout << "d1 (backward: " << (uint32_t)d1.backward << ", forward: " << (uint32_t)d1.forward << ", distance: " - << (uint32_t)d1.distance << ", id: " << (uint32_t)d1.id << ", shortcut: " << (uint32_t)d1.shortcut << std::endl; - std::cout << "d2 (backward: " << (uint32_t)d2.backward << ", forward: " << (uint32_t)d2.forward << ", distance: " - << (uint32_t)d2.distance << ", id: " << (uint32_t)d2.id << ", shortcut: " << (uint32_t)d2.shortcut << std::endl; - error = true; - break; - } - } - PrintStatus(!error); - std::cout << "Check graph structure..."; - error = false; + bool error = false; for (uint32_t node = 0; node < facade.GetNumberOfNodes(); ++node) { EdgeRange r1 = facade.GetAdjacentEdgeRange(node); @@ -161,7 +168,42 @@ void Converter::run(const std::string & name) } } PrintStatus(!error); - */ + + std::cout << "Check edges data ..."; + error = false; + assert(facade.GetNumberOfEdges() == facadeNew.GetNumberOfEdges()); + for (uint32_t i = 0; i < facade.GetNumberOfNodes(); ++i) + { + for (auto e : facade.GetAdjacentEdgeRange(i)) + { + QueryEdge::EdgeData d1 = facade.GetEdgeData(e); + QueryEdge::EdgeData d2 = facadeNew.GetEdgeData(e, i); + + if (d1.backward != d2.backward || + d1.forward != d2.forward || + d1.distance != d2.distance || + d1.id != d2.id || + d1.shortcut != d2.shortcut) + { + stringstream ss; + ss << "File name: " << name << std::endl; + ss << "Edge num: " << e << std::endl; + ss << "d1 (backward: " << (uint32_t)d1.backward << ", forward: " << (uint32_t)d1.forward << ", distance: " + << (uint32_t)d1.distance << ", id: " << (uint32_t)d1.id << ", shortcut: " << (uint32_t)d1.shortcut << std::endl; + ss << "d2 (backward: " << (uint32_t)d2.backward << ", forward: " << (uint32_t)d2.forward << ", distance: " + << (uint32_t)d2.distance << ", id: " << (uint32_t)d2.id << ", shortcut: " << (uint32_t)d2.shortcut << std::endl; + error = true; + + my::DeleteFileX(fPath); + + LOG(LCRITICAL, (ss.str())); + break; + } + } + } + PrintStatus(!error); + + my::DeleteFileX(fPath); } } |