Merge pull request #5618 from bykoianko/master-cross-mwm-GetEdgeListbeta-695

CrossMwmIndexGraph::GetEdgeList(...) implementation.

14 files changed, 377 insertions, 90 deletions

diff --git a/routing/car_router.cpp b/routing/car_router.cpp
index 4b92293e28..ba99f2dc96 100644
--- a/routing/car_router.cpp
+++ b/routing/car_router.cpp
@@ -401,9 +401,8 @@ CarRouter::ResultCode CarRouter::CalculateRoute(m2::PointD const & startPoint,
                                                 m2::PointD const & finalPoint,
                                                 RouterDelegate const & delegate, Route & route)
 {
-// TODO uncomment this to activate cross mwm index router.
-//  if (AllMwmsHaveRoutingIndex())
-//    return m_router->CalculateRoute(startPoint, startDirection, finalPoint, delegate, route);
+  if (AllMwmsHaveRoutingIndex())
+    return m_router->CalculateRoute(startPoint, startDirection, finalPoint, delegate, route);
 
   my::HighResTimer timer(true);
 
diff --git a/routing/cross_mwm_index_graph.cpp b/routing/cross_mwm_index_graph.cpp
index 7952f4f7ba..ed6dafdf0d 100644
--- a/routing/cross_mwm_index_graph.cpp
+++ b/routing/cross_mwm_index_graph.cpp
@@ -1,5 +1,8 @@
 #include "routing/cross_mwm_index_graph.hpp"
 
+#include "routing/cross_mwm_road_graph.hpp"
+#include "routing/osrm_path_segment_factory.hpp"
+
 #include "base/macros.hpp"
 #include "base/stl_helpers.hpp"
 
@@ -12,8 +15,40 @@ using namespace std;
 
 namespace
 {
-bool GetTransitionSegment(OsrmFtSegMapping const & segMapping, TWrittenNodeId nodeId,
-                          NumMwmId numMwmId, Segment & segment)
+struct NodeIds
+{
+  TOsrmNodeId m_directNodeId;
+  TOsrmNodeId m_reverseNodeId;
+};
+
+/// \returns FtSeg by |segment|.
+OsrmMappingTypes::FtSeg GetFtSeg(Segment const & segment)
+{
+  return OsrmMappingTypes::FtSeg(segment.GetFeatureId(), segment.GetMinPointId(),
+                                 segment.GetMaxPointId());
+}
+
+/// \returns a pair of direct and reverse(backward) node id by |segment|.
+/// The first member of the pair is direct node id and the second is reverse node id.
+NodeIds GetDirectAndReverseNodeId(OsrmFtSegMapping const & segMapping, Segment const & segment)
+{
+  OsrmFtSegMapping::TFtSegVec const ftSegs = {GetFtSeg(segment)};
+  OsrmFtSegMapping::OsrmNodesT osrmNodes;
+  segMapping.GetOsrmNodes(ftSegs, osrmNodes);
+  CHECK_LESS(osrmNodes.size(), 2, ());
+  if (osrmNodes.empty())
+    return {INVALID_NODE_ID, INVALID_NODE_ID};
+
+  NodeIds const forwardNodeIds = {osrmNodes.begin()->second.first,
+                                  osrmNodes.begin()->second.second};
+  NodeIds const backwardNodeIds = {osrmNodes.begin()->second.second,
+                                   osrmNodes.begin()->second.first};
+
+  return segment.IsForward() ? forwardNodeIds : backwardNodeIds;
+}
+
+bool GetFirstValidSegment(OsrmFtSegMapping const & segMapping, NumMwmId numMwmId,
+                          TWrittenNodeId nodeId, Segment & segment)
 {
   auto const range = segMapping.GetSegmentsRange(nodeId);
   for (size_t segmentIndex = range.first; segmentIndex != range.second; ++segmentIndex)
@@ -22,6 +57,7 @@ bool GetTransitionSegment(OsrmFtSegMapping const & segMapping, TWrittenNodeId no
     // The meaning of node id in osrm is an edge between two joints.
     // So, it's possible to consider the first valid segment from the range which returns by GetSegmentsRange().
     segMapping.GetSegmentByIndex(segmentIndex, seg);
+
     if (!seg.IsValid())
       continue;
 
@@ -29,75 +65,107 @@ bool GetTransitionSegment(OsrmFtSegMapping const & segMapping, TWrittenNodeId no
     segment = Segment(numMwmId, seg.m_fid, min(seg.m_pointStart, seg.m_pointEnd), seg.IsForward());
     return true;
   }
-  LOG(LERROR, ("No valid segments in the range returned by OsrmFtSegMapping::GetSegmentsRange(", nodeId,
-               "). Num mwm id:", numMwmId));
+  LOG(LDEBUG, ("No valid segments in the range returned by OsrmFtSegMapping::GetSegmentsRange(",
+               nodeId, "). Num mwm id:", numMwmId));
   return false;
 }
 
-void AddTransitionSegment(OsrmFtSegMapping const & segMapping, TWrittenNodeId nodeId,
-                          NumMwmId numMwmId, std::vector<Segment> & segments)
+void AddFirstValidSegment(OsrmFtSegMapping const & segMapping, NumMwmId numMwmId,
+                          TWrittenNodeId nodeId, vector<Segment> & segments)
 {
   Segment key;
-  if (GetTransitionSegment(segMapping, nodeId, numMwmId, key))
+  if (GetFirstValidSegment(segMapping, numMwmId, nodeId, key))
     segments.push_back(key);
 }
 
 void FillTransitionSegments(OsrmFtSegMapping const & segMapping, TWrittenNodeId nodeId,
                             NumMwmId numMwmId, ms::LatLon const & latLon,
-                            std::map<Segment, ms::LatLon> & transitionSegments)
+                            map<Segment, vector<ms::LatLon>> & transitionSegments)
 {
   Segment key;
-  if (!GetTransitionSegment(segMapping, nodeId, numMwmId, key))
-    return;
-
-  auto const p = transitionSegments.emplace(key, latLon);
-  if (p.second)
+  if (!GetFirstValidSegment(segMapping, numMwmId, nodeId, key))
     return;
 
-  // @TODO(bykoianko) It's necessary to investigate this case.
-  LOG(LWARNING, ("Trying to insert a transition segment that was previously inserted. The key:",
-                 *p.first, ", the value:", latLon));
+  transitionSegments[key].push_back(latLon);
 }
 
-ms::LatLon const & GetLatLon(std::map<Segment, ms::LatLon> const & segMap, Segment const & s)
+vector<ms::LatLon> const & GetLatLon(map<Segment, vector<ms::LatLon>> const & segMap,
+                                     Segment const & s)
 {
   auto it = segMap.find(s);
   CHECK(it != segMap.cend(), ());
   return it->second;
 }
+
+void AddSegmentEdge(NumMwmIds const & numMwmIds, OsrmFtSegMapping const & segMapping,
+                    CrossWeightedEdge const & osrmEdge, bool isOutgoing, NumMwmId numMwmId,
+                    vector<SegmentEdge> & edges)
+{
+  BorderCross const & target = osrmEdge.GetTarget();
+  CrossNode const & crossNode = isOutgoing ? target.fromNode : target.toNode;
+
+  if (!crossNode.mwmId.IsAlive())
+    return;
+
+  NumMwmId const crossNodeMwmId =
+      numMwmIds.GetId(crossNode.mwmId.GetInfo()->GetLocalFile().GetCountryFile());
+  CHECK_EQUAL(numMwmId, crossNodeMwmId, ());
+
+  Segment segment;
+  if (!GetFirstValidSegment(segMapping, crossNodeMwmId, crossNode.node, segment))
+    return;
+
+  // OSRM and AStar have different car models, therefore AStar heuristic doesn't work for OSRM node
+  // ids (edges).
+  // This factor makes index graph (used in AStar) edge weight smaller than node ids weight.
+  //
+  // As a result large cross mwm routes with connectors works as Dijkstra, but short and medium routes
+  // without connectors works as AStar.
+  // Most of routes don't use leaps, therefore it is important to keep AStar performance.
+  double constexpr kAstarHeuristicFactor = 100000;
+  edges.emplace_back(segment,
+                     osrmEdge.GetWeight() * kOSRMWeightToSecondsMultiplier * kAstarHeuristicFactor);
+}
 }  // namespace
 
 namespace routing
 {
+CrossMwmIndexGraph::CrossMwmIndexGraph(shared_ptr<NumMwmIds> numMwmIds,
+                                       RoutingIndexManager & indexManager)
+  : m_indexManager(indexManager), m_numMwmIds(numMwmIds)
+{
+  ResetCrossMwmGraph();
+}
+
+CrossMwmIndexGraph::~CrossMwmIndexGraph() {}
+
 bool CrossMwmIndexGraph::IsTransition(Segment const & s, bool isOutgoing)
 {
   // @TODO(bykoianko) It's necessary to check if mwm of |s| contains an A* cross mwm section
   // and if so to use it. If not, osrm cross mwm sections should be used.
 
   // Checking if a segment |s| is a transition segment by osrm cross mwm sections.
-  auto it = m_transitionCache.find(s.GetMwmId());
-  if (it == m_transitionCache.cend())
-  {
-    InsertWholeMwmTransitionSegments(s.GetMwmId());
-    it = m_transitionCache.find(s.GetMwmId());
-  }
-  CHECK(it != m_transitionCache.cend(),
-        ("Mwm ", s.GetMwmId(), "has not been downloaded. s:", s, ". isOutgoing", isOutgoing));
+  TransitionSegments const & t = GetSegmentMaps(s.GetMwmId());
 
   if (isOutgoing)
-    return it->second.m_outgoing.count(s) != 0;
-  return it->second.m_ingoing.count(s) != 0;
+    return t.m_outgoing.count(s) != 0;
+  return t.m_ingoing.count(s) != 0;
 }
 
-void CrossMwmIndexGraph::GetTwins(Segment const & s, bool isOutgoing, std::vector<Segment> & twins)
+void CrossMwmIndexGraph::GetTwins(Segment const & s, bool isOutgoing, vector<Segment> & twins)
 {
-  CHECK(IsTransition(s, isOutgoing), ("The segment is not a transition segment."));
+  CHECK(IsTransition(s, isOutgoing), ("The segment", s, "is not a transition segment for isOutgoing ==", isOutgoing));
+  // Note. There's an extremely rare case when a segment is ingoing and outgoing at the same time.
+  // |twins| is not filled for such cases. For details please see a note in
+  // rossMwmIndexGraph::GetEdgeList().
+  if (IsTransition(s, !isOutgoing))
+    return;
+
   twins.clear();
   // @TODO(bykoianko) It's necessary to check if mwm of |s| contains an A* cross mwm section
   // and if so to use it. If not, osrm cross mwm sections should be used.
 
-  auto const getTwins = [&](NumMwmId /* numMwmId */, TRoutingMappingPtr const & segMapping)
-  {
+  auto const getTwins = [&](TRoutingMappingPtr const & segMapping) {
     vector<string> const & neighboringMwm = segMapping->m_crossContext.GetNeighboringMwmList();
 
     for (string const & name : neighboringMwm)
@@ -106,46 +174,97 @@ void CrossMwmIndexGraph::GetTwins(Segment const & s, bool isOutgoing, std::vecto
     auto it = m_transitionCache.find(s.GetMwmId());
     CHECK(it != m_transitionCache.cend(), ());
 
-    ms::LatLon const & latLon = isOutgoing ? GetLatLon(it->second.m_outgoing, s)
-                                           : GetLatLon(it->second.m_ingoing, s);
+    vector<ms::LatLon> const & latLons =
+        isOutgoing ? GetLatLon(it->second.m_outgoing, s) : GetLatLon(it->second.m_ingoing, s);
     for (string const & name : neighboringMwm)
     {
-      auto const addTransitionSegments = [&](NumMwmId numMwmId, TRoutingMappingPtr const & mapping)
-      {
-        if (isOutgoing)
-        {
-          mapping->m_crossContext.ForEachIngoingNodeNearPoint(latLon, [&](IngoingCrossNode const & node){
-            AddTransitionSegment(mapping->m_segMapping, node.m_nodeId, numMwmId, twins);
-          });
-        }
-        else
+      NumMwmId const numMwmId = m_numMwmIds->GetId(CountryFile(name));
+      auto const addFirstValidSegment = [&](TRoutingMappingPtr const & mapping) {
+        for (auto const & ll : latLons)
         {
-          mapping->m_crossContext.ForEachOutgoingNodeNearPoint(latLon, [&](OutgoingCrossNode const & node){
-            AddTransitionSegment(mapping->m_segMapping, node.m_nodeId, numMwmId, twins);
-          });
+          if (isOutgoing)
+          {
+            mapping->m_crossContext.ForEachIngoingNodeNearPoint(
+                ll, [&](IngoingCrossNode const & node) {
+                  AddFirstValidSegment(mapping->m_segMapping, numMwmId, node.m_nodeId, twins);
+                });
+          }
+          else
+          {
+            mapping->m_crossContext.ForEachOutgoingNodeNearPoint(
+                ll, [&](OutgoingCrossNode const & node) {
+                  AddFirstValidSegment(mapping->m_segMapping, numMwmId, node.m_nodeId, twins);
+                });
+          }
         }
       };
 
-      if (!LoadWith(m_numMwmIds->GetId(CountryFile(name)), addTransitionSegments))
+      if (!LoadWith(numMwmId, addFirstValidSegment))
         continue;  // mwm was not loaded.
     }
   };
 
   LoadWith(s.GetMwmId(), getTwins);
   my::SortUnique(twins);
+
+  for (Segment const & t : twins)
+    CHECK_NOT_EQUAL(s.GetMwmId(), t.GetMwmId(), ());
 }
 
-void CrossMwmIndexGraph::GetEdgeList(Segment const & /* s */,
-                                     bool /* isOutgoing */, std::vector<SegmentEdge> & /* edges */) const
+void CrossMwmIndexGraph::GetEdgeList(Segment const & s, bool isOutgoing,
+                                     vector<SegmentEdge> & edges)
 {
   // @TODO(bykoianko) It's necessary to check if mwm of |s| contains an A* cross mwm section
   // and if so to use it. If not, osrm cross mwm sections should be used.
-  NOTIMPLEMENTED();
+
+  CHECK(IsTransition(s, !isOutgoing), ("The segment is not a transition segment. IsTransition(",
+                                       s, ",", !isOutgoing, ") returns false."));
+
+  // Note. According to cross-mwm OSRM sections there're node id which could be ingoing and outgoing
+  // at the same time. For example in Berlin mwm on Nordlicher Berliner Ring (A10) near crossing
+  // with A11
+  // there's such node id. It's an extremely rare case. There're probably several such node id
+  // for the whole Europe. Such cases are not processed in WorldGraph::GetEdgeList() for the time
+  // being.
+  // To prevent filling |edges| with twins instead of leap edges and vice versa in
+  // WorldGraph::GetEdgeList()
+  // CrossMwmIndexGraph::GetEdgeList() does not fill |edges| if |s| is a transition segment which
+  // corresponces node id described above.
+  if (IsTransition(s, isOutgoing))
+    return;
+
+  edges.clear();
+  auto const fillEdgeList = [&](TRoutingMappingPtr const & mapping) {
+    vector<BorderCross> borderCrosses;
+    GetBorderCross(mapping, s, isOutgoing, borderCrosses);
+
+    for (BorderCross const & v : borderCrosses)
+    {
+      vector<CrossWeightedEdge> adj;
+      if (isOutgoing)
+        m_crossMwmGraph->GetOutgoingEdgesList(v, adj);
+      else
+        m_crossMwmGraph->GetIngoingEdgesList(v, adj);
+
+      for (CrossWeightedEdge const & edge : adj)
+        AddSegmentEdge(*m_numMwmIds, mapping->m_segMapping, edge, isOutgoing, s.GetMwmId(), edges);
+    }
+  };
+  LoadWith(s.GetMwmId(), fillEdgeList);
+
+  my::SortUnique(edges);
 }
 
 void CrossMwmIndexGraph::Clear()
 {
+  ResetCrossMwmGraph();
   m_transitionCache.clear();
+  m_mappingGuards.clear();
+}
+
+void CrossMwmIndexGraph::ResetCrossMwmGraph()
+{
+  m_crossMwmGraph = make_unique<CrossMwmGraph>(m_indexManager);
 }
 
 void CrossMwmIndexGraph::InsertWholeMwmTransitionSegments(NumMwmId numMwmId)
@@ -153,7 +272,7 @@ void CrossMwmIndexGraph::InsertWholeMwmTransitionSegments(NumMwmId numMwmId)
   if (m_transitionCache.count(numMwmId) != 0)
     return;
 
-  auto const fillAllTransitionSegments = [this](NumMwmId numMwmId, TRoutingMappingPtr const & mapping){
+  auto const fillAllTransitionSegments = [&](TRoutingMappingPtr const & mapping) {
     TransitionSegments transitionSegments;
     mapping->m_crossContext.ForEachOutgoingNode([&](OutgoingCrossNode const & node)
     {
@@ -174,4 +293,84 @@ void CrossMwmIndexGraph::InsertWholeMwmTransitionSegments(NumMwmId numMwmId)
   if (!LoadWith(numMwmId, fillAllTransitionSegments))
     m_transitionCache.emplace(numMwmId, TransitionSegments());
 }
+
+void CrossMwmIndexGraph::GetBorderCross(TRoutingMappingPtr const & mapping, Segment const & s,
+                                        bool isOutgoing, vector<BorderCross> & borderCrosses)
+{
+  // ingoing edge
+  NodeIds const nodeIdsTo = GetDirectAndReverseNodeId(mapping->m_segMapping, s);
+
+  vector<ms::LatLon> const & transitionPoints =
+      isOutgoing ? GetIngoingTransitionPoints(s) : GetOutgoingTransitionPoints(s);
+  CHECK(!transitionPoints.empty(), ("Segment:", s, ", isOutgoing:", isOutgoing));
+
+  // If |isOutgoing| == true |nodes| is "to" cross nodes, otherwise |nodes| is "from" cross nodes.
+  vector<CrossNode> nodes;
+  for (ms::LatLon const & p : transitionPoints)
+    nodes.emplace_back(nodeIdsTo.m_directNodeId, nodeIdsTo.m_reverseNodeId, mapping->GetMwmId(), p);
+
+  // outgoing edge
+  vector<Segment> twins;
+  GetTwins(s, !isOutgoing, twins);
+  CHECK(!twins.empty(), ("Segment:", s, ", isOutgoing:", isOutgoing));
+  for (Segment const & twin : twins)
+  {
+    // If |isOutgoing| == true |otherSideMapping| is mapping outgoing (to) border cross.
+    // If |isOutgoing| == false |mapping| is mapping ingoing (from) border cross.
+    auto const fillBorderCrossOut = [&](TRoutingMappingPtr const & otherSideMapping) {
+      NodeIds const nodeIdsFrom = GetDirectAndReverseNodeId(otherSideMapping->m_segMapping, twin);
+      vector<ms::LatLon> const & otherSideTransitionPoints =
+          isOutgoing ? GetOutgoingTransitionPoints(twin) : GetIngoingTransitionPoints(twin);
+
+      CHECK(!otherSideTransitionPoints.empty(), ("Segment:", s, ", isOutgoing:", isOutgoing));
+      for (CrossNode const & node : nodes)
+      {
+        // If |isOutgoing| == true |otherSideNodes| is "from" cross nodes, otherwise
+        // |otherSideNodes| is "to" cross nodes.
+        BorderCross bc;
+        if (isOutgoing)
+          bc.toNode = node;
+        else
+          bc.fromNode = node;
+
+        for (ms::LatLon const & ll : otherSideTransitionPoints)
+        {
+          CrossNode & resultNode = isOutgoing ? bc.fromNode : bc.toNode;
+          resultNode = CrossNode(nodeIdsFrom.m_directNodeId, nodeIdsFrom.m_reverseNodeId,
+                                 otherSideMapping->GetMwmId(), ll);
+          borderCrosses.push_back(bc);
+        }
+      }
+    };
+    LoadWith(twin.GetMwmId(), fillBorderCrossOut);
+  }
+}
+
+CrossMwmIndexGraph::TransitionSegments const & CrossMwmIndexGraph::GetSegmentMaps(NumMwmId numMwmId)
+{
+  auto it = m_transitionCache.find(numMwmId);
+  if (it == m_transitionCache.cend())
+  {
+    InsertWholeMwmTransitionSegments(numMwmId);
+    it = m_transitionCache.find(numMwmId);
+  }
+  CHECK(it != m_transitionCache.cend(), ("Mwm ", numMwmId, "has not been downloaded."));
+  return it->second;
+}
+
+vector<ms::LatLon> const & CrossMwmIndexGraph::GetIngoingTransitionPoints(Segment const & s)
+{
+  auto const & ingoingSeg = GetSegmentMaps(s.GetMwmId()).m_ingoing;
+  auto const it = ingoingSeg.find(s);
+  CHECK(it != ingoingSeg.cend(), ("Segment:", s));
+  return it->second;
+}
+
+vector<ms::LatLon> const & CrossMwmIndexGraph::GetOutgoingTransitionPoints(Segment const & s)
+{
+  auto const & outgoingSeg = GetSegmentMaps(s.GetMwmId()).m_outgoing;
+  auto const it = outgoingSeg.find(s);
+  CHECK(it != outgoingSeg.cend(), ("Segment:", s));
+  return it->second;
+}
 }  // namespace routing
diff --git a/routing/cross_mwm_index_graph.hpp b/routing/cross_mwm_index_graph.hpp
index af0aa2515a..053c7e2d78 100644
--- a/routing/cross_mwm_index_graph.hpp
+++ b/routing/cross_mwm_index_graph.hpp
@@ -16,14 +16,15 @@
 
 namespace routing
 {
+struct BorderCross;
+class CrossMwmGraph;
+
 /// \brief Getting information for cross mwm routing.
 class CrossMwmIndexGraph final
 {
 public:
-  CrossMwmIndexGraph(std::shared_ptr<NumMwmIds> numMwmIds, RoutingIndexManager & indexManager)
-    : m_indexManager(indexManager), m_numMwmIds(numMwmIds)
-  {
-  }
+  CrossMwmIndexGraph(std::shared_ptr<NumMwmIds> numMwmIds, RoutingIndexManager & indexManager);
+  ~CrossMwmIndexGraph();
 
   /// \brief Transition segment is a segment which is crossed by mwm border. That means
   /// start and finsh of such segment have to lie in different mwms. If a segment is
@@ -72,21 +73,36 @@ public:
   /// enter transition segments of the mwm of |s| and ending at |s|.
   /// Weight of each edge is equal to weight of the route form |s| to |SegmentEdge::m_target|
   /// if |isOutgoing| == true and from |SegmentEdge::m_target| to |s| otherwise.
-  void GetEdgeList(Segment const & s, bool isOutgoing, std::vector<SegmentEdge> & edges) const;
+  void GetEdgeList(Segment const & s, bool isOutgoing, std::vector<SegmentEdge> & edges);
 
   void Clear();
 
 private:
   struct TransitionSegments
   {
-    std::map<Segment, ms::LatLon> m_ingoing;
-    std::map<Segment, ms::LatLon> m_outgoing;
+    std::map<Segment, std::vector<ms::LatLon>> m_ingoing;
+    std::map<Segment, std::vector<ms::LatLon>> m_outgoing;
   };
 
+  void ResetCrossMwmGraph();
+
   /// \brief Inserts all ingoing and outgoing transition segments of mwm with |numMwmId|
   /// to |m_transitionCache|.
   void InsertWholeMwmTransitionSegments(NumMwmId numMwmId);
 
+  /// \brief Fills |borderCrosses| of mwm with |mapping| according to |s|.
+  /// \param mapping if |isOutgoing| == true |mapping| is mapping ingoing (from) border cross.
+  /// If |isOutgoing| == false |mapping| is mapping outgoing (to) border cross.
+  /// \note |s| and |isOutgoing| params have the same restrictions which described in
+  /// GetEdgeList() method.
+  void GetBorderCross(TRoutingMappingPtr const & mapping, Segment const & s, bool isOutgoing,
+                      std::vector<BorderCross> & borderCrosses);
+
+  TransitionSegments const & GetSegmentMaps(NumMwmId numMwmId);
+
+  std::vector<ms::LatLon> const & GetIngoingTransitionPoints(Segment const & s);
+  std::vector<ms::LatLon> const & GetOutgoingTransitionPoints(Segment const & s);
+
   template <class Fn>
   bool LoadWith(NumMwmId numMwmId, Fn && fn)
   {
@@ -97,15 +113,26 @@ private:
     if (!mapping->IsValid())
       return false; // mwm was not loaded.
 
-    MappingGuard mappingGuard(mapping);
-    mapping->LoadCrossContext();
-    fn(numMwmId, mapping);
+    auto const it = m_mappingGuards.find(numMwmId);
+    if (it == m_mappingGuards.cend())
+    {
+      m_mappingGuards[numMwmId] = make_unique<MappingGuard>(mapping);
+      mapping->LoadCrossContext();
+    }
+
+    fn(mapping);
     return true;
   }
 
   RoutingIndexManager & m_indexManager;
   std::shared_ptr<NumMwmIds> m_numMwmIds;
+  /// \note According to the constructor CrossMwmGraph is initialized with RoutingIndexManager &.
+  /// But then it is copied by value to CrossMwmGraph::RoutingIndexManager m_indexManager.
+  /// It means that there're two copies of RoutingIndexManager in CrossMwmIndexGraph.
+  std::unique_ptr<CrossMwmGraph> m_crossMwmGraph;
 
   std::map<NumMwmId, TransitionSegments> m_transitionCache;
+
+  std::map<NumMwmId, std::unique_ptr<MappingGuard>> m_mappingGuards;
 };
 }  // routing
diff --git a/routing/cross_mwm_road_graph.cpp b/routing/cross_mwm_road_graph.cpp
index fc2936f9a0..e3f048c859 100644
--- a/routing/cross_mwm_road_graph.cpp
+++ b/routing/cross_mwm_road_graph.cpp
@@ -92,28 +92,33 @@ private:
 };
 
 bool ForEachNodeNearPoint(CrossRoutingContextReader const & currentContext,
-                          CrossNode const & crossNode,
+                          ms::LatLon const & point,
                           ClosestNodeFinder<IngoingCrossNode> const & findingNode)
 {
-  return currentContext.ForEachIngoingNodeNearPoint(crossNode.point, findingNode);
+  return currentContext.ForEachIngoingNodeNearPoint(point, findingNode);
 }
 
 bool ForEachNodeNearPoint(CrossRoutingContextReader const & currentContext,
-                          CrossNode const & crossNode,
+                          ms::LatLon const & point,
                           ClosestNodeFinder<OutgoingCrossNode> const & findingNode)
 {
-  return currentContext.ForEachOutgoingNodeNearPoint(crossNode.point, findingNode);
+  return currentContext.ForEachOutgoingNodeNearPoint(point, findingNode);
 }
 
 template <class Node>
-void FindCrossNode(CrossRoutingContextReader const & currentContext, CrossNode const & crossNode,
+bool FindCrossNode(CrossRoutingContextReader const & currentContext, CrossNode const & crossNode,
                    Node & node)
 {
-  double minDistance = std::numeric_limits<double>::max();
+  double constexpr kInvalidDistance = std::numeric_limits<double>::max();
+  double minDistance = kInvalidDistance;
   ClosestNodeFinder<Node> findingNode(crossNode, minDistance, node);
-  CHECK(ForEachNodeNearPoint(currentContext, crossNode, findingNode), ());
-  CHECK_NOT_EQUAL(minDistance, std::numeric_limits<double>::max(),
-                  ("crossNode.point:", crossNode.point));
+  CHECK(ForEachNodeNearPoint(currentContext, crossNode.point, findingNode), ());
+  if (minDistance == kInvalidDistance)
+  {
+    LOG(LWARNING, ("Cross node is not found. Point:", crossNode.point));
+    return false;
+  }
+  return true;
 }
 
 template <class Fn>
@@ -121,7 +126,7 @@ vector<BorderCross> const & ConstructBorderCrossImpl(
     TWrittenNodeId nodeId, TRoutingMappingPtr const & currentMapping,
     unordered_map<CrossMwmGraph::TCachingKey, vector<BorderCross>, CrossMwmGraph::Hash> const &
         cachedNextNodes,
-    Fn && borderCrossConstructor /*bool & result*/)
+    Fn && borderCrossConstructor)
 {
   auto const key = make_pair(nodeId, currentMapping->GetMwmId());
   auto const it = cachedNextNodes.find(key);
@@ -180,6 +185,7 @@ IRouter::ResultCode CrossMwmGraph::SetStartNode(CrossNode const & startNode)
     {
       vector<BorderCross> const & nextCrosses =
           ConstructBorderCross(startMapping, outgoingNodes[i]);
+
       for (auto const & nextCross : nextCrosses)
       {
         if (nextCross.toNode.IsValid())
@@ -380,14 +386,22 @@ void CrossMwmGraph::GetEdgesList(BorderCross const & v, bool isOutgoing,
   if (isOutgoing)
   {
     IngoingCrossNode ingoingNode;
-    FindCrossNode<IngoingCrossNode>(currentContext, v.toNode, ingoingNode);
+    if (!FindCrossNode<IngoingCrossNode>(currentContext, v.toNode, ingoingNode))
+      return;
+    if (!ingoingNode.IsValid())
+      return;
+
     currentContext.ForEachOutgoingNode(EdgesFiller<IngoingCrossNode, OutgoingCrossNode>(
         currentMapping, currentContext, ingoingNode, *this, adj));
   }
   else
   {
     OutgoingCrossNode outgoingNode;
-    FindCrossNode<OutgoingCrossNode>(currentContext, v.fromNode, outgoingNode);
+    if (!FindCrossNode<OutgoingCrossNode>(currentContext, v.fromNode, outgoingNode))
+      return;
+    if (!outgoingNode.IsValid())
+      return;
+
     currentContext.ForEachIngoingNode(EdgesFiller<OutgoingCrossNode, IngoingCrossNode>(
         currentMapping, currentContext, outgoingNode, *this, adj));
   }
diff --git a/routing/cross_mwm_road_graph.hpp b/routing/cross_mwm_road_graph.hpp
index b6f289adf4..fa9765f557 100644
--- a/routing/cross_mwm_road_graph.hpp
+++ b/routing/cross_mwm_road_graph.hpp
@@ -1,6 +1,7 @@
 #pragma once
 
 #include "routing/car_router.hpp"
+#include "routing/cross_mwm_router.hpp"
 #include "routing/osrm_engine.hpp"
 #include "routing/router.hpp"
 
@@ -17,7 +18,7 @@
 namespace routing
 {
 /// OSRM graph node representation with graph mwm name and border crossing point.
-struct CrossNode
+struct CrossNode final
 {
   NodeID node;
   NodeID reverseNode;
@@ -64,7 +65,7 @@ inline string DebugPrint(CrossNode const & t)
 }
 
 /// Representation of border crossing. Contains node on previous map and node on next map.
-struct BorderCross
+struct BorderCross final
 {
   CrossNode fromNode;
   CrossNode toNode;
@@ -74,6 +75,7 @@ struct BorderCross
 
   // TODO(bykoianko) Consider using fields |fromNode| and |toNode| in operator== and operator<.
   inline bool operator==(BorderCross const & a) const { return toNode == a.toNode; }
+  inline bool operator!=(BorderCross const & a) const { return !(*this == a); }
   inline bool operator<(BorderCross const & a) const { return toNode < a.toNode; }
 };
 
@@ -85,21 +87,35 @@ inline string DebugPrint(BorderCross const & t)
 }
 
 /// A class which represents an cross mwm weighted edge used by CrossMwmGraph.
-class CrossWeightedEdge
+class CrossWeightedEdge final
 {
 public:
-  CrossWeightedEdge(BorderCross const & target, double weight) : target(target), weight(weight) {}
+  CrossWeightedEdge(BorderCross const & target, double weight) : m_target(target), m_weight(weight)
+  {
+  }
+
+  BorderCross const & GetTarget() const { return m_target; }
+  double GetWeight() const { return m_weight; }
+
+  bool operator==(CrossWeightedEdge const & a) const
+  {
+    return m_target == a.m_target && m_weight == a.m_weight;
+  }
 
-  inline BorderCross const & GetTarget() const { return target; }
-  inline double GetWeight() const { return weight; }
+  bool operator<(CrossWeightedEdge const & a) const
+  {
+    if (m_target != a.m_target)
+      return m_target < a.m_target;
+    return m_weight < a.m_weight;
+  }
 
 private:
-  BorderCross target;
-  double weight;
+  BorderCross m_target;
+  double m_weight;
 };
 
 /// A graph used for cross mwm routing in an astar algorithms.
-class CrossMwmGraph
+class CrossMwmGraph final
 {
 public:
   using TCachingKey = pair<TWrittenNodeId, Index::MwmId>;
diff --git a/routing/cross_routing_context.hpp b/routing/cross_routing_context.hpp
index ec2bde2dde..69be60be80 100644
--- a/routing/cross_routing_context.hpp
+++ b/routing/cross_routing_context.hpp
@@ -34,11 +34,14 @@ struct IngoingCrossNode
     , m_adjacencyIndex(kInvalidAdjacencyIndex)
   {
   }
+
   IngoingCrossNode(TWrittenNodeId nodeId, ms::LatLon const & point, size_t const adjacencyIndex)
     : m_point(point), m_nodeId(nodeId), m_adjacencyIndex(adjacencyIndex)
   {
   }
 
+  bool IsValid() const { return m_nodeId != kInvalidContextEdgeNodeId; }
+
   void Save(Writer & w) const;
 
   size_t Load(Reader const & r, size_t pos, size_t adjacencyIndex);
@@ -60,6 +63,7 @@ struct OutgoingCrossNode
     , m_adjacencyIndex(kInvalidAdjacencyIndex)
   {
   }
+
   OutgoingCrossNode(TWrittenNodeId nodeId, size_t const index, ms::LatLon const & point,
                     size_t const adjacencyIndex)
     : m_point(point)
@@ -69,6 +73,8 @@ struct OutgoingCrossNode
   {
   }
 
+  bool IsValid() const { return m_nodeId != kInvalidContextEdgeNodeId; }
+
   void Save(Writer & w) const;
 
   size_t Load(Reader const & r, size_t pos, size_t adjacencyIndex);
diff --git a/routing/index_router.cpp b/routing/index_router.cpp
index 053b78f191..246caba3b0 100644
--- a/routing/index_router.cpp
+++ b/routing/index_router.cpp
@@ -238,8 +238,10 @@ IRouter::ResultCode IndexRouter::ProcessLeaps(vector<Segment> const & input,
     ++i;
     CHECK_LESS(i, input.size(), ());
     Segment const & next = input[i];
-    CHECK_EQUAL(current.GetMwmId(), next.GetMwmId(),
-                ("Different mwm ids for leap enter and exit, i:", i));
+
+    CHECK_EQUAL(
+        current.GetMwmId(), next.GetMwmId(),
+        ("Different mwm ids for leap enter and exit, i:", i, "size of input:", input.size()));
 
     IndexGraphStarter::FakeVertex const start(current, starter.GetPoint(current, true /* front */));
     IndexGraphStarter::FakeVertex const finish(next, starter.GetPoint(next, true /* front */));
diff --git a/routing/osrm2feature_map.hpp b/routing/osrm2feature_map.hpp
index 261f601db7..9813743096 100644
--- a/routing/osrm2feature_map.hpp
+++ b/routing/osrm2feature_map.hpp
@@ -166,6 +166,11 @@ public:
   /// @name For unit test purpose only.
   //@{
   /// @return STL-like range [s, e) of segments indexies for passed node.
+  /// @note Methods GetSegmentsRange(...) and GetOsrmNodes(...) are not symmetric.
+  /// For example in Tverskay Oblast for node id 161179 two FtSet can be gotten
+  /// with GetSegmentsRange() / GetSegmentByIndex().
+  /// But having these segments it's impossible to get node id 161179 with the help of
+  /// GetOsrmNodes(...).
   pair<size_t, size_t> GetSegmentsRange(TOsrmNodeId nodeId) const;
   /// @return Node id for segment's index.
   TOsrmNodeId GetNodeId(uint32_t segInd) const;
diff --git a/routing/osrm_engine.hpp b/routing/osrm_engine.hpp
index 152f984490..a87f043c7b 100644
--- a/routing/osrm_engine.hpp
+++ b/routing/osrm_engine.hpp
@@ -43,7 +43,7 @@ struct FeatureGraphNode
 struct RawPathData
 {
   NodeID node;
-  EdgeWeight segmentWeight;
+  EdgeWeight segmentWeight;  // Time in tenths of a second to pass |node|.
 
   RawPathData() : node(SPECIAL_NODEID), segmentWeight(INVALID_EDGE_WEIGHT) {}
 
diff --git a/routing/osrm_path_segment_factory.cpp b/routing/osrm_path_segment_factory.cpp
index 15261f9bf8..eb301e7d85 100644
--- a/routing/osrm_path_segment_factory.cpp
+++ b/routing/osrm_path_segment_factory.cpp
@@ -12,9 +12,6 @@
 
 namespace
 {
-// Osrm multiples seconds to 10, so we need to divide it back.
-double constexpr kOSRMWeightToSecondsMultiplier = 1. / 10.;
-
 using TSeg = routing::OsrmMappingTypes::FtSeg;
 
 void LoadPathGeometry(buffer_vector<TSeg, 8> const & buffer, size_t startIndex,
diff --git a/routing/osrm_path_segment_factory.hpp b/routing/osrm_path_segment_factory.hpp
index 9fd2754a43..0fbe1b30f4 100644
--- a/routing/osrm_path_segment_factory.hpp
+++ b/routing/osrm_path_segment_factory.hpp
@@ -8,6 +8,9 @@ struct FeatureGraphNode;
 struct RawPathData;
 struct RoutingMapping;
 
+// Osrm multiples seconds to 10, so we need to divide it back.
+double constexpr kOSRMWeightToSecondsMultiplier = 0.1;
+
 // General constructor.
 void OsrmPathSegmentFactory(RoutingMapping & mapping, Index const & index,
                             RawPathData const & osrmPathSegment, LoadedPathSegment & loadedPathSegment);
diff --git a/routing/routing_integration_tests/cross_section_tests.cpp b/routing/routing_integration_tests/cross_section_tests.cpp
index 8b48249476..acd8025414 100644
--- a/routing/routing_integration_tests/cross_section_tests.cpp
+++ b/routing/routing_integration_tests/cross_section_tests.cpp
@@ -199,6 +199,7 @@ UNIT_TEST(CrossMwmGraphTest)
       ++ingoingCounter;
       vector<BorderCross> const & targets =
           crossMwmGraph.ConstructBorderCross(currentMapping, node);
+
       for (BorderCross const & t : targets)
       {
         vector<CrossWeightedEdge> outAdjs;
diff --git a/routing/routing_tests/cross_routing_tests.cpp b/routing/routing_tests/cross_routing_tests.cpp
index 9074cd92a9..15df806f59 100644
--- a/routing/routing_tests/cross_routing_tests.cpp
+++ b/routing/routing_tests/cross_routing_tests.cpp
@@ -165,4 +165,12 @@ UNIT_TEST(TestFindingByPoint)
   TEST(!newContext.ForEachOutgoingNodeNearPoint(p3, fnOutgoing), ());
   TEST(outgoingNode.empty(), ());
 }
+UNIT_TEST(TestCrossWeightedEdgeComparator)
+{
+  CrossNode const from(0, Index::MwmId(), ms::LatLon::Zero());
+  CrossWeightedEdge const lhs(BorderCross(from, {1, Index::MwmId(), ms::LatLon::Zero()}), 2.0);
+  CrossWeightedEdge const rhs(BorderCross(from, {2, Index::MwmId(), ms::LatLon::Zero()}), 1.0);
+
+  TEST(lhs < rhs || rhs < lhs || lhs == rhs, ());
+}
 }  // namespace
diff --git a/routing/segment.hpp b/routing/segment.hpp
index 1729b22cb2..cd476c7e7b 100644
--- a/routing/segment.hpp
+++ b/routing/segment.hpp
@@ -37,6 +37,9 @@ public:
     return m_forward == front ? m_segmentIdx + 1 : m_segmentIdx;
   }
 
+  uint32_t GetMinPointId() const { return m_segmentIdx; }
+  uint32_t GetMaxPointId() const { return m_segmentIdx + 1; }
+
   RoadPoint GetRoadPoint(bool front) const { return RoadPoint(m_featureId, GetPointId(front)); }
 
   bool operator<(Segment const & seg) const
@@ -80,6 +83,13 @@ public:
     return m_target == edge.m_target && m_weight == edge.m_weight;
   }
 
+  bool operator<(SegmentEdge const & edge) const
+  {
+    if (m_target != edge.m_target)
+      return m_target < edge.m_target;
+    return m_weight < edge.m_weight;
+  }
+
 private:
   // Target is vertex going to for outgoing edges, vertex going from for ingoing edges.
   Segment m_target;