[routing] Improve compression. Forward/backward calculates from matrix

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();