diff options
author | Denis Koronchik <denis@mapswithme.com> | 2014-10-10 18:06:50 +0400 |
---|---|---|
committer | Alex Zolotarev <alex@maps.me> | 2015-09-23 02:30:25 +0300 |
commit | ace4a01bb619abf93f89b68b376a3f3c42592b61 (patch) | |
tree | 88c5ea2b4cea6fda404d2c4e515eaffd7200d011 /3party/osrm | |
parent | 218c509c9ddcf6f6841316f7707889ab08bf6662 (diff) |
[routing] Improve compression. Forward/backward calculates from matrix
Diffstat (limited to '3party/osrm')
-rw-r--r-- | 3party/osrm/osrm-backend/mapsme/converter.cpp | 168 | ||||
-rw-r--r-- | 3party/osrm/osrm-backend/mapsme/converter.hpp | 28 |
2 files changed, 150 insertions, 46 deletions
diff --git a/3party/osrm/osrm-backend/mapsme/converter.cpp b/3party/osrm/osrm-backend/mapsme/converter.cpp index 3f15375ba3..441eb124bc 100644 --- a/3party/osrm/osrm-backend/mapsme/converter.cpp +++ b/3party/osrm/osrm-backend/mapsme/converter.cpp @@ -3,7 +3,6 @@ #include <iostream> #include "../Server/DataStructures/InternalDataFacade.h" -#include "../DataStructures/QueryEdge.h" #include "../../../../coding/matrix_traversal.hpp" #include "../../../../coding/internal/file_data.hpp" @@ -26,6 +25,13 @@ void PrintStatus(bool b) std::cout << (b ? "[Ok]" : "[Fail]") << std::endl; } +string EdgeDataToString(QueryEdge::EdgeData const & d) +{ + stringstream ss; + ss << "[" << d.distance << ", " << d.shortcut << ", " << d.forward << ", " << d.backward << ", " << d.id << "]"; + return ss.str(); +} + Converter::Converter() { @@ -53,36 +59,81 @@ void Converter::run(const std::string & name) std::vector<uint64_t> edges; std::vector<uint32_t> edgesData; std::vector<bool> shortcuts; - std::vector<uint32_t> edgeId; + std::vector<uint64_t> edgeId; std::cout << "Repack graph..."; + typedef pair<uint64_t, QueryEdge::EdgeData> EdgeInfoT; + typedef vector<EdgeInfoT> EdgeInfoVecT; + + uint64_t copiedEdges = 0; for (uint64_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)); + } + + auto compareFn = [](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 false; + }; + + sort(edgesInfo.begin(), edgesInfo.end(), compareFn); + /*std::cout << "---" << std::endl; + for (auto e : edgesInfo) + std::cout << e.first << ", " << EdgeDataToString(e.second) << std::endl;*/ + + uint64_t lastTarget = 0; + for (auto edge : edgesInfo) + { + uint64_t 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); - uint32_t d = data.distance; - d = d << 1; - d += data.forward ? 1 : 0; - d = d << 1; - d += data.backward ? 1 : 0; + auto addDataFn = [&](bool b) + { + uint64_t e = TraverseMatrixInRowOrder<uint64_t>(nodeCount, node, target, b); + if (!edges.empty() && (edges.back() >= e)) + LOG(LCRITICAL, ("Invalid order of edges", e, edges.back(), nodeCount, node, target, b)); + + edges.push_back(e); + edgesData.push_back(data.distance); + shortcuts.push_back(data.shortcut); - edges.push_back(TraverseMatrixInRowOrder<uint64_t>(nodeCount, node, target, data.backward)); - edgesData.push_back(d); - shortcuts.push_back(data.shortcut); + int id1 = data.id; + int id2 = node; - int id1 = data.id; - int id2 = node; + if (data.shortcut) + edgeId.push_back(bits::ZigZagEncode(id2 - id1)); + }; - if (data.shortcut) - edgeId.push_back(bits::ZigZagEncode(id2 - id1)); + if (data.forward && data.backward) + { + addDataFn(false); + addDataFn(true); + copiedEdges++; + } + else + addDataFn(data.backward); } } + std::cout << "Edges count: " << edgeId.size() << std::endl; PrintStatus(true); @@ -117,6 +168,9 @@ void Converter::run(const std::string & name) fileName = name + "." + ROUTING_SHORTCUTS_FILE_TAG; succinct::mapper::freeze(shortcutsVector, fileName.c_str()); + if (edgeId.size() != shortcutsVector.num_ones()) + LOG(LCRITICAL, ("Invalid data")); + /// @todo Restore this checking. Now data facade depends on mwm libraries. std::cout << "--- Test packed data" << std::endl; @@ -147,39 +201,63 @@ void Converter::run(const std::string & name) DataFacadeT facadeNew; facadeNew.Load(container); + uint64_t edgesCount = facadeNew.GetNumberOfEdges() - copiedEdges; 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 count " << facade.GetNumberOfEdges() << " == " << edgesCount << "..."; + PrintStatus(facade.GetNumberOfEdges() == edgesCount); - std::cout << "Check graph structure..."; + std::cout << "Check edges data ..."; bool error = false; - for (uint32_t node = 0; node < facade.GetNumberOfNodes(); ++node) - { - EdgeRange r1 = facade.GetAdjacentEdgeRange(node); - EdgeRange r2 = facadeNew.GetAdjacentEdgeRange(node); - if ((r1.front() != r2.front()) || (r1.back() != r2.back())) - { - std::cout << "Node num: " << node << std::endl; - std::cout << "r1 (" << r1.front() << ", " << r1.back() << ")" << std::endl; - std::cout << "r2 (" << r2.front() << ", " << r2.back() << ")" << std::endl; - - error = true; - break; - } - } - PrintStatus(!error); + auto errorFn = [&](string const & s) + { + my::DeleteFileX(fPath); + LOG(LCRITICAL, (s)); + }; - std::cout << "Check edges data ..."; - error = false; + typedef vector<QueryEdge::EdgeData> EdgeDataT; assert(facade.GetNumberOfEdges() == facadeNew.GetNumberOfEdges()); for (uint32_t i = 0; i < facade.GetNumberOfNodes(); ++i) { + EdgeDataT v1, v2; + for (auto e : facade.GetAdjacentEdgeRange(i)) { - QueryEdge::EdgeData d1 = facade.GetEdgeData(e); - QueryEdge::EdgeData d2 = facadeNew.GetEdgeData(e, i); + QueryEdge::EdgeData d = facade.GetEdgeData(e); + if (d.forward && d.backward) + { + d.backward = false; + v1.push_back(d); + d.forward = false; + d.backward = true; + } + + v1.push_back(d); + } + + for (auto e : facadeNew.GetAdjacentEdgeRange(i)) + v2.push_back(facadeNew.GetEdgeData(e, i)); + + if (v1.size() != v2.size()) + { + stringstream ss; + ss << "File name: " << name << std::endl; + ss << "Not equal edges count for node: " << i << std::endl; + ss << "v1: " << v1.size() << " v2: " << v2.size() << std::endl; + + errorFn(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) + { + QueryEdge::EdgeData const & d1 = v1[k]; + QueryEdge::EdgeData const & d2 = v2[k]; if (d1.backward != d2.backward || d1.forward != d2.forward || @@ -187,21 +265,19 @@ void Converter::run(const std::string & name) (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; + 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; + ss << "Node: " << i << std::endl; + ss << EdgeDataToString(d1) << ", " << EdgeDataToString(d2) << std::endl; - my::DeleteFileX(fPath); - - LOG(LCRITICAL, (ss.str())); - break; + errorFn(ss.str()); } } + } PrintStatus(!error); diff --git a/3party/osrm/osrm-backend/mapsme/converter.hpp b/3party/osrm/osrm-backend/mapsme/converter.hpp index f434c9a5ca..9d75340e10 100644 --- a/3party/osrm/osrm-backend/mapsme/converter.hpp +++ b/3party/osrm/osrm-backend/mapsme/converter.hpp @@ -2,11 +2,39 @@ #include <string> +#include "../DataStructures/QueryEdge.h" + namespace mapsme { +struct EdgeLess +{ + bool operator () (QueryEdge::EdgeData const & e1, QueryEdge::EdgeData const & e2) const + { + + if (e1.distance != e2.distance) + return e1.distance < e2.distance; + + if (e1.shortcut != e2.shortcut) + return e1.shortcut < e2.shortcut; + + if (e1.forward != e2.forward) + return e1.forward < e2.forward; + + if (e1.backward != e2.backward) + return e1.backward < e2.backward; + + if (e1.id != e2.id) + return e1.id < e2.id; + + return false; + } +}; + class Converter { + + public: Converter(); |