[routing] Add DijkstraWrapperJoints for calculation leaps in generator. Boost up to 35%.

18 files changed, 595 insertions, 494 deletions

diff --git a/routing/CMakeLists.txt b/routing/CMakeLists.txt
index a4dadd147e..a6b1552e3d 100644
--- a/routing/CMakeLists.txt
+++ b/routing/CMakeLists.txt
@@ -54,7 +54,6 @@ set(
   index_graph_serialization.hpp
   index_graph_starter.cpp
   index_graph_starter.hpp
-  index_graph_starter_joints.cpp
   index_graph_starter_joints.hpp
   index_road_graph.cpp
   index_road_graph.hpp
diff --git a/routing/base/astar_algorithm.hpp b/routing/base/astar_algorithm.hpp
index 6fc23896e3..3e4e0fb718 100644
--- a/routing/base/astar_algorithm.hpp
+++ b/routing/base/astar_algorithm.hpp
@@ -139,6 +139,18 @@ public:
 
     void SetParent(Vertex const & parent, Vertex const & child) { m_parents[parent] = child; }
 
+    bool HasParent(Vertex const & child)
+    {
+      return m_parents.count(child) != 0;
+    }
+
+    Vertex const & GetParent(Vertex const & child)
+    {
+      auto const it = m_parents.find(child);
+      CHECK(it != m_parents.cend(), ("Can not find parent of child:", child));
+      return it->second;
+    }
+
     void ReconstructPath(Vertex const & v, std::vector<Vertex> & path) const;
 
   private:
diff --git a/routing/index_graph.cpp b/routing/index_graph.cpp
index dd97466b62..5b29af4c9e 100644
--- a/routing/index_graph.cpp
+++ b/routing/index_graph.cpp
@@ -9,6 +9,8 @@
 #include "base/checked_cast.hpp"
 #include "base/exception.hpp"
 
+#include "routing/world_graph.hpp"
+
 #include <algorithm>
 #include <cstdlib>
 #include <limits>
@@ -408,4 +410,6 @@ RouteWeight IndexGraph::GetPenalties(Segment const & u, Segment const & v)
 
   return RouteWeight(uTurnPenalty /* weight */, passThroughPenalty, accessPenalty, 0.0 /* transitTime */);
 }
+
+WorldGraphMode IndexGraph::GetMode() const { return WorldGraphMode::Undefined; }
 }  // namespace routing
diff --git a/routing/index_graph.hpp b/routing/index_graph.hpp
index cd31179a2d..e9f49fb9d8 100644
--- a/routing/index_graph.hpp
+++ b/routing/index_graph.hpp
@@ -24,6 +24,8 @@
 
 namespace routing
 {
+enum class WorldGraphMode;
+
 class IndexGraph final
 {
 public:
@@ -91,17 +93,20 @@ public:
   void GetLastPointsForJoint(std::vector<Segment> const & children, bool isOutgoing,
                              std::vector<uint32_t> & lastPoints);
 
-private:
+  WorldGraphMode GetMode() const;
+  m2::PointD const & GetPoint(Segment const & segment, bool front)
+  {
+    return GetGeometry().GetRoad(segment.GetFeatureId()).GetPoint(segment.GetPointId(front));
+  }
+
   RouteWeight CalcSegmentWeight(Segment const & segment);
+
+private:
   void GetNeighboringEdges(Segment const & from, RoadPoint const & rp, bool isOutgoing,
                            vector<SegmentEdge> & edges);
   void GetNeighboringEdge(Segment const & from, Segment const & to, bool isOutgoing,
                           vector<SegmentEdge> & edges);
   RouteWeight GetPenalties(Segment const & u, Segment const & v);
-  m2::PointD const & GetPoint(Segment const & segment, bool front)
-  {
-    return GetGeometry().GetRoad(segment.GetFeatureId()).GetPoint(segment.GetPointId(front));
-  }
 
   void GetSegmentCandidateForJoint(Segment const & parent, bool isOutgoing, std::vector<Segment> & children);
   void ReconstructJointSegment(Segment const & parent, std::vector<Segment> const & firstChildren,
diff --git a/routing/index_graph_starter.cpp b/routing/index_graph_starter.cpp
index 82e73237b1..f6a0b1d538 100644
--- a/routing/index_graph_starter.cpp
+++ b/routing/index_graph_starter.cpp
@@ -169,7 +169,7 @@ void IndexGraphStarter::GetEdgesList(Segment const & segment, bool isOutgoing,
   edges.clear();
 
   // If mode is LeapsOnly we need to connect start/finish segment to transitions.
-  if (m_graph.GetMode() == WorldGraph::Mode::LeapsOnly)
+  if (m_graph.GetMode() == WorldGraphMode::LeapsOnly)
   {
     if (segment.IsRealSegment() && !IsRoutingOptionsGood(segment))
       return;
diff --git a/routing/index_graph_starter.hpp b/routing/index_graph_starter.hpp
index 5cfe29da05..29398cf1d4 100644
--- a/routing/index_graph_starter.hpp
+++ b/routing/index_graph_starter.hpp
@@ -53,7 +53,7 @@ public:
   void Append(FakeEdgesContainer const & container);
 
   WorldGraph & GetGraph() const { return m_graph; }
-  WorldGraph::Mode GetMode() const { return m_graph.GetMode(); }
+  WorldGraphMode GetMode() const { return m_graph.GetMode(); }
   Junction const & GetStartJunction() const;
   Junction const & GetFinishJunction() const;
   Segment GetStartSegment() const { return GetFakeSegment(m_start.m_id); }
@@ -82,6 +82,12 @@ public:
   // start and finish in pass-through/non-pass-through area and number of non-pass-through crosses.
   bool CheckLength(RouteWeight const & weight);
 
+  void GetEdgeList(Segment const & segment, bool isOutgoing,
+                   std::vector<JointEdge> & edges, std::vector<RouteWeight> & parentWeights) const
+  {
+    return m_graph.GetEdgeList(segment, isOutgoing, edges, parentWeights);
+  }
+
   void GetEdgesList(Segment const & segment, bool isOutgoing,
                     std::vector<SegmentEdge> & edges) const;
 
@@ -106,6 +112,11 @@ public:
     return m_graph.HeuristicCostEstimate(GetPoint(from, true /* front */), to);
   }
 
+  bool IsJoint(Segment const & segment, bool fromStart)
+  {
+    return GetGraph().GetIndexGraph(segment.GetMwmId()).IsJoint(segment.GetRoadPoint(fromStart));
+  }
+
   RouteWeight CalcSegmentWeight(Segment const & segment) const;
   double CalcSegmentETA(Segment const & segment) const;
 
diff --git a/routing/index_graph_starter_joints.cpp b/routing/index_graph_starter_joints.cpp
deleted file mode 100644
index 5b93579956..0000000000
--- a/routing/index_graph_starter_joints.cpp
+++ /dev/null
@@ -1,416 +0,0 @@
-#include "routing/index_graph_starter_joints.hpp"
-
-#include "base/assert.hpp"
-
-#include <algorithm>
-#include <utility>
-
-namespace routing
-{
-IndexGraphStarterJoints::IndexGraphStarterJoints(IndexGraphStarter & starter,
-                                                 Segment const & startSegment,
-                                                 Segment const & endSegment)
-  : m_starter(starter), m_startSegment(startSegment), m_endSegment(endSegment)
-{
-  Init(startSegment, endSegment);
-}
-
-void IndexGraphStarterJoints::Init(Segment const & startSegment, Segment const & endSegment)
-{
-  m_startSegment = startSegment;
-  m_endSegment = endSegment;
-
-  m_startPoint = m_starter.GetPoint(m_startSegment, true /* front */);
-  m_endPoint = m_starter.GetPoint(m_endSegment, true /* front */);
-
-  CHECK(m_starter.GetGraph().GetMode() == WorldGraph::Mode::Joints ||
-        m_starter.GetGraph().GetMode() == WorldGraph::Mode::JointSingleMwm, ());
-
-  if (startSegment.IsRealSegment())
-    m_startJoint = CreateInvisibleJoint(startSegment, true /* start */);
-  else
-    m_startJoint = CreateFakeJoint(m_starter.GetStartSegment(), m_starter.GetStartSegment());
-
-  if (endSegment.IsRealSegment())
-    m_endJoint = CreateInvisibleJoint(endSegment, false /* start */);
-  else
-    m_endJoint = CreateFakeJoint(m_starter.GetFinishSegment(), m_starter.GetFinishSegment());
-
-  m_reconstructedFakeJoints[m_startJoint] = {m_startSegment};
-  m_reconstructedFakeJoints[m_endJoint] = {m_endSegment};
-
-  m_startOutEdges = FindFirstJoints(startSegment, true /* fromStart */);
-  m_endOutEdges = FindFirstJoints(endSegment, false /* fromStart */);
-
-  m_savedWeight[m_endJoint] = Weight(0.0);
-  for (auto const & edge : m_endOutEdges)
-    m_savedWeight[edge.GetTarget()] = edge.GetWeight();
-
-  m_init = true;
-}
-
-RouteWeight IndexGraphStarterJoints::HeuristicCostEstimate(JointSegment const & from, JointSegment const & to)
-{
-  Segment fromSegment;
-  Segment toSegment;
-
-  if (to.IsFake() || IsInvisible(to))
-    toSegment = m_fakeJointSegments[to].GetSegment(false /* start */);
-  else
-    toSegment = to.GetSegment(false /* start */);
-
-  if (from.IsFake() || IsInvisible(from))
-    fromSegment = m_fakeJointSegments[from].GetSegment(false /* start */);
-  else
-    fromSegment = from.GetSegment(false /* start */);
-
-  ASSERT(toSegment == m_startSegment || toSegment == m_endSegment, ("Invariant violated."));
-
-  return toSegment == m_startSegment ? m_starter.HeuristicCostEstimate(fromSegment, m_startPoint)
-                                     : m_starter.HeuristicCostEstimate(fromSegment, m_endPoint);
-}
-
-m2::PointD const & IndexGraphStarterJoints::GetPoint(JointSegment const & jointSegment, bool start)
-{
-  Segment segment;
-  if (jointSegment.IsFake())
-    segment = m_fakeJointSegments[jointSegment].GetSegment(start);
-  else
-    segment = jointSegment.GetSegment(start);
-
-  return m_starter.GetPoint(segment, jointSegment.IsForward());
-}
-
-std::vector<Segment> IndexGraphStarterJoints::ReconstructJoint(JointSegment const & joint)
-{
-  // We have invisible JointSegments, which are come from start to start or end to end.
-  // They need just for generic algorithm working. So we skip such objects.
-  if (IsInvisible(joint))
-    return {};
-
-  // In case of a fake vertex we return its prebuild path.
-  if (joint.IsFake())
-  {
-    auto it = m_reconstructedFakeJoints.find(joint);
-    CHECK(it != m_reconstructedFakeJoints.end(), ("Can not find such fake joint"));
-
-    return it->second;
-  }
-
-  // Otherwise just reconstruct segment consequently.
-  std::vector<Segment> subpath;
-
-  Segment currentSegment = joint.GetSegment(true /* start */);
-  Segment lastSegment = joint.GetSegment(false /* start */);
-
-  bool forward = currentSegment.GetSegmentIdx() < lastSegment.GetSegmentIdx();
-  while (currentSegment != lastSegment)
-  {
-    subpath.emplace_back(currentSegment);
-    currentSegment.Next(forward);
-  }
-
-  subpath.emplace_back(lastSegment);
-
-  return subpath;
-}
-
-void IndexGraphStarterJoints::AddFakeJoints(Segment const & segment, bool isOutgoing,
-                                            std::vector<JointEdge> & edges)
-{
-  // If |isOutgoing| is true, we need real segments, that are real parts
-  // of fake joints, entered to finish and vice versa.
-  std::vector<JointEdge> const & endings = isOutgoing ? m_endOutEdges : m_startOutEdges;
-
-  bool opposite = !isOutgoing;
-  for (auto const & edge : endings)
-  {
-    // The one end of FakeJointSegment is start/finish and the opposite end is real segment.
-    // So we check, whether |segment| is equal to the real segment of FakeJointSegment.
-    // If yes, that means, that we can go from |segment| to start/finish.
-    Segment firstSegment = m_fakeJointSegments[edge.GetTarget()].GetSegment(!opposite /* start */);
-    if (firstSegment == segment)
-    {
-      edges.emplace_back(edge);
-      return;
-    }
-  }
-}
-
-void IndexGraphStarterJoints::GetEdgeList(JointSegment const & vertex, bool isOutgoing,
-                                          std::vector<JointEdge> & edges)
-{
-  CHECK(m_init, ("IndexGraphStarterJoints was not initialized."));
-
-  edges.clear();
-
-  Segment parentSegment;
-
-  // This vector needs for backward A* search. Assume, we have parent and child_1, child_2.
-  // In this case we will save next weights:
-  // 1) from child_1 to parent.
-  // 2) from child_2 to parent.
-  // That needs for correct edges weights calculation.
-  std::vector<Weight> parentWeights;
-  size_t firstFakeId = 0;
-
-  // Case of fake start or finish joints.
-  // Note: startJoint and finishJoint are just loops
-  //       from start to start or end to end vertex.
-  if (vertex == GetStartJoint())
-  {
-    edges.insert(edges.end(), m_startOutEdges.begin(), m_startOutEdges.end());
-    parentWeights.insert(parentWeights.end(), edges.size(), Weight(0.0));
-    firstFakeId = edges.size();
-  }
-  else if (vertex == GetFinishJoint())
-  {
-    edges.insert(edges.end(), m_endOutEdges.begin(), m_endOutEdges.end());
-    // If vertex is FinishJoint, parentWeight is equal to zero, because the first vertex is zero-weight loop.
-    parentWeights.insert(parentWeights.end(), edges.size(), Weight(0.0));
-  }
-  else
-  {
-    bool opposite = !isOutgoing;
-    if (vertex.IsFake())
-    {
-      CHECK(m_fakeJointSegments.find(vertex) != m_fakeJointSegments.end(),
-            ("No such fake joint:", vertex, "in JointStarter."));
-
-      FakeJointSegment fakeJointSegment = m_fakeJointSegments[vertex];
-
-      auto const & startSegment = isOutgoing ? m_startSegment : m_endSegment;
-      auto const & endSegment = isOutgoing ? m_endSegment : m_startSegment;
-      auto const & endJoint = isOutgoing ? GetFinishJoint() : GetStartJoint();
-
-      // This is case when we can build route from start to finish without real segment, only fake.
-      // It happens when start and finish are close to each other.
-      // If we want A* stop, we should add |endJoint| to its queue, then A* will see the vertex: |endJoint|
-      // where it has already been and stop working.
-      if (fakeJointSegment.GetSegment(opposite /* start */) == endSegment)
-      {
-        if (isOutgoing)
-        {
-          static auto constexpr kZeroWeight = RouteWeight(0.0);
-          edges.emplace_back(endJoint, kZeroWeight);
-        }
-        else
-        {
-          auto it = m_savedWeight.find(vertex);
-          CHECK(it != m_savedWeight.end(), ("Can not find weight for:", vertex));
-
-          Weight const & weight = it->second;
-          edges.emplace_back(endJoint, weight);
-        }
-        return;
-      }
-
-      CHECK(fakeJointSegment.GetSegment(!opposite /* start */) == startSegment, ());
-      parentSegment = fakeJointSegment.GetSegment(opposite /* start */);
-    }
-    else
-    {
-      parentSegment = vertex.GetSegment(opposite /* start */);
-    }
-
-    std::vector<JointEdge> jointEdges;
-    m_starter.GetGraph().GetEdgeList(parentSegment, isOutgoing, jointEdges, parentWeights);
-    edges.insert(edges.end(), jointEdges.begin(), jointEdges.end());
-
-    firstFakeId = edges.size();
-    for (size_t i = 0; i < jointEdges.size(); ++i)
-    {
-      size_t prevSize = edges.size();
-      AddFakeJoints(jointEdges[i].GetTarget().GetSegment(!opposite /* start */), isOutgoing, edges);
-
-      // If we add fake edge, we should add new parentWeight as "child[i] -> parent".
-      // Because fake edge and current edge (jointEdges[i]) have the same first
-      // segments (differ only the ends), so we add to |parentWeights| the same
-      // value: parentWeights[i].
-      if (edges.size() != prevSize)
-      {
-        CHECK_LESS(i, parentWeights.size(), ());
-        parentWeights.emplace_back(parentWeights[i]);
-      }
-    }
-  }
-
-  if (!isOutgoing)
-  {
-    // |parentSegment| is parent-vertex from which we search children.
-    // For correct weight calculation we should get weight of JointSegment, that
-    // ends in |parentSegment| and add |parentWeight[i]| to the saved value.
-    auto it = m_savedWeight.find(vertex);
-    CHECK(it != m_savedWeight.end(), ("Can not find weight for:", vertex));
-
-    Weight const & weight = it->second;
-    for (size_t i = 0; i < edges.size(); ++i)
-    {
-      // Saving weight of current edges for returning in the next iterations.
-      m_savedWeight[edges[i].GetTarget()] = edges[i].GetWeight();
-      // For parent JointSegment we know its weight without last segment, because for each child
-      // it will differ (child_1 => parent != child_2 => parent), but (!) we save this weight in
-      // |parentWeights[]|. So the weight of an ith edge is a cached "weight of parent JointSegment" +
-      // "parentWeight[i]".
-      CHECK_LESS(i, parentWeights.size(), ());
-      edges[i].GetWeight() = weight + parentWeights[i];
-    }
-
-    // Delete useless weight of parent JointSegment.
-    m_savedWeight.erase(it);
-  }
-  else
-  {
-    // This needs for correct weights calculation of FakeJointSegments during forward A* search.
-    for (size_t i = firstFakeId; i < edges.size(); ++i)
-      edges[i].GetWeight() += parentWeights[i];
-  }
-}
-
-JointSegment IndexGraphStarterJoints::CreateFakeJoint(Segment const & from, Segment const & to)
-{
-  JointSegment jointSegment;
-  jointSegment.ToFake(m_fakeId++);
-
-  FakeJointSegment fakeJointSegment(from, to);
-  m_fakeJointSegments[jointSegment] = fakeJointSegment;
-
-  return jointSegment;
-}
-
-std::vector<JointEdge> IndexGraphStarterJoints::FindFirstJoints(Segment const & startSegment, bool fromStart)
-{
-  Segment endSegment = fromStart ? m_endSegment : m_startSegment;
-
-  std::queue<Segment> queue;
-  queue.emplace(startSegment);
-
-  std::map<Segment, Segment> parent;
-  std::map<Segment, RouteWeight> weight;
-  std::vector<JointEdge> result;
-
-  auto const reconstructPath = [&parent, &startSegment, &endSegment](Segment current, bool forward) {
-    std::vector<Segment> path;
-    // In case we can go from start to finish without joint (e.g. start and finish at
-    // the same long feature), we don't add the last segment to path for correctness
-    // reconstruction of the route. Otherwise last segment will repeat twice.
-    if (current != endSegment)
-      path.emplace_back(current);
-
-    if (current == startSegment)
-      return path;
-
-    for (;;)
-    {
-      Segment parentSegment = parent[current];
-
-      path.emplace_back(parentSegment);
-      if (parentSegment == startSegment)
-        break;
-      current = parentSegment;
-    }
-
-    if (forward)
-      std::reverse(path.begin(), path.end());
-
-    return path;
-  };
-
-  auto const addFake = [&](Segment const & segment, Segment const & beforeConvert)
-  {
-    JointSegment fakeJoint;
-    fakeJoint = fromStart ? CreateFakeJoint(startSegment, segment) :
-                            CreateFakeJoint(segment, startSegment);
-    result.emplace_back(fakeJoint, weight[beforeConvert]);
-
-    std::vector<Segment> path = reconstructPath(beforeConvert, fromStart);
-    m_reconstructedFakeJoints.emplace(fakeJoint, std::move(path));
-  };
-
-  auto const isEndOfSegment = [&](Segment const & fake, Segment const & segment)
-  {
-    CHECK(!fake.IsRealSegment(), ());
-
-    auto fakeEnd = m_starter.GetPoint(fake, fake.IsForward());
-    auto realEnd = m_starter.GetPoint(segment, segment.IsForward());
-
-    static auto constexpr kEps = 1e-5;
-    return base::AlmostEqualAbs(fakeEnd, realEnd, kEps);
-  };
-
-  while (!queue.empty())
-  {
-    Segment segment = queue.front();
-    queue.pop();
-    Segment beforeConvert = segment;
-    // Either the segment is fake and it can be converted to real one with |Joint| end (RoadPoint),
-    // or it's the real one and its end (RoadPoint) is |Joint|.
-    if (((!segment.IsRealSegment() && m_starter.ConvertToReal(segment) &&
-          isEndOfSegment(beforeConvert, segment)) || beforeConvert.IsRealSegment()) &&
-        IsJoint(segment, fromStart))
-    {
-      addFake(segment, beforeConvert);
-      continue;
-    }
-
-    if (beforeConvert == endSegment)
-    {
-      addFake(segment, beforeConvert);
-      continue;
-    }
-
-    std::vector<SegmentEdge> edges;
-    m_starter.GetEdgesList(beforeConvert, fromStart, edges);
-    for (auto const & edge : edges)
-    {
-      Segment const & child = edge.GetTarget();
-      auto const & newWeight = weight[beforeConvert] + edge.GetWeight();
-      if (weight.find(child) == weight.end() || weight[child] > newWeight)
-      {
-        parent[child] = beforeConvert;
-        weight[child] = newWeight;
-        queue.emplace(child);
-      }
-    }
-  }
-
-  return result;
-}
-
-JointSegment IndexGraphStarterJoints::CreateInvisibleJoint(Segment const & segment, bool start)
-{
-  JointSegment result;
-  result.ToFake(start ? kInvisibleId : kInvisibleId + 1);
-  m_fakeJointSegments[result] = FakeJointSegment(segment, segment);
-
-  return result;
-}
-
-bool IndexGraphStarterJoints::IsInvisible(JointSegment const & jointSegment) const
-{
-  return jointSegment.GetStartSegmentId() == jointSegment.GetEndSegmentId() &&
-         jointSegment.GetStartSegmentId() >= kInvisibleId &&
-         jointSegment.GetStartSegmentId() != std::numeric_limits<uint32_t>::max();
-}
-
-bool IndexGraphStarterJoints::IsJoint(Segment const & segment, bool fromStart)
-{
-  return m_starter.GetGraph().GetIndexGraph(segment.GetMwmId())
-                  .IsJoint(segment.GetRoadPoint(fromStart));
-}
-
-void IndexGraphStarterJoints::Reset()
-{
-  m_startJoint = JointSegment();
-  m_endJoint = JointSegment();
-  m_startSegment = Segment();
-  m_endSegment = Segment();
-  m_savedWeight.clear();
-  m_fakeJointSegments.clear();
-  m_reconstructedFakeJoints.clear();
-  m_startOutEdges.clear();
-  m_endOutEdges.clear();
-  m_fakeId = 0;
-  m_init = false;
-}
-}  // namespace routing
diff --git a/routing/index_graph_starter_joints.hpp b/routing/index_graph_starter_joints.hpp
index cc61b03929..e4d3b38d66 100644
--- a/routing/index_graph_starter_joints.hpp
+++ b/routing/index_graph_starter_joints.hpp
@@ -6,13 +6,17 @@
 
 #include "geometry/point2d.hpp"
 
+#include <limits>
 #include <map>
 #include <queue>
 #include <set>
 #include <vector>
 
+#include "boost/optional.hpp"
+
 namespace routing
 {
+template <typename Graph>
 class IndexGraphStarterJoints
 {
 public:
@@ -20,11 +24,14 @@ public:
   using Edge = JointEdge;
   using Weight = RouteWeight;
 
-  explicit IndexGraphStarterJoints(IndexGraphStarter & starter) : m_starter(starter) {}
-  IndexGraphStarterJoints(IndexGraphStarter & starter,
+  explicit IndexGraphStarterJoints(Graph & graph) : m_graph(graph) {}
+  IndexGraphStarterJoints(Graph & graph,
                           Segment const & startSegment,
                           Segment const & endSegment);
 
+  IndexGraphStarterJoints(Graph & graph,
+                          Segment const & startSegment);
+
   void Init(Segment const & startSegment, Segment const & endSegment);
 
   JointSegment const & GetStartJoint() const { return m_startJoint; }
@@ -45,18 +52,27 @@ public:
     GetEdgeList(vertex, false /* isOutgoing */, edges);
   }
 
-  WorldGraph::Mode GetMode() const { return m_starter.GetMode(); }
+  WorldGraphMode GetMode() const { return m_graph.GetMode(); }
   // End of A* interface.
-
-  IndexGraphStarter & GetStarter() { return m_starter; }
-
+  
   /// \brief Reconstructs JointSegment by segment after building the route.
   std::vector<Segment> ReconstructJoint(JointSegment const & joint);
 
   void Reset();
 
+  // Can not check segment for fake or not with segment.IsRealSegment(), because all segments
+  // have got fake m_numMwmId during mwm generation.
+  bool IsRealSegment(Segment const & segment) const
+  {
+    return segment.GetFeatureId() != std::numeric_limits<uint32_t>::max();
+  }
+
+  Segment const & GetSegmentOfFakeJoint(JointSegment const & joint, bool start);
+
 private:
-  static auto constexpr kInvisibleId = std::numeric_limits<uint32_t>::max() - 2;
+  static auto constexpr kInvisibleStartId = std::numeric_limits<uint32_t>::max() - 2;
+  static auto constexpr kInvisibleEndId = std::numeric_limits<uint32_t>::max() - 1;
+  static auto constexpr kInvalidId = std::numeric_limits<uint32_t>::max();
 
   struct FakeJointSegment
   {
@@ -64,7 +80,7 @@ private:
     FakeJointSegment(Segment const & start, Segment const & end)
       : m_start(start), m_end(end) {}
 
-    Segment GetSegment(bool start) const
+    Segment const & GetSegment(bool start) const
     {
       return start ? m_start : m_end;
     }
@@ -79,7 +95,20 @@ private:
 
   JointSegment CreateFakeJoint(Segment const & from, Segment const & to);
 
-  bool IsJoint(Segment const & segment, bool fromStart);
+  bool IsJoint(Segment const & segment, bool fromStart) const
+  {
+    return m_graph.IsJoint(segment, fromStart);
+  }
+
+  bool FillEdgesAndParentsWeights(JointSegment const & vertex,
+                                  bool isOutgoing,
+                                  size_t & firstFakeId,
+                                  std::vector<JointEdge> & edges,
+                                  std::vector<Weight> & parentWeights);
+
+  boost::optional<Segment> GetParentSegment(JointSegment const & vertex,
+                                            bool isOutgoing,
+                                            std::vector<JointEdge> & edges);
 
   /// \brief Makes BFS from |startSegment| in direction |fromStart| and find the closest segments
   /// which end RoadPoints are joints. Thus we build fake joint segments graph.
@@ -87,10 +116,19 @@ private:
 
   JointSegment CreateInvisibleJoint(Segment const & segment, bool start);
 
-  bool IsInvisible(JointSegment const & jointSegment) const;
+  bool IsInvisible(JointSegment const & jointSegment) const
+  {
+    static_assert(kInvisibleStartId < kInvisibleEndId && kInvisibleEndId != kInvalidId,
+                  "FakeID's are crossing in JointSegment.");
+
+    return jointSegment.GetStartSegmentId() == jointSegment.GetEndSegmentId() &&
+           (jointSegment.GetStartSegmentId() == kInvisibleStartId ||
+           jointSegment.GetStartSegmentId() == kInvisibleEndId) &&
+           jointSegment.GetStartSegmentId() != kInvalidId;
+  }
 
   // For GetEdgeList from segments.
-  IndexGraphStarter & m_starter;
+  Graph & m_graph;
 
   // Fake start and end joints.
   JointSegment m_startJoint;
@@ -120,4 +158,438 @@ private:
   uint32_t m_fakeId = 0;
   bool m_init = false;
 };
+
+template <typename Graph>
+IndexGraphStarterJoints<Graph>::IndexGraphStarterJoints(Graph & graph,
+                                                        Segment const & startSegment,
+                                                        Segment const & endSegment)
+  : m_graph(graph), m_startSegment(startSegment), m_endSegment(endSegment)
+{
+  Init(m_startSegment, m_endSegment);
+}
+
+template <typename Graph>
+IndexGraphStarterJoints<Graph>::IndexGraphStarterJoints(Graph & graph,
+                                                        Segment const & startSegment)
+  : m_graph(graph), m_startSegment(startSegment), m_endSegment(Segment())
+{
+  Init(m_startSegment, m_endSegment);
+}
+
+template <typename Graph>
+void IndexGraphStarterJoints<Graph>::Init(Segment const & startSegment, Segment const & endSegment)
+{
+  m_startSegment = startSegment;
+  m_endSegment = endSegment;
+
+  if (IsRealSegment(startSegment))
+    m_startJoint = CreateInvisibleJoint(startSegment, true /* start */);
+  else
+    m_startJoint = CreateFakeJoint(m_graph.GetStartSegment(), m_graph.GetStartSegment());
+
+  if (IsRealSegment(endSegment))
+    m_endJoint = CreateInvisibleJoint(endSegment, false /* start */);
+  else
+    m_endJoint = CreateFakeJoint(m_graph.GetFinishSegment(), m_graph.GetFinishSegment());
+
+  m_reconstructedFakeJoints[m_startJoint] = {m_startSegment};
+  m_reconstructedFakeJoints[m_endJoint] = {m_endSegment};
+
+  m_startOutEdges = FindFirstJoints(startSegment, true /* fromStart */);
+  m_endOutEdges = FindFirstJoints(endSegment, false /* fromStart */);
+
+  m_savedWeight[m_endJoint] = Weight(0.0);
+  for (auto const & edge : m_endOutEdges)
+    m_savedWeight[edge.GetTarget()] = edge.GetWeight();
+
+  m_init = true;
+}
+
+template <typename Graph>
+RouteWeight IndexGraphStarterJoints<Graph>::HeuristicCostEstimate(JointSegment const & from, JointSegment const & to)
+{
+  Segment const & fromSegment =
+    from.IsFake() || IsInvisible(from) ? m_fakeJointSegments[from].GetSegment(false /* start */)
+                                       : from.GetSegment(false /* start */);
+
+  Segment const & toSegment =
+    to.IsFake() || IsInvisible(to) ? m_fakeJointSegments[to].GetSegment(false /* start */)
+                                   : to.GetSegment(false /* start */);
+
+  ASSERT(toSegment == m_startSegment || toSegment == m_endSegment, ("Invariant violated."));
+
+  return toSegment == m_startSegment ? m_graph.HeuristicCostEstimate(fromSegment, m_startPoint)
+                                     : m_graph.HeuristicCostEstimate(fromSegment, m_endPoint);
+}
+
+template <typename Graph>
+m2::PointD const &
+IndexGraphStarterJoints<Graph>::GetPoint(JointSegment const & jointSegment, bool start)
+{
+  Segment segment = jointSegment.IsFake() ? m_fakeJointSegments[jointSegment].GetSegment(start)
+                                          : jointSegment.GetSegment(start);
+
+  return m_graph.GetPoint(segment, jointSegment.IsForward());
+}
+
+template <typename Graph>
+std::vector<Segment> IndexGraphStarterJoints<Graph>::ReconstructJoint(JointSegment const & joint)
+{
+  // We have invisible JointSegments, which are come from start to start or end to end.
+  // They need just for generic algorithm working. So we skip such objects.
+  if (IsInvisible(joint))
+    return {};
+
+  // In case of a fake vertex we return its prebuild path.
+  if (joint.IsFake())
+  {
+    auto const it = m_reconstructedFakeJoints.find(joint);
+    CHECK(it != m_reconstructedFakeJoints.cend(), ("Can not find such fake joint"));
+
+    return it->second;
+  }
+
+  // Otherwise just reconstruct segment consequently.
+  std::vector<Segment> subpath;
+
+  Segment currentSegment = joint.GetSegment(true /* start */);
+  Segment lastSegment = joint.GetSegment(false /* start */);
+
+  bool const forward = currentSegment.GetSegmentIdx() < lastSegment.GetSegmentIdx();
+  while (currentSegment != lastSegment)
+  {
+    subpath.emplace_back(currentSegment);
+    currentSegment.Next(forward);
+  }
+
+  subpath.emplace_back(lastSegment);
+  return subpath;
+}
+
+template <typename Graph>
+void IndexGraphStarterJoints<Graph>::AddFakeJoints(Segment const & segment, bool isOutgoing,
+                                                   std::vector<JointEdge> & edges)
+{
+  // If |isOutgoing| is true, we need real segments, that are real parts
+  // of fake joints, entered to finish and vice versa.
+  std::vector<JointEdge> const & endings = isOutgoing ? m_endOutEdges : m_startOutEdges;
+
+  bool const opposite = !isOutgoing;
+  for (auto const & edge : endings)
+  {
+    // The one end of FakeJointSegment is start/finish and the opposite end is real segment.
+    // So we check, whether |segment| is equal to the real segment of FakeJointSegment.
+    // If yes, that means, that we can go from |segment| to start/finish.
+    Segment const & firstSegment = m_fakeJointSegments[edge.GetTarget()].GetSegment(!opposite /* start */);
+    if (firstSegment == segment)
+    {
+      edges.emplace_back(edge);
+      return;
+    }
+  }
+}
+
+template <typename Graph>
+Segment const & IndexGraphStarterJoints<Graph>::GetSegmentOfFakeJoint(JointSegment const & joint, bool start)
+{
+  auto const it = m_fakeJointSegments.find(joint);
+  CHECK(it != m_fakeJointSegments.cend(), ("No such fake joint:", joint, "in JointStarter."));
+
+  return (it->second).GetSegment(start);
+}
+
+template <typename Graph>
+boost::optional<Segment> IndexGraphStarterJoints<Graph>::GetParentSegment(JointSegment const & vertex,
+                                                                          bool isOutgoing,
+                                                                          std::vector<JointEdge> & edges)
+{
+  boost::optional<Segment> parentSegment;
+  bool const opposite = !isOutgoing;
+  if (vertex.IsFake())
+  {
+    CHECK(m_fakeJointSegments.find(vertex) != m_fakeJointSegments.end(),
+          ("No such fake joint:", vertex, "in JointStarter."));
+
+    FakeJointSegment fakeJointSegment = m_fakeJointSegments[vertex];
+
+    auto const & startSegment = isOutgoing ? m_startSegment : m_endSegment;
+    auto const & endSegment = isOutgoing ? m_endSegment : m_startSegment;
+    auto const & endJoint = isOutgoing ? GetFinishJoint() : GetStartJoint();
+
+    // This is case when we can build route from start to finish without real segment, only fake.
+    // It happens when start and finish are close to each other.
+    // If we want A* stop, we should add |endJoint| to its queue, then A* will see the vertex: |endJoint|
+    // where it has already been and stop working.
+    if (fakeJointSegment.GetSegment(opposite /* start */) == endSegment)
+    {
+      if (isOutgoing)
+      {
+        static auto constexpr kZeroWeight = RouteWeight(0.0);
+        edges.emplace_back(endJoint, kZeroWeight);
+      }
+      else
+      {
+        auto const it = m_savedWeight.find(vertex);
+        CHECK(it != m_savedWeight.cend(), ("Can not find weight for:", vertex));
+
+        Weight const & weight = it->second;
+        edges.emplace_back(endJoint, weight);
+      }
+      return {};
+    }
+
+    CHECK(fakeJointSegment.GetSegment(!opposite /* start */) == startSegment, ());
+    parentSegment = fakeJointSegment.GetSegment(opposite /* start */);
+  }
+  else
+  {
+    parentSegment = vertex.GetSegment(opposite /* start */);
+  }
+
+  return parentSegment;
+}
+
+template <typename Graph>
+bool IndexGraphStarterJoints<Graph>::FillEdgesAndParentsWeights(JointSegment const & vertex,
+                                                                bool isOutgoing,
+                                                                size_t & firstFakeId,
+                                                                std::vector<JointEdge> & edges,
+                                                                std::vector<Weight> & parentWeights)
+{
+  // Case of fake start or finish joints.
+  // Note: startJoint and finishJoint are just loops
+  //       from start to start or end to end vertex.
+  if (vertex == GetStartJoint())
+  {
+    edges.insert(edges.end(), m_startOutEdges.begin(), m_startOutEdges.end());
+    parentWeights.insert(parentWeights.end(), edges.size(), Weight(0.0));
+    firstFakeId = edges.size();
+  }
+  else if (vertex == GetFinishJoint())
+  {
+    edges.insert(edges.end(), m_endOutEdges.begin(), m_endOutEdges.end());
+    // If vertex is FinishJoint, parentWeight is equal to zero, because the first vertex is zero-weight loop.
+    parentWeights.insert(parentWeights.end(), edges.size(), Weight(0.0));
+  }
+  else
+  {
+    auto const optional = GetParentSegment(vertex, isOutgoing, edges);
+    if (!optional)
+      return false;
+
+    Segment parentSegment = optional.value();
+
+    std::vector<JointEdge> jointEdges;
+    m_graph.GetEdgeList(parentSegment, isOutgoing, jointEdges, parentWeights);
+    edges.insert(edges.end(), jointEdges.begin(), jointEdges.end());
+
+    firstFakeId = edges.size();
+    bool const opposite = !isOutgoing;
+    for (size_t i = 0; i < jointEdges.size(); ++i)
+    {
+      size_t prevSize = edges.size();
+      AddFakeJoints(jointEdges[i].GetTarget().GetSegment(!opposite /* start */), isOutgoing, edges);
+      // If we add fake edge, we should add new parentWeight as "child[i] -> parent".
+      // Because fake edge and current edge (jointEdges[i]) have the same first
+      // segments (differ only the ends), so we add to |parentWeights| the same
+      // value: parentWeights[i].
+      if (edges.size() != prevSize)
+      {
+        CHECK_LESS(i, parentWeights.size(), ());
+        parentWeights.emplace_back(parentWeights[i]);
+      }
+    }
+  }
+
+  return true;
+}
+
+template <typename Graph>
+void IndexGraphStarterJoints<Graph>::GetEdgeList(JointSegment const & vertex, bool isOutgoing,
+                                                 std::vector<JointEdge> & edges)
+{
+  CHECK(m_init, ("IndexGraphStarterJoints was not initialized."));
+
+  edges.clear();
+
+  // This vector needs for backward A* search. Assume, we have parent and child_1, child_2.
+  // In this case we will save next weights:
+  // 1) from child_1 to parent.
+  // 2) from child_2 to parent.
+  // That needs for correct edges weights calculation.
+  std::vector<Weight> parentWeights;
+
+  size_t firstFakeId = 0;
+  if (!FillEdgesAndParentsWeights(vertex, isOutgoing, firstFakeId, edges, parentWeights))
+    return;
+
+  if (!isOutgoing)
+  {
+    // |parentSegment| is parent-vertex from which we search children.
+    // For correct weight calculation we should get weight of JointSegment, that
+    // ends in |parentSegment| and add |parentWeight[i]| to the saved value.
+    auto const it = m_savedWeight.find(vertex);
+    CHECK(it != m_savedWeight.cend(), ("Can not find weight for:", vertex));
+
+    Weight const & weight = it->second;
+    for (size_t i = 0; i < edges.size(); ++i)
+    {
+      // Saving weight of current edges for returning in the next iterations.
+      m_savedWeight[edges[i].GetTarget()] = edges[i].GetWeight();
+      // For parent JointSegment we know its weight without last segment, because for each child
+      // it will differ (child_1 => parent != child_2 => parent), but (!) we save this weight in
+      // |parentWeights[]|. So the weight of an ith edge is a cached "weight of parent JointSegment" +
+      // "parentWeight[i]".
+      CHECK_LESS(i, parentWeights.size(), ());
+      edges[i].GetWeight() = weight + parentWeights[i];
+    }
+
+    // Delete useless weight of parent JointSegment.
+    m_savedWeight.erase(it);
+  }
+  else
+  {
+    // This needs for correct weights calculation of FakeJointSegments during forward A* search.
+    for (size_t i = firstFakeId; i < edges.size(); ++i)
+      edges[i].GetWeight() += parentWeights[i];
+  }
+}
+
+template <typename Graph>
+JointSegment IndexGraphStarterJoints<Graph>::CreateFakeJoint(Segment const & from, Segment const & to)
+{
+  JointSegment jointSegment;
+  jointSegment.ToFake(m_fakeId++);
+
+  FakeJointSegment fakeJointSegment(from, to);
+  m_fakeJointSegments[jointSegment] = fakeJointSegment;
+
+  return jointSegment;
+}
+
+template <typename Graph>
+std::vector<JointEdge> IndexGraphStarterJoints<Graph>::FindFirstJoints(Segment const & startSegment,
+                                                                       bool fromStart)
+{
+  Segment endSegment = fromStart ? m_endSegment : m_startSegment;
+
+  std::queue<Segment> queue;
+  queue.push(startSegment);
+
+  std::map<Segment, Segment> parent;
+  std::map<Segment, RouteWeight> weight;
+  std::vector<JointEdge> result;
+
+  auto const reconstructPath = [&parent, &startSegment, &endSegment](Segment current, bool forward)
+  {
+    std::vector<Segment> path;
+    // In case we can go from start to finish without joint (e.g. start and finish at
+    // the same long feature), we don't add the last segment to path for correctness
+    // reconstruction of the route. Otherwise last segment will repeat twice.
+    if (current != endSegment)
+      path.emplace_back(current);
+
+    if (current == startSegment)
+      return path;
+
+    Segment parentSegment;
+    do
+    {
+      parentSegment = parent[current];
+      path.emplace_back(parentSegment);
+      current = parentSegment;
+    } while (parentSegment != startSegment);
+
+    if (forward)
+      std::reverse(path.begin(), path.end());
+
+    return path;
+  };
+
+  auto const addFake = [&](Segment const & segment, Segment const & beforeConvert)
+  {
+    JointSegment fakeJoint;
+    fakeJoint = fromStart ? CreateFakeJoint(startSegment, segment) :
+                            CreateFakeJoint(segment, startSegment);
+    result.emplace_back(fakeJoint, weight[beforeConvert]);
+
+    std::vector<Segment> path = reconstructPath(beforeConvert, fromStart);
+    m_reconstructedFakeJoints[fakeJoint] = path;
+  };
+
+  auto const isEndOfSegment = [&](Segment const & fake, Segment const & segment)
+  {
+    CHECK(!IsRealSegment(fake), ());
+
+    auto const fakeEnd = m_graph.GetPoint(fake, fake.IsForward());
+    auto const realEnd = m_graph.GetPoint(segment, segment.IsForward());
+
+    static auto constexpr kEps = 1e-5;
+    return base::AlmostEqualAbs(fakeEnd, realEnd, kEps);
+  };
+
+  while (!queue.empty())
+  {
+    Segment segment = queue.front();
+    queue.pop();
+    Segment beforeConvert = segment;
+    // Either the segment is fake and it can be converted to real one with |Joint| end (RoadPoint),
+    // or it's the real one and its end (RoadPoint) is |Joint|.
+    if (((!IsRealSegment(segment) && m_graph.ConvertToReal(segment) &&
+          isEndOfSegment(beforeConvert, segment)) || IsRealSegment(beforeConvert)) &&
+        IsJoint(segment, fromStart))
+    {
+      addFake(segment, beforeConvert);
+      continue;
+    }
+
+    if (beforeConvert == endSegment)
+    {
+      addFake(segment, beforeConvert);
+      continue;
+    }
+
+    std::vector<SegmentEdge> edges;
+    m_graph.GetEdgesList(beforeConvert, fromStart, edges);
+    for (auto const & edge : edges)
+    {
+      Segment child = edge.GetTarget();
+      auto const & newWeight = weight[beforeConvert] + edge.GetWeight();
+      if (weight.find(child) == weight.end() || weight[child] > newWeight)
+      {
+        parent[child] = beforeConvert;
+        weight[child] = newWeight;
+        queue.push(child);
+      }
+    }
+  }
+
+  return result;
+}
+
+template <typename Graph>
+JointSegment IndexGraphStarterJoints<Graph>::CreateInvisibleJoint(Segment const & segment, bool start)
+{
+  JointSegment result;
+  result.ToFake(start ? kInvisibleStartId : kInvisibleEndId);
+  m_fakeJointSegments[result] = FakeJointSegment(segment, segment);
+
+  return result;
+}
+
+template <typename Graph>
+void IndexGraphStarterJoints<Graph>::Reset()
+{
+  m_startJoint = JointSegment();
+  m_endJoint = JointSegment();
+  m_startSegment = Segment();
+  m_endSegment = Segment();
+  m_savedWeight.clear();
+  m_fakeJointSegments.clear();
+  m_reconstructedFakeJoints.clear();
+  m_startOutEdges.clear();
+  m_endOutEdges.clear();
+  m_fakeId = 0;
+  m_init = false;
+}
 }  // namespace routing
diff --git a/routing/index_router.cpp b/routing/index_router.cpp
index 4c372678f4..18abca1d89 100644
--- a/routing/index_router.cpp
+++ b/routing/index_router.cpp
@@ -315,7 +315,7 @@ IndexRouter::IndexRouter(VehicleType vehicleType, bool loadAltitudes,
 unique_ptr<WorldGraph> IndexRouter::MakeSingleMwmWorldGraph()
 {
   auto worldGraph = MakeWorldGraph();
-  worldGraph->SetMode(WorldGraph::Mode::SingleMwm);
+  worldGraph->SetMode(WorldGraphMode::SingleMwm);
   return worldGraph;
 }
 
@@ -491,7 +491,7 @@ RouterResultCode IndexRouter::DoCalculateRoute(Checkpoints const & checkpoints,
 }
 
 vector<Segment> ProcessJoints(vector<JointSegment> const & jointsPath,
-                              IndexGraphStarterJoints & jointStarter)
+                              IndexGraphStarterJoints<IndexGraphStarter> & jointStarter)
 {
   CHECK(!jointsPath.empty(), ());
 
@@ -529,14 +529,14 @@ RouterResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoints,
   {
     case VehicleType::Pedestrian:
     case VehicleType::Bicycle:
-      starter.GetGraph().SetMode(WorldGraph::Mode::Joints);
+      starter.GetGraph().SetMode(WorldGraphMode::Joints);
       break;
     case VehicleType::Transit:
-      starter.GetGraph().SetMode(WorldGraph::Mode::NoLeaps);
+      starter.GetGraph().SetMode(WorldGraphMode::NoLeaps);
       break;
     case VehicleType::Car:
-      starter.GetGraph().SetMode(AreMwmsNear(starter.GetMwms()) ? WorldGraph::Mode::Joints
-                                                                : WorldGraph::Mode::LeapsOnly);
+      starter.GetGraph().SetMode(AreMwmsNear(starter.GetMwms()) ? WorldGraphMode::Joints
+                                                                : WorldGraphMode::LeapsOnly);
       break;
     case VehicleType::Count:
       CHECK(false, ("Unknown vehicle type:", m_vehicleType));
@@ -572,9 +572,9 @@ RouterResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoints,
   auto checkLength = [&starter](RouteWeight const & weight) { return starter.CheckLength(weight); };
 
   base::HighResTimer timer;
-  if (starter.GetGraph().GetMode() == WorldGraph::Mode::Joints)
+  if (starter.GetGraph().GetMode() == WorldGraphMode::Joints)
   {
-    IndexGraphStarterJoints jointStarter(starter, starter.GetStartSegment(), starter.GetFinishSegment());
+    IndexGraphStarterJoints<IndexGraphStarter> jointStarter(starter, starter.GetStartSegment(), starter.GetFinishSegment());
     RoutingResult<JointSegment, RouteWeight> routingResult;
     auto const onVisitJunctionJoints = [&](JointSegment const & from, JointSegment const & to)
     {
@@ -594,12 +594,12 @@ RouterResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoints,
       delegate.OnPointCheck(pointFrom);
     };
 
-    AStarAlgorithm<IndexGraphStarterJoints>::Params params(
+    AStarAlgorithm<IndexGraphStarterJoints<IndexGraphStarter>>::Params params(
       jointStarter, jointStarter.GetStartJoint(), jointStarter.GetFinishJoint(), nullptr /* prevRoute */,
       delegate, onVisitJunctionJoints, checkLength);
 
     set<NumMwmId> const mwmIds = starter.GetMwms();
-    RouterResultCode const result = FindPath<IndexGraphStarterJoints>(params, mwmIds, routingResult);
+    RouterResultCode const result = FindPath<IndexGraphStarterJoints<IndexGraphStarter>>(params, mwmIds, routingResult);
     if (result != RouterResultCode::NoError)
       return result;
 
@@ -639,7 +639,7 @@ RouterResultCode IndexRouter::AdjustRoute(Checkpoints const & checkpoints,
   base::Timer timer;
   TrafficStash::Guard guard(m_trafficStash);
   auto graph = MakeWorldGraph();
-  graph->SetMode(WorldGraph::Mode::Joints);
+  graph->SetMode(WorldGraphMode::NoLeaps);
 
   Segment startSegment;
   m2::PointD const & pointFrom = checkpoints.GetPointFrom();
@@ -821,11 +821,11 @@ bool IndexRouter::FindBestSegment(m2::PointD const & point, m2::PointD const & d
 
 RouterResultCode IndexRouter::ProcessLeapsJoints(vector<Segment> const & input,
                                                  RouterDelegate const & delegate,
-                                                 WorldGraph::Mode prevMode,
+                                                 WorldGraphMode prevMode,
                                                  IndexGraphStarter & starter,
                                                  vector<Segment> & output)
 {
-  if (prevMode != WorldGraph::Mode::LeapsOnly)
+  if (prevMode != WorldGraphMode::LeapsOnly)
   {
     output = input;
     return RouterResultCode::NoError;
@@ -886,9 +886,9 @@ RouterResultCode IndexRouter::ProcessLeapsJoints(vector<Segment> const & input,
   };
 
   set<NumMwmId> mwmIds;
-  IndexGraphStarterJoints jointStarter(starter);
+  IndexGraphStarterJoints<IndexGraphStarter> jointStarter(starter);
 
-  auto const runAStarAlgorithm = [&](size_t start, size_t end, WorldGraph::Mode mode,
+  auto const runAStarAlgorithm = [&](size_t start, size_t end, WorldGraphMode mode,
                                      RoutingResult<JointSegment, RouteWeight> & routingResult)
   {
     // Clear previous loaded graphs to not spend too much memory at one time.
@@ -903,17 +903,17 @@ RouterResultCode IndexRouter::ProcessLeapsJoints(vector<Segment> const & input,
 
     fillMwmIds(start, end, mwmIds);
 
-    AStarAlgorithm<IndexGraphStarterJoints>::Params params(
+    AStarAlgorithm<IndexGraphStarterJoints<IndexGraphStarter>>::Params params(
       jointStarter, jointStarter.GetStartJoint(), jointStarter.GetFinishJoint(),
       nullptr /* prevRoute */, delegate,
       {} /* onVisitedVertexCallback */, checkLength);
 
-    return FindPath<IndexGraphStarterJoints>(params, mwmIds, routingResult);
+    return FindPath<IndexGraphStarterJoints<IndexGraphStarter>>(params, mwmIds, routingResult);
   };
 
   deque<vector<Segment>> paths;
   size_t prevStart = numeric_limits<size_t>::max();
-  auto const tryBuildRoute = [&](size_t start, size_t end, WorldGraph::Mode mode,
+  auto const tryBuildRoute = [&](size_t start, size_t end, WorldGraphMode mode,
                                  RoutingResult<JointSegment, RouteWeight> & routingResult)
   {
     RouterResultCode const result = runAStarAlgorithm(start, end, mode, routingResult);
@@ -965,7 +965,7 @@ RouterResultCode IndexRouter::ProcessLeapsJoints(vector<Segment> const & input,
       next = i + 1;
     }
 
-    if (!tryBuildRoute(prev, next, WorldGraph::Mode::JointSingleMwm, routingResult))
+    if (!tryBuildRoute(prev, next, WorldGraphMode::JointSingleMwm, routingResult))
     {
       auto const prevPoint = starter.GetPoint(input[next], true);
       // |next + 1| - is the twin of |next|
@@ -989,7 +989,7 @@ RouterResultCode IndexRouter::ProcessLeapsJoints(vector<Segment> const & input,
       else
         next += 2;
 
-      if (!tryBuildRoute(prev, next, WorldGraph::Mode::Joints, routingResult))
+      if (!tryBuildRoute(prev, next, WorldGraphMode::Joints, routingResult))
       {
         // Already in start
         if (prev == 0)
@@ -1000,7 +1000,7 @@ RouterResultCode IndexRouter::ProcessLeapsJoints(vector<Segment> const & input,
           dropFirstSegment = false;
 
         CHECK_GREATER_OR_EQUAL(prev, 0, ());
-        if (!tryBuildRoute(prev, next, WorldGraph::Mode::Joints, routingResult))
+        if (!tryBuildRoute(prev, next, WorldGraphMode::Joints, routingResult))
           return RouterResultCode::RouteNotFound;
       }
     }
@@ -1034,7 +1034,7 @@ RouterResultCode IndexRouter::RedressRoute(vector<Segment> const & segments,
     junctions.emplace_back(starter.GetRouteJunction(segments, i));
 
   IndexRoadGraph roadGraph(m_numMwmIds, starter, segments, junctions, m_dataSource);
-  starter.GetGraph().SetMode(WorldGraph::Mode::NoLeaps);
+  starter.GetGraph().SetMode(WorldGraphMode::NoLeaps);
 
   Route::TTimes times;
   times.reserve(segments.size());
diff --git a/routing/index_router.hpp b/routing/index_router.hpp
index a0c1c0dd08..82aebd1466 100644
--- a/routing/index_router.hpp
+++ b/routing/index_router.hpp
@@ -111,7 +111,7 @@ private:
   // Input route may contains 'leaps': shortcut edges from mwm border enter to exit.
   // ProcessLeaps replaces each leap with calculated route through mwm.
   RouterResultCode ProcessLeapsJoints(vector<Segment> const & input, RouterDelegate const & delegate,
-                                      WorldGraph::Mode prevMode, IndexGraphStarter & starter,
+                                      WorldGraphMode prevMode, IndexGraphStarter & starter,
                                       vector<Segment> & output);
   RouterResultCode RedressRoute(std::vector<Segment> const & segments,
                                 RouterDelegate const & delegate, IndexGraphStarter & starter,
@@ -146,7 +146,7 @@ private:
       RoutingResult<typename Graph::Vertex, typename Graph::Weight> & routingResult) const
   {
     AStarAlgorithm<Graph> algorithm;
-    if (params.m_graph.GetMode() == WorldGraph::Mode::LeapsOnly)
+    if (params.m_graph.GetMode() == WorldGraphMode::LeapsOnly)
     {
       return ConvertTransitResult(mwmIds,
                                   ConvertResult<Graph>(algorithm.FindPath(params, routingResult)));
diff --git a/routing/joint_segment.cpp b/routing/joint_segment.cpp
index f33feaab58..66658a5724 100644
--- a/routing/joint_segment.cpp
+++ b/routing/joint_segment.cpp
@@ -6,10 +6,16 @@
 
 namespace routing
 {
+bool IsRealSegment(Segment const & segment)
+{
+  return segment.GetSegmentIdx() != std::numeric_limits<uint32_t>::max();
+}
 
 JointSegment::JointSegment(Segment const & from, Segment const & to)
 {
-  CHECK(from.IsRealSegment() && to.IsRealSegment(),
+  // Can not check segment for fake or not with segment.IsRealSegment(), because all segments
+  // have got fake m_numMwmId during mwm generation.
+  CHECK(IsRealSegment(from) && IsRealSegment(to),
         ("Segments of joints can not be fake. Only through ToFake() method."));
 
   CHECK_EQUAL(from.GetMwmId(), to.GetMwmId(), ("Different mwmIds in segments for JointSegment"));
diff --git a/routing/joint_segment.hpp b/routing/joint_segment.hpp
index ae49cab097..9655769c18 100644
--- a/routing/joint_segment.hpp
+++ b/routing/joint_segment.hpp
@@ -38,6 +38,11 @@ public:
   bool operator<(JointSegment const & rhs) const;
   bool operator==(JointSegment const & rhs) const;
 
+  bool operator!=(JointSegment const & rhs) const
+  {
+    return !(*this == rhs);
+  }
+
 private:
   static uint32_t constexpr kInvalidId = std::numeric_limits<uint32_t>::max();
   uint32_t m_featureId = kInvalidId;
diff --git a/routing/single_vehicle_world_graph.cpp b/routing/single_vehicle_world_graph.cpp
index 0e8db521cd..3860fd61a8 100644
--- a/routing/single_vehicle_world_graph.cpp
+++ b/routing/single_vehicle_world_graph.cpp
@@ -73,14 +73,14 @@ void SingleVehicleWorldGraph::GetEdgeList(Segment const & parent, bool isOutgoin
   auto & indexGraph = GetIndexGraph(parent.GetMwmId());
   indexGraph.GetEdgeList(parent, isOutgoing, jointEdges, parentWeights);
 
-  if (m_mode != WorldGraph::Mode::JointSingleMwm)
+  if (m_mode != WorldGraphMode::JointSingleMwm)
     CheckAndProcessTransitFeatures(parent, jointEdges, parentWeights, isOutgoing);
 }
 
 void SingleVehicleWorldGraph::GetEdgeList(Segment const & segment, bool isOutgoing,
                                           vector<SegmentEdge> & edges)
 {
-  if (m_mode == Mode::LeapsOnly)
+  if (m_mode == WorldGraphMode::LeapsOnly)
   {
     CHECK(m_crossMwmGraph, ());
     // Ingoing edges listing is not supported for leaps because we do not have enough information
@@ -97,14 +97,14 @@ void SingleVehicleWorldGraph::GetEdgeList(Segment const & segment, bool isOutgoi
   IndexGraph & indexGraph = m_loader->GetIndexGraph(segment.GetMwmId());
   indexGraph.GetEdgeList(segment, isOutgoing, edges);
 
-  if (m_mode != Mode::JointSingleMwm && m_crossMwmGraph && m_crossMwmGraph->IsTransition(segment, isOutgoing))
+  if (m_mode != WorldGraphMode::SingleMwm && m_crossMwmGraph && m_crossMwmGraph->IsTransition(segment, isOutgoing))
     GetTwins(segment, isOutgoing, edges);
 }
 
 Junction const & SingleVehicleWorldGraph::GetJunction(Segment const & segment, bool front)
 {
   return GetRoadGeometry(segment.GetMwmId(), segment.GetFeatureId())
-      .GetJunction(segment.GetPointId(front));
+         .GetJunction(segment.GetPointId(front));
 }
 
 m2::PointD const & SingleVehicleWorldGraph::GetPoint(Segment const & segment, bool front)
diff --git a/routing/single_vehicle_world_graph.hpp b/routing/single_vehicle_world_graph.hpp
index 20827a4efa..e29e459084 100644
--- a/routing/single_vehicle_world_graph.hpp
+++ b/routing/single_vehicle_world_graph.hpp
@@ -43,8 +43,8 @@ public:
   bool IsOneWay(NumMwmId mwmId, uint32_t featureId) override;
   bool IsPassThroughAllowed(NumMwmId mwmId, uint32_t featureId) override;
   void ClearCachedGraphs() override { m_loader->Clear(); }
-  void SetMode(Mode mode) override { m_mode = mode; }
-  Mode GetMode() const override { return m_mode; }
+  void SetMode(WorldGraphMode mode) override { m_mode = mode; }
+  WorldGraphMode GetMode() const override { return m_mode; }
   void GetOutgoingEdgesList(Segment const & segment, std::vector<SegmentEdge> & edges) override;
   void GetIngoingEdgesList(Segment const & segment, std::vector<SegmentEdge> & edges) override;
   RouteWeight HeuristicCostEstimate(Segment const & from, Segment const & to) override;
@@ -91,7 +91,7 @@ private:
   std::unique_ptr<CrossMwmGraph> m_crossMwmGraph;
   std::unique_ptr<IndexGraphLoader> m_loader;
   std::shared_ptr<EdgeEstimator> m_estimator;
-  Mode m_mode = Mode::NoLeaps;
   RoutingOptions m_avoidRoutingOptions = RoutingOptions();
+  WorldGraphMode m_mode = WorldGraphMode::NoLeaps;
 };
 }  // namespace routing
diff --git a/routing/transit_world_graph.cpp b/routing/transit_world_graph.cpp
index 9ca2a88077..a1b2882bdc 100644
--- a/routing/transit_world_graph.cpp
+++ b/routing/transit_world_graph.cpp
@@ -192,7 +192,7 @@ std::vector<RouteSegment::SpeedCamera> TransitWorldGraph::GetSpeedCamInfo(Segmen
 void TransitWorldGraph::GetTwinsInner(Segment const & segment, bool isOutgoing,
                                       vector<Segment> & twins)
 {
-  if (m_mode == Mode::SingleMwm || !m_crossMwmGraph ||
+  if (m_mode == WorldGraphMode::SingleMwm || !m_crossMwmGraph ||
       !m_crossMwmGraph->IsTransition(segment, isOutgoing))
   {
     return;
diff --git a/routing/transit_world_graph.hpp b/routing/transit_world_graph.hpp
index 01621cd5a9..453383e577 100644
--- a/routing/transit_world_graph.hpp
+++ b/routing/transit_world_graph.hpp
@@ -48,8 +48,8 @@ public:
   // All transit features are allowed for through passage.
   bool IsPassThroughAllowed(NumMwmId mwmId, uint32_t featureId) override;
   void ClearCachedGraphs() override;
-  void SetMode(Mode mode) override { m_mode = mode; }
-  Mode GetMode() const override { return m_mode; }
+  void SetMode(WorldGraphMode mode) override { m_mode = mode; }
+  WorldGraphMode GetMode() const override { return m_mode; }
   void GetOutgoingEdgesList(Segment const & segment, std::vector<SegmentEdge> & edges) override;
   void GetIngoingEdgesList(Segment const & segment, std::vector<SegmentEdge> & edges) override;
   RouteWeight HeuristicCostEstimate(Segment const & from, Segment const & to) override;
@@ -92,7 +92,7 @@ private:
   std::unique_ptr<IndexGraphLoader> m_indexLoader;
   std::unique_ptr<TransitGraphLoader> m_transitLoader;
   std::shared_ptr<EdgeEstimator> m_estimator;
-  Mode m_mode = Mode::NoLeaps;
+  WorldGraphMode m_mode = WorldGraphMode::NoLeaps;
   std::vector<Segment> const kEmptyTransitions = {};
 };
 }  // namespace routing
diff --git a/routing/world_graph.cpp b/routing/world_graph.cpp
index aff4c60f69..d0b3d5c60b 100644
--- a/routing/world_graph.cpp
+++ b/routing/world_graph.cpp
@@ -7,7 +7,7 @@ void WorldGraph::GetTwins(Segment const & segment, bool isOutgoing, std::vector<
   std::vector<Segment> twins;
   GetTwinsInner(segment, isOutgoing, twins);
 
-  if (GetMode() == Mode::LeapsOnly)
+  if (GetMode() == WorldGraphMode::LeapsOnly)
   {
     // Ingoing edges listing is not supported in LeapsOnly mode because we do not have enough
     // information to calculate |segment| weight. See https://jira.mail.ru/browse/MAPSME-5743 for details.
@@ -28,7 +28,7 @@ void WorldGraph::GetTwins(Segment const & segment, bool isOutgoing, std::vector<
   }
 
   auto prevMode = GetMode();
-  SetMode(Mode::SingleMwm);
+  SetMode(WorldGraphMode::SingleMwm);
 
   for (Segment const & twin : twins)
     GetEdgeList(twin, isOutgoing, edges);
@@ -48,15 +48,16 @@ bool WorldGraph::IsRoutingOptionsGood(Segment const & /* segment */)
 
 void WorldGraph::SetRoutingOptions(RoutingOptions /* routingOption */) {}
 
-std::string DebugPrint(WorldGraph::Mode mode)
+std::string DebugPrint(WorldGraphMode mode)
 {
   switch (mode)
   {
-  case WorldGraph::Mode::LeapsOnly: return "LeapsOnly";
-  case WorldGraph::Mode::NoLeaps: return "NoLeaps";
-  case WorldGraph::Mode::SingleMwm: return "SingleMwm";
-  case WorldGraph::Mode::Joints: return "Joints";
-  case WorldGraph::Mode::JointSingleMwm: return "JointsSingleMwm";
+  case WorldGraphMode::LeapsOnly: return "LeapsOnly";
+  case WorldGraphMode::NoLeaps: return "NoLeaps";
+  case WorldGraphMode::SingleMwm: return "SingleMwm";
+  case WorldGraphMode::Joints: return "Joints";
+  case WorldGraphMode::JointSingleMwm: return "JointsSingleMwm";
+  case WorldGraphMode::Undefined: return "Undefined";
   }
 
   UNREACHABLE();
diff --git a/routing/world_graph.hpp b/routing/world_graph.hpp
index 882d26dbfb..d4d4dd082c 100644
--- a/routing/world_graph.hpp
+++ b/routing/world_graph.hpp
@@ -20,6 +20,20 @@
 
 namespace routing
 {
+enum class WorldGraphMode
+{
+  LeapsOnly,       // Mode for building a cross mwm route containing only leaps. In case of start and
+                   // finish they (start and finish) will be connected with all transition segments of
+                   // their mwm with leap (fake) edges.
+  NoLeaps,         // Mode for building route and getting outgoing/ingoing edges without leaps at all.
+  SingleMwm,       // Mode for building route and getting outgoing/ingoing edges within mwm source
+                   // segment belongs to.
+  Joints,          // Mode for building route with jumps between Joints.
+  JointSingleMwm,  // Like |SingleMwm|, but in |Joints| mode.
+
+  Undefined        // Default mode, until initialization.
+};
+
 class WorldGraph
 {
 public:
@@ -28,18 +42,6 @@ public:
   using Edge = IndexGraph::Edge;
   using Weight = IndexGraph::Weight;
 
-  enum class Mode
-  {
-    LeapsOnly,      // Mode for building a cross mwm route containing only leaps. In case of start and
-                    // finish they (start and finish) will be connected with all transition segments of
-                    // their mwm with leap (fake) edges.
-    NoLeaps,        // Mode for building route and getting outgoing/ingoing edges without leaps at all.
-    SingleMwm,      // Mode for building route and getting outgoing/ingoing edges within mwm source
-                    // segment belongs to.
-    Joints,         // Mode for building route with jumps between Joints.
-    JointSingleMwm  // Like |SingleMwm|, but in |Joints| mode.
-  };
-
   virtual ~WorldGraph() = default;
 
   virtual void GetEdgeList(Segment const & segment, bool isOutgoing,
@@ -60,8 +62,8 @@ public:
 
   // Clear memory used by loaded graphs.
   virtual void ClearCachedGraphs() = 0;
-  virtual void SetMode(Mode mode) = 0;
-  virtual Mode GetMode() const = 0;
+  virtual void SetMode(WorldGraphMode mode) = 0;
+  virtual WorldGraphMode GetMode() const = 0;
 
   // Interface for AStarAlgorithm:
   virtual void GetOutgoingEdgesList(Segment const & segment, std::vector<SegmentEdge> & edges) = 0;
@@ -96,5 +98,5 @@ protected:
                              std::vector<Segment> & twins) = 0;
 };
 
-std::string DebugPrint(WorldGraph::Mode mode);
+std::string DebugPrint(WorldGraphMode mode);
 }  // namespace routing