Pull request #4672 review fixesindex-routing

33 files changed, 504 insertions, 401 deletions

diff --git a/generator/routing_index_generator.cpp b/generator/routing_index_generator.cpp
index d301f231a4..078f16eb13 100644
--- a/generator/routing_index_generator.cpp
+++ b/generator/routing_index_generator.cpp
@@ -12,6 +12,7 @@
 
 #include "base/logging.hpp"
 
+#include "std/bind.hpp"
 #include "std/unordered_map.hpp"
 #include "std/vector.hpp"
 
@@ -26,8 +27,7 @@ class Processor final
 public:
   void ProcessAllFeatures(string const & filename)
   {
-    feature::ForEachFromDat(filename,
-                            [this](FeatureType const & f, uint32_t id) { ProcessFeature(f, id); });
+    feature::ForEachFromDat(filename, bind(&Processor::ProcessFeature, this, _1, _2));
   }
 
   void BuildGraph(IndexGraph & graph) const
diff --git a/map/framework.cpp b/map/framework.cpp
index 609f01cfb1..052b83a3c9 100644
--- a/map/framework.cpp
+++ b/map/framework.cpp
@@ -8,13 +8,13 @@
 #include "defines.hpp"
 #include "private.h"
 
-#include "routing/astar_router.hpp"
 #include "routing/car_router.hpp"
 #include "routing/online_absent_fetcher.hpp"
 #include "routing/road_graph_router.hpp"
 #include "routing/route.hpp"
 #include "routing/routing_algorithm.hpp"
 #include "routing/routing_helpers.hpp"
+#include "routing/single_mwm_router.hpp"
 
 #include "search/downloader_search_callback.hpp"
 #include "search/editor_delegate.hpp"
@@ -2446,7 +2446,7 @@ void Framework::SetRouterImpl(RouterType type)
 
     router.reset(
         new CarRouter(m_model.GetIndex(), countryFileGetter,
-                      CreateCarAStarBidirectionalRouter(m_model.GetIndex())));
+                      SingleMwmRouter::CreateCarRouter(m_model.GetIndex())));
     fetcher.reset(new OnlineAbsentCountriesFetcher(countryFileGetter, localFileChecker));
     m_routingSession.SetRoutingSettings(routing::GetCarRoutingSettings());
   }
diff --git a/routing/base/astar_algorithm.hpp b/routing/base/astar_algorithm.hpp
index 103468b17c..1c753701b3 100644
--- a/routing/base/astar_algorithm.hpp
+++ b/routing/base/astar_algorithm.hpp
@@ -61,13 +61,13 @@ public:
 
   using TOnVisitedVertexCallback = std::function<void(TVertexType const &, TVertexType const &)>;
 
-  Result FindPath(TGraphType const & graph,
+  Result FindPath(TGraphType & graph,
                   TVertexType const & startVertex, TVertexType const & finalVertex,
                   RoutingResult<TVertexType> & result,
                   my::Cancellable const & cancellable = my::Cancellable(),
                   TOnVisitedVertexCallback onVisitedVertexCallback = nullptr) const;
 
-  Result FindPathBidirectional(TGraphType const & graph,
+  Result FindPathBidirectional(TGraphType & graph,
                                TVertexType const & startVertex, TVertexType const & finalVertex,
                                RoutingResult<TVertexType> & result,
                                my::Cancellable const & cancellable = my::Cancellable(),
@@ -104,7 +104,7 @@ private:
   struct BidirectionalStepContext
   {
     BidirectionalStepContext(bool forward, TVertexType const & startVertex,
-                             TVertexType const & finalVertex, TGraphType const & graph)
+                             TVertexType const & finalVertex, TGraphType & graph)
         : forward(forward), startVertex(startVertex), finalVertex(finalVertex), graph(graph)
     {
       bestVertex = forward ? startVertex : finalVertex;
@@ -151,7 +151,7 @@ private:
     bool const forward;
     TVertexType const & startVertex;
     TVertexType const & finalVertex;
-    TGraph const & graph;
+    TGraph & graph;
 
     priority_queue<State, vector<State>, greater<State>> queue;
     map<TVertexType, double> bestDistance;
@@ -182,7 +182,7 @@ private:
 
 template <typename TGraph>
 typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPath(
-    TGraphType const & graph,
+    TGraphType & graph,
     TVertexType const & startVertex, TVertexType const & finalVertex,
     RoutingResult<TVertexType> & result,
     my::Cancellable const & cancellable,
@@ -257,7 +257,7 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPath(
 
 template <typename TGraph>
 typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPathBidirectional(
-    TGraphType const & graph,
+    TGraphType & graph,
     TVertexType const & startVertex, TVertexType const & finalVertex,
     RoutingResult<TVertexType> & result,
     my::Cancellable const & cancellable,
diff --git a/routing/car_router.cpp b/routing/car_router.cpp
index 08c13421a1..24ac35d1e4 100644
--- a/routing/car_router.cpp
+++ b/routing/car_router.cpp
@@ -244,7 +244,7 @@ bool CarRouter::CheckRoutingAbility(m2::PointD const & startPoint, m2::PointD co
 }
 
 CarRouter::CarRouter(Index & index, TCountryFileFn const & countryFileFn,
-                     unique_ptr<AStarRouter> localRouter)
+                     unique_ptr<SingleMwmRouter> localRouter)
   : m_index(index), m_indexManager(countryFileFn, index), m_router(move(localRouter))
 {
 }
diff --git a/routing/car_router.hpp b/routing/car_router.hpp
index 4f974869d5..29f6693813 100644
--- a/routing/car_router.hpp
+++ b/routing/car_router.hpp
@@ -1,11 +1,11 @@
 #pragma once
 
-#include "routing/astar_router.hpp"
 #include "routing/osrm_data_facade.hpp"
 #include "routing/osrm_engine.hpp"
 #include "routing/route.hpp"
 #include "routing/router.hpp"
 #include "routing/routing_mapping.hpp"
+#include "routing/single_mwm_router.hpp"
 
 #include "std/unique_ptr.hpp"
 #include "std/vector.hpp"
@@ -35,7 +35,7 @@ public:
   typedef vector<double> GeomTurnCandidateT;
 
   CarRouter(Index & index, TCountryFileFn const & countryFileFn,
-            unique_ptr<AStarRouter> localRouter);
+            unique_ptr<SingleMwmRouter> localRouter);
 
   virtual string GetName() const override;
 
@@ -115,6 +115,6 @@ private:
 
   RoutingIndexManager m_indexManager;
 
-  unique_ptr<AStarRouter> m_router;
+  unique_ptr<SingleMwmRouter> m_router;
 };
 }  // namespace routing
diff --git a/routing/cross_mwm_router.cpp b/routing/cross_mwm_router.cpp
index 7d398ca9af..6b3bc3aef3 100644
--- a/routing/cross_mwm_router.cpp
+++ b/routing/cross_mwm_router.cpp
@@ -10,7 +10,7 @@ namespace
 {
 /// Function to run AStar Algorithm from the base.
 IRouter::ResultCode CalculateRoute(BorderCross const & startPos, BorderCross const & finalPos,
-                                   CrossMwmGraph const & roadGraph, RouterDelegate const & delegate,
+                                   CrossMwmGraph & roadGraph, RouterDelegate const & delegate,
                                    RoutingResult<BorderCross> & route)
 {
   using TAlgorithm = AStarAlgorithm<CrossMwmGraph>;
diff --git a/routing/directions_engine.cpp b/routing/directions_engine.cpp
index c054c9a74f..53d5ed602a 100644
--- a/routing/directions_engine.cpp
+++ b/routing/directions_engine.cpp
@@ -87,39 +87,4 @@ bool IDirectionsEngine::ReconstructPath(IRoadGraph const & graph, vector<Junctio
 
   return true;
 }
-
-void ReconstructRoute(IDirectionsEngine * engine, IRoadGraph const & graph,
-                      my::Cancellable const & cancellable, vector<Junction> & path, Route & route)
-{
-  if (path.empty())
-  {
-    LOG(LERROR, ("Can't reconstruct route from an empty list of positions."));
-    return;
-  }
-
-  // By some reason there're two adjacent positions on a road with
-  // the same end-points. This could happen, for example, when
-  // direction on a road was changed.  But it doesn't matter since
-  // this code reconstructs only geometry of a route.
-  path.erase(unique(path.begin(), path.end()), path.end());
-
-  Route::TTimes times;
-  Route::TTurns turnsDir;
-  vector<Junction> junctions;
-  // @TODO(bykoianko) streetNames is not filled in Generate(). It should be done.
-  Route::TStreets streetNames;
-  if (engine)
-    engine->Generate(graph, path, times, turnsDir, junctions, cancellable);
-
-  vector<m2::PointD> routeGeometry;
-  JunctionsToPoints(junctions, routeGeometry);
-  feature::TAltitudes altitudes;
-  JunctionsToAltitudes(junctions, altitudes);
-
-  route.SetGeometry(routeGeometry.begin(), routeGeometry.end());
-  route.SetSectionTimes(move(times));
-  route.SetTurnInstructions(move(turnsDir));
-  route.SetStreetNames(move(streetNames));
-  route.SetAltitudes(move(altitudes));
-}
 }  // namespace routing
diff --git a/routing/directions_engine.hpp b/routing/directions_engine.hpp
index c82b1c5d59..7893e9b5c4 100644
--- a/routing/directions_engine.hpp
+++ b/routing/directions_engine.hpp
@@ -28,7 +28,4 @@ protected:
   void CalculateTimes(IRoadGraph const & graph, vector<Junction> const & path,
                       Route::TTimes & times) const;
 };
-
-void ReconstructRoute(IDirectionsEngine * engine, IRoadGraph const & graph,
-                      my::Cancellable const & cancellable, vector<Junction> & path, Route & route);
 }  // namespace routing
diff --git a/routing/edge_estimator.cpp b/routing/edge_estimator.cpp
index 4bf6f8579e..52cb10905a 100644
--- a/routing/edge_estimator.cpp
+++ b/routing/edge_estimator.cpp
@@ -17,7 +17,7 @@ inline double TimeBetweenSec(m2::PointD const & from, m2::PointD const & to, dou
 class CarEdgeEstimator : public EdgeEstimator
 {
 public:
-  CarEdgeEstimator(shared_ptr<IVehicleModel> vehicleModel);
+  CarEdgeEstimator(IVehicleModel const & vehicleModel);
 
   // EdgeEstimator overrides:
   double CalcEdgesWeight(RoadGeometry const & road, uint32_t pointFrom,
@@ -28,8 +28,8 @@ private:
   double const m_maxSpeedMPS;
 };
 
-CarEdgeEstimator::CarEdgeEstimator(shared_ptr<IVehicleModel> vehicleModel)
-  : m_maxSpeedMPS(vehicleModel->GetMaxSpeed() * kKMPH2MPS)
+CarEdgeEstimator::CarEdgeEstimator(IVehicleModel const & vehicleModel)
+  : m_maxSpeedMPS(vehicleModel.GetMaxSpeed() * kKMPH2MPS)
 {
 }
 
@@ -56,7 +56,8 @@ double CarEdgeEstimator::CalcHeuristic(m2::PointD const & from, m2::PointD const
 
 namespace routing
 {
-shared_ptr<EdgeEstimator> CreateCarEdgeEstimator(shared_ptr<IVehicleModel> vehicleModel)
+// static
+shared_ptr<EdgeEstimator> EdgeEstimator::CreateForCar(IVehicleModel const & vehicleModel)
 {
   return make_shared<CarEdgeEstimator>(vehicleModel);
 }
diff --git a/routing/edge_estimator.hpp b/routing/edge_estimator.hpp
index 50a6591a47..0a6ec2d1e0 100644
--- a/routing/edge_estimator.hpp
+++ b/routing/edge_estimator.hpp
@@ -18,7 +18,7 @@ public:
   virtual double CalcEdgesWeight(RoadGeometry const & road, uint32_t pointFrom,
                                  uint32_t pointTo) const = 0;
   virtual double CalcHeuristic(m2::PointD const & from, m2::PointD const & to) const = 0;
-};
 
-shared_ptr<EdgeEstimator> CreateCarEdgeEstimator(shared_ptr<IVehicleModel> vehicleModel);
+  static shared_ptr<EdgeEstimator> CreateForCar(IVehicleModel const & vehicleModel);
+};
 }  // namespace routing
diff --git a/routing/geometry.cpp b/routing/geometry.cpp
index 38c3359b0b..9336740db3 100644
--- a/routing/geometry.cpp
+++ b/routing/geometry.cpp
@@ -1,9 +1,13 @@
-#include "geometry.hpp"
+#include "routing/geometry.hpp"
+
+#include "routing/routing_exception.hpp"
 
 #include "geometry/mercator.hpp"
 
 #include "base/assert.hpp"
 
+#include "std/string.hpp"
+
 using namespace routing;
 
 namespace
@@ -11,22 +15,22 @@ namespace
 class GeometryLoaderImpl final : public GeometryLoader
 {
 public:
-  GeometryLoaderImpl(Index const & index, MwmSet::MwmId const & mwmId,
+  GeometryLoaderImpl(Index const & index, MwmSet::MwmId const & mwmId, string const & country,
                      shared_ptr<IVehicleModel> vehicleModel);
 
   // GeometryLoader overrides:
   virtual void Load(uint32_t featureId, RoadGeometry & road) const override;
 
 private:
-  Index const & m_index;
-  MwmSet::MwmId const m_mwmId;
   shared_ptr<IVehicleModel> m_vehicleModel;
   Index::FeaturesLoaderGuard m_guard;
+  string const m_country;
 };
 
 GeometryLoaderImpl::GeometryLoaderImpl(Index const & index, MwmSet::MwmId const & mwmId,
+                                       string const & country,
                                        shared_ptr<IVehicleModel> vehicleModel)
-  : m_index(index), m_mwmId(mwmId), m_vehicleModel(vehicleModel), m_guard(m_index, m_mwmId)
+  : m_vehicleModel(vehicleModel), m_guard(index, mwmId), m_country(country)
 {
   ASSERT(m_vehicleModel, ());
 }
@@ -36,10 +40,7 @@ void GeometryLoaderImpl::Load(uint32_t featureId, RoadGeometry & road) const
   FeatureType feature;
   bool const isFound = m_guard.GetFeatureByIndex(featureId, feature);
   if (!isFound)
-  {
-    LOG(LERROR, ("Feature", featureId, "not found"));
-    return;
-  }
+    MYTHROW(RoutingException, ("Feature", featureId, "not found in ", m_country));
 
   feature.ParseGeometry(FeatureType::BEST_GEOMETRY);
   road.Load(*m_vehicleModel, feature);
@@ -48,9 +49,11 @@ void GeometryLoaderImpl::Load(uint32_t featureId, RoadGeometry & road) const
 
 namespace routing
 {
+// RoadGeometry ------------------------------------------------------------------------------------
 RoadGeometry::RoadGeometry(bool oneWay, double speed, Points const & points)
-  : m_isRoad(true), m_isOneWay(oneWay), m_speed(speed), m_points(points)
+  : m_points(points), m_speed(speed), m_isRoad(true), m_isOneWay(oneWay)
 {
+  ASSERT_GREATER(speed, 0.0, ());
 }
 
 void RoadGeometry::Load(IVehicleModel const & vehicleModel, FeatureType const & feature)
@@ -59,19 +62,35 @@ void RoadGeometry::Load(IVehicleModel const & vehicleModel, FeatureType const &
   m_isOneWay = vehicleModel.IsOneWay(feature);
   m_speed = vehicleModel.GetSpeed(feature);
 
+  m_points.clear();
   m_points.reserve(feature.GetPointsCount());
   for (size_t i = 0; i < feature.GetPointsCount(); ++i)
     m_points.emplace_back(feature.GetPoint(i));
 }
 
+// Geometry ----------------------------------------------------------------------------------------
 Geometry::Geometry(unique_ptr<GeometryLoader> loader) : m_loader(move(loader))
 {
   ASSERT(m_loader, ());
 }
 
-unique_ptr<GeometryLoader> CreateGeometryLoader(Index const & index, MwmSet::MwmId const & mwmId,
-                                                shared_ptr<IVehicleModel> vehicleModel)
+RoadGeometry const & Geometry::GetRoad(uint32_t featureId)
+{
+  auto const & it = m_roads.find(featureId);
+  if (it != m_roads.cend())
+    return it->second;
+
+  RoadGeometry & road = m_roads[featureId];
+  m_loader->Load(featureId, road);
+  return road;
+}
+
+// static
+unique_ptr<GeometryLoader> GeometryLoader::Create(Index const & index, MwmSet::MwmId const & mwmId,
+                                                  shared_ptr<IVehicleModel> vehicleModel)
 {
-  return make_unique<GeometryLoaderImpl>(index, mwmId, vehicleModel);
+  CHECK(mwmId.IsAlive(), ());
+  return make_unique<GeometryLoaderImpl>(index, mwmId, mwmId.GetInfo()->GetCountryName(),
+                                         vehicleModel);
 }
 }  // namespace routing
diff --git a/routing/geometry.hpp b/routing/geometry.hpp
index a98f649cf3..c6fc91c318 100644
--- a/routing/geometry.hpp
+++ b/routing/geometry.hpp
@@ -29,7 +29,8 @@ public:
 
   bool IsOneWay() const { return m_isOneWay; }
 
-  bool GetSpeed() const { return m_speed; }
+  // Kilometers per hour.
+  double GetSpeed() const { return m_speed; }
 
   m2::PointD const & GetPoint(uint32_t pointId) const
   {
@@ -40,10 +41,10 @@ public:
   uint32_t GetPointsCount() const { return m_points.size(); }
 
 private:
+  Points m_points;
+  double m_speed = 0.0;
   bool m_isRoad = false;
   bool m_isOneWay = false;
-  double m_speed = 0.0;
-  Points m_points;
 };
 
 class GeometryLoader
@@ -52,6 +53,10 @@ public:
   virtual ~GeometryLoader() = default;
 
   virtual void Load(uint32_t featureId, RoadGeometry & road) const = 0;
+
+  // mwmId should be alive: it is caller responsibility to check it.
+  static unique_ptr<GeometryLoader> Create(Index const & index, MwmSet::MwmId const & mwmId,
+                                           shared_ptr<IVehicleModel> vehicleModel);
 };
 
 class Geometry final
@@ -60,28 +65,16 @@ public:
   Geometry() = default;
   explicit Geometry(unique_ptr<GeometryLoader> loader);
 
-  RoadGeometry const & GetRoad(uint32_t featureId) const
-  {
-    auto const & it = m_roads.find(featureId);
-    if (it != m_roads.cend())
-      return it->second;
-
-    RoadGeometry & road = m_roads[featureId];
-    m_loader->Load(featureId, road);
-    return road;
-  }
+  RoadGeometry const & GetRoad(uint32_t featureId);
 
-  m2::PointD const & GetPoint(RoadPoint const & rp) const
+  m2::PointD const & GetPoint(RoadPoint const & rp)
   {
     return GetRoad(rp.GetFeatureId()).GetPoint(rp.GetPointId());
   }
 
 private:
   // Feature id to RoadGeometry map.
-  mutable unordered_map<uint32_t, RoadGeometry> m_roads;
+  unordered_map<uint32_t, RoadGeometry> m_roads;
   unique_ptr<GeometryLoader> m_loader;
 };
-
-unique_ptr<GeometryLoader> CreateGeometryLoader(Index const & index, MwmSet::MwmId const & mwmId,
-                                                shared_ptr<IVehicleModel> vehicleModel);
 }  // namespace routing
diff --git a/routing/index_graph.cpp b/routing/index_graph.cpp
index 6e3e0136c3..ae316a57af 100644
--- a/routing/index_graph.cpp
+++ b/routing/index_graph.cpp
@@ -11,14 +11,14 @@ IndexGraph::IndexGraph(unique_ptr<GeometryLoader> loader, shared_ptr<EdgeEstimat
   ASSERT(m_estimator, ());
 }
 
-void IndexGraph::GetEdgesList(Joint::Id jointId, bool isOutgoing, vector<JointEdge> & edges) const
+void IndexGraph::GetEdgeList(Joint::Id jointId, bool isOutgoing, vector<JointEdge> & edges)
 {
   m_jointIndex.ForEachPoint(jointId, [this, &edges, isOutgoing](RoadPoint const & rp) {
-    AddNeighboringEdges(rp, isOutgoing, edges);
+    GetNeighboringEdges(rp, isOutgoing, edges);
   });
 }
 
-m2::PointD const & IndexGraph::GetPoint(Joint::Id jointId) const
+m2::PointD const & IndexGraph::GetPoint(Joint::Id jointId)
 {
   return m_geometry.GetPoint(m_jointIndex.GetPoint(jointId));
 }
@@ -40,7 +40,7 @@ Joint::Id IndexGraph::InsertJoint(RoadPoint const & rp)
   return jointId;
 }
 
-bool IndexGraph::JointLaysOnRoad(Joint::Id jointId, uint32_t featureId) const
+bool IndexGraph::JointLiesOnRoad(Joint::Id jointId, uint32_t featureId) const
 {
   bool result = false;
   m_jointIndex.ForEachPoint(jointId, [&result, featureId](RoadPoint const & rp) {
@@ -51,8 +51,8 @@ bool IndexGraph::JointLaysOnRoad(Joint::Id jointId, uint32_t featureId) const
   return result;
 }
 
-inline void IndexGraph::AddNeighboringEdges(RoadPoint rp, bool isOutgoing,
-                                            vector<JointEdge> & edges) const
+void IndexGraph::GetNeighboringEdges(RoadPoint const & rp, bool isOutgoing,
+                                     vector<JointEdge> & edges)
 {
   RoadGeometry const & road = m_geometry.GetRoad(rp.GetFeatureId());
   if (!road.IsRoad())
@@ -60,14 +60,14 @@ inline void IndexGraph::AddNeighboringEdges(RoadPoint rp, bool isOutgoing,
 
   bool const bidirectional = !road.IsOneWay();
   if (!isOutgoing || bidirectional)
-    AddNeighboringEdge(road, rp, false /* forward */, edges);
+    GetNeighboringEdge(road, rp, false /* forward */, edges);
 
   if (isOutgoing || bidirectional)
-    AddNeighboringEdge(road, rp, true /* forward */, edges);
+    GetNeighboringEdge(road, rp, true /* forward */, edges);
 }
 
-inline void IndexGraph::AddNeighboringEdge(RoadGeometry const & road, RoadPoint rp, bool forward,
-                                           vector<JointEdge> & edges) const
+inline void IndexGraph::GetNeighboringEdge(RoadGeometry const & road, RoadPoint const & rp,
+                                           bool forward, vector<JointEdge> & edges) const
 {
   pair<Joint::Id, uint32_t> const & neighbor = m_roadIndex.FindNeighbor(rp, forward);
   if (neighbor.first != Joint::kInvalidId)
@@ -77,8 +77,8 @@ inline void IndexGraph::AddNeighboringEdge(RoadGeometry const & road, RoadPoint
   }
 }
 
-void IndexGraph::AddDirectEdge(uint32_t featureId, uint32_t pointFrom, uint32_t pointTo,
-                               Joint::Id target, bool forward, vector<JointEdge> & edges) const
+void IndexGraph::GetDirectedEdge(uint32_t featureId, uint32_t pointFrom, uint32_t pointTo,
+                                 Joint::Id target, bool forward, vector<JointEdge> & edges)
 {
   RoadGeometry const & road = m_geometry.GetRoad(featureId);
   if (!road.IsRoad())
diff --git a/routing/index_graph.hpp b/routing/index_graph.hpp
index 77ec8bb2a4..f6e6cf0379 100644
--- a/routing/index_graph.hpp
+++ b/routing/index_graph.hpp
@@ -39,25 +39,30 @@ public:
   IndexGraph() = default;
   explicit IndexGraph(unique_ptr<GeometryLoader> loader, shared_ptr<EdgeEstimator> estimator);
 
-  void AddDirectEdge(uint32_t featureId, uint32_t pointFrom, uint32_t pointTo, Joint::Id target,
-                     bool forward, vector<JointEdge> & edges) const;
-  void AddNeighboringEdges(RoadPoint rp, bool isOutgoing, vector<JointEdge> & edges) const;
-  void GetEdgesList(Joint::Id jointId, bool forward, vector<JointEdge> & edges) const;
-  Joint::Id GetJointId(RoadPoint rp) const { return m_roadIndex.GetJointId(rp); }
-  Geometry const & GetGeometry() const { return m_geometry; }
+  // Creates edge for points in same feature.
+  void GetDirectedEdge(uint32_t featureId, uint32_t pointFrom, uint32_t pointTo, Joint::Id target,
+                       bool forward, vector<JointEdge> & edges);
+  void GetNeighboringEdges(RoadPoint const & rp, bool isOutgoing, vector<JointEdge> & edges);
+
+  // Put outgoing (or ingoing) egdes for jointId to the 'edges' vector.
+  void GetEdgeList(Joint::Id jointId, bool isOutgoing, vector<JointEdge> & edges);
+  Joint::Id GetJointId(RoadPoint const & rp) const { return m_roadIndex.GetJointId(rp); }
+  m2::PointD const & GetPoint(Joint::Id jointId);
+
+  Geometry & GetGeometry() { return m_geometry; }
   EdgeEstimator const & GetEstimator() const { return *m_estimator; }
-  m2::PointD const & GetPoint(Joint::Id jointId) const;
   uint32_t GetNumRoads() const { return m_roadIndex.GetSize(); }
   uint32_t GetNumJoints() const { return m_jointIndex.GetNumJoints(); }
   uint32_t GetNumPoints() const { return m_jointIndex.GetNumPoints(); }
+
   void Import(vector<Joint> const & joints);
   Joint::Id InsertJoint(RoadPoint const & rp);
-  bool JointLaysOnRoad(Joint::Id jointId, uint32_t featureId) const;
+  bool JointLiesOnRoad(Joint::Id jointId, uint32_t featureId) const;
 
   template <typename F>
   void ForEachPoint(Joint::Id jointId, F && f) const
   {
-    m_jointIndex.ForEachPoint(jointId, f);
+    m_jointIndex.ForEachPoint(jointId, forward<F>(f));
   }
 
   template <class Sink>
@@ -76,7 +81,7 @@ public:
   }
 
 private:
-  void AddNeighboringEdge(RoadGeometry const & road, RoadPoint rp, bool forward,
+  void GetNeighboringEdge(RoadGeometry const & road, RoadPoint const & rp, bool forward,
                           vector<JointEdge> & edges) const;
 
   Geometry m_geometry;
diff --git a/routing/index_graph_starter.cpp b/routing/index_graph_starter.cpp
index 53f64a7b1b..5ae00512d6 100644
--- a/routing/index_graph_starter.cpp
+++ b/routing/index_graph_starter.cpp
@@ -1,99 +1,41 @@
 #include "routing/index_graph_starter.hpp"
 
+#include "routing/routing_exception.hpp"
+
 namespace routing
 {
-IndexGraphStarter::IndexGraphStarter(IndexGraph const & graph, RoadPoint startPoint,
-                                     RoadPoint finishPoint)
+IndexGraphStarter::IndexGraphStarter(IndexGraph & graph, RoadPoint const & startPoint,
+                                     RoadPoint const & finishPoint)
   : m_graph(graph)
-  , m_startPoint(startPoint)
-  , m_finishPoint(finishPoint)
-  , m_startImplant(graph.GetNumJoints())
-  , m_finishImplant(graph.GetNumJoints() + 1)
-  , m_startJoint(CalcStartJoint())
-  , m_finishJoint(CalcFinishJoint())
+  , m_start(graph, startPoint, graph.GetNumJoints())
+  , m_finish(graph, finishPoint, graph.GetNumJoints() + 1)
 {
-}
-
-Joint::Id IndexGraphStarter::CalcStartJoint() const
-{
-  Joint::Id const jointId = m_graph.GetJointId(m_startPoint);
-  if (jointId == Joint::kInvalidId)
-    return m_startImplant;
-
-  return jointId;
-}
-
-Joint::Id IndexGraphStarter::CalcFinishJoint() const
-{
-  if (m_startPoint == m_finishPoint)
-    return CalcStartJoint();
-
-  Joint::Id const jointId = m_graph.GetJointId(m_finishPoint);
-  if (jointId == Joint::kInvalidId)
-    return m_finishImplant;
+  m_start.SetupJointId(graph);
 
-  return jointId;
+  if (startPoint == finishPoint)
+    m_finish.m_jointId = m_start.m_jointId;
+  else
+    m_finish.SetupJointId(graph);
 }
 
-void IndexGraphStarter::GetEdgesList(Joint::Id jointId, bool isOutgoing,
-                                     vector<JointEdge> & edges) const
+m2::PointD const & IndexGraphStarter::GetPoint(Joint::Id jointId)
 {
-  edges.clear();
-
-  if (jointId == m_startImplant)
-  {
-    m_graph.AddNeighboringEdges(m_startPoint, isOutgoing, edges);
-
-    if (FinishIsImplant() && m_startPoint.GetFeatureId() == m_finishPoint.GetFeatureId())
-      m_graph.AddDirectEdge(m_startPoint.GetFeatureId(), m_startPoint.GetPointId(),
-                            m_finishPoint.GetPointId(), m_finishJoint, isOutgoing, edges);
-
-    return;
-  }
-
-  if (jointId == m_finishImplant)
-  {
-    m_graph.AddNeighboringEdges(m_finishPoint, isOutgoing, edges);
+  if (jointId == m_start.m_fakeId)
+    return m_graph.GetGeometry().GetPoint(m_start.m_point);
 
-    if (StartIsImplant() && m_startPoint.GetFeatureId() == m_finishPoint.GetFeatureId())
-      m_graph.AddDirectEdge(m_finishPoint.GetFeatureId(), m_finishPoint.GetPointId(),
-                            m_startPoint.GetPointId(), m_startJoint, isOutgoing, edges);
+  if (jointId == m_finish.m_fakeId)
+    return m_graph.GetGeometry().GetPoint(m_finish.m_point);
 
-    return;
-  }
-
-  m_graph.GetEdgesList(jointId, isOutgoing, edges);
-
-  if (StartIsImplant() && m_graph.JointLaysOnRoad(jointId, m_startPoint.GetFeatureId()))
-  {
-    vector<JointEdge> startEdges;
-    m_graph.AddNeighboringEdges(m_startPoint, !isOutgoing, startEdges);
-    for (JointEdge const & edge : startEdges)
-    {
-      if (edge.GetTarget() == jointId)
-        edges.emplace_back(m_startJoint, edge.GetWeight());
-    }
-  }
-
-  if (FinishIsImplant() && m_graph.JointLaysOnRoad(jointId, m_finishPoint.GetFeatureId()))
-  {
-    vector<JointEdge> finishEdges;
-    m_graph.AddNeighboringEdges(m_finishPoint, !isOutgoing, finishEdges);
-    for (JointEdge const & edge : finishEdges)
-    {
-      if (edge.GetTarget() == jointId)
-        edges.emplace_back(m_finishJoint, edge.GetWeight());
-    }
-  }
+  return m_graph.GetPoint(jointId);
 }
 
 void IndexGraphStarter::RedressRoute(vector<Joint::Id> const & route,
-                                     vector<RoadPoint> & roadPoints) const
+                                     vector<RoadPoint> & roadPoints)
 {
   if (route.size() < 2)
   {
     if (route.size() == 1)
-      roadPoints.emplace_back(m_startPoint);
+      roadPoints.emplace_back(m_start.m_point);
     return;
   }
 
@@ -126,62 +68,128 @@ void IndexGraphStarter::RedressRoute(vector<Joint::Id> const & route,
     }
     else
     {
-      MYTHROW(RootException,
-              ("Wrong equality pointFrom = pointTo =", pointFrom, ", featureId = ", featureId));
+      CHECK(false,
+            ("Wrong equality pointFrom = pointTo =", pointFrom, ", featureId = ", featureId));
     }
 
     roadPoints.emplace_back(rp1);
   }
 }
 
+void IndexGraphStarter::GetEdgesList(Joint::Id jointId, bool isOutgoing, vector<JointEdge> & edges)
+{
+  edges.clear();
+
+  if (jointId == m_start.m_fakeId)
+  {
+    GetFakeEdges(m_start, m_finish, isOutgoing, edges);
+    return;
+  }
+
+  if (jointId == m_finish.m_fakeId)
+  {
+    GetFakeEdges(m_finish, m_start, isOutgoing, edges);
+    return;
+  }
+
+  m_graph.GetEdgeList(jointId, isOutgoing, edges);
+  GetArrivalFakeEdges(jointId, m_start, isOutgoing, edges);
+  GetArrivalFakeEdges(jointId, m_finish, isOutgoing, edges);
+}
+
+void IndexGraphStarter::GetFakeEdges(IndexGraphStarter::FakeJoint const & from,
+                                     IndexGraphStarter::FakeJoint const & to, bool isOutgoing,
+                                     vector<JointEdge> & edges)
+{
+  m_graph.GetNeighboringEdges(from.m_point, isOutgoing, edges);
+
+  if (!to.BelongsToGraph() && from.m_point.GetFeatureId() == to.m_point.GetFeatureId())
+  {
+    m_graph.GetDirectedEdge(from.m_point.GetFeatureId(), from.m_point.GetPointId(),
+                            to.m_point.GetPointId(), to.m_jointId, isOutgoing, edges);
+  }
+}
+
+void IndexGraphStarter::GetArrivalFakeEdges(Joint::Id jointId,
+                                            IndexGraphStarter::FakeJoint const & fakeJoint,
+                                            bool isOutgoing, vector<JointEdge> & edges)
+{
+  if (fakeJoint.BelongsToGraph())
+    return;
+
+  if (!m_graph.JointLiesOnRoad(jointId, fakeJoint.m_point.GetFeatureId()))
+    return;
+
+  vector<JointEdge> startEdges;
+  m_graph.GetNeighboringEdges(fakeJoint.m_point, !isOutgoing, startEdges);
+  for (JointEdge const & edge : startEdges)
+  {
+    if (edge.GetTarget() == jointId)
+      edges.emplace_back(fakeJoint.m_jointId, edge.GetWeight());
+  }
+}
+
 void IndexGraphStarter::FindPointsWithCommonFeature(Joint::Id jointId0, Joint::Id jointId1,
-                                                    RoadPoint & result0, RoadPoint & result1) const
+                                                    RoadPoint & result0, RoadPoint & result1)
 {
   bool found = false;
   double minWeight = -1.0;
 
   ForEachPoint(jointId0, [&](RoadPoint const & rp0) {
     ForEachPoint(jointId1, [&](RoadPoint const & rp1) {
-      if (rp0.GetFeatureId() == rp1.GetFeatureId())
-      {
-        RoadGeometry const & road = m_graph.GetGeometry().GetRoad(rp0.GetFeatureId());
-        if (!road.IsRoad())
-          return;
+      if (rp0.GetFeatureId() != rp1.GetFeatureId())
+        return;
+
+      RoadGeometry const & road = m_graph.GetGeometry().GetRoad(rp0.GetFeatureId());
+      if (!road.IsRoad())
+        return;
 
-        if (road.IsOneWay() && rp0.GetPointId() > rp1.GetPointId())
-          return;
+      if (road.IsOneWay() && rp0.GetPointId() > rp1.GetPointId())
+        return;
 
-        if (found)
+      if (found)
+      {
+        if (minWeight < 0.0)
         {
-          if (minWeight < 0.0)
-          {
-            // CalcEdgesWeight is very expensive.
-            // So calculate it only if second common feature found.
-            RoadGeometry const & prevRoad = m_graph.GetGeometry().GetRoad(result0.GetFeatureId());
-            minWeight = m_graph.GetEstimator().CalcEdgesWeight(prevRoad, result0.GetPointId(),
-                                                               result1.GetPointId());
-          }
-
-          double const weight =
-              m_graph.GetEstimator().CalcEdgesWeight(road, rp0.GetPointId(), rp1.GetPointId());
-          if (weight < minWeight)
-          {
-            minWeight = weight;
-            result0 = rp0;
-            result1 = rp1;
-          }
+          // CalcEdgesWeight is very expensive.
+          // So calculate it only if second common feature found.
+          RoadGeometry const & prevRoad = m_graph.GetGeometry().GetRoad(result0.GetFeatureId());
+          minWeight = m_graph.GetEstimator().CalcEdgesWeight(prevRoad, result0.GetPointId(),
+                                                             result1.GetPointId());
         }
-        else
+
+        double const weight =
+            m_graph.GetEstimator().CalcEdgesWeight(road, rp0.GetPointId(), rp1.GetPointId());
+        if (weight < minWeight)
         {
+          minWeight = weight;
           result0 = rp0;
           result1 = rp1;
-          found = true;
         }
       }
+      else
+      {
+        result0 = rp0;
+        result1 = rp1;
+        found = true;
+      }
     });
   });
 
-  if (!found)
-    MYTHROW(RootException, ("Can't find common feature for joints", jointId0, jointId1));
+  CHECK(found, ("Can't find common feature for joints", jointId0, jointId1));
+}
+
+// IndexGraphStarter::FakeJoint --------------------------------------------------------------------
+IndexGraphStarter::FakeJoint::FakeJoint(IndexGraph const & graph, RoadPoint const & point,
+                                        Joint::Id fakeId)
+  : m_point(point), m_fakeId(fakeId), m_jointId(Joint::kInvalidId)
+{
+}
+
+void IndexGraphStarter::FakeJoint::SetupJointId(IndexGraph const & graph)
+{
+  m_jointId = graph.GetJointId(m_point);
+  if (m_jointId == Joint::kInvalidId)
+    m_jointId = m_fakeId;
 }
 }  // namespace routing
diff --git a/routing/index_graph_starter.hpp b/routing/index_graph_starter.hpp
index c036c0bd14..87a8d0151c 100644
--- a/routing/index_graph_starter.hpp
+++ b/routing/index_graph_starter.hpp
@@ -3,13 +3,15 @@
 #include "routing/index_graph.hpp"
 #include "routing/joint.hpp"
 
+#include "std/utility.hpp"
+
 namespace routing
 {
 // The problem:
 // IndexGraph contains only road points connected in joints.
 // So it is possible IndexGraph doesn't contain start and finish.
 //
-// IndexGraphStarter implants start and finish for AStarAlgorithm.
+// IndexGraphStarter adds fake start and finish joint ids for AStarAlgorithm.
 //
 class IndexGraphStarter final
 {
@@ -18,36 +20,26 @@ public:
   using TVertexType = Joint::Id;
   using TEdgeType = JointEdge;
 
-  IndexGraphStarter(IndexGraph const & graph, RoadPoint startPoint, RoadPoint finishPoint);
-
-  IndexGraph const & GetGraph() const { return m_graph; }
-  Joint::Id GetStartJoint() const { return m_startJoint; }
-  Joint::Id GetFinishJoint() const { return m_finishJoint; }
+  IndexGraphStarter(IndexGraph & graph, RoadPoint const & startPoint,
+                    RoadPoint const & finishPoint);
 
-  m2::PointD const & GetPoint(Joint::Id jointId) const
-  {
-    if (jointId == m_startImplant)
-      return m_graph.GetGeometry().GetPoint(m_startPoint);
+  IndexGraph & GetGraph() const { return m_graph; }
+  Joint::Id GetStartJoint() const { return m_start.m_jointId; }
+  Joint::Id GetFinishJoint() const { return m_finish.m_jointId; }
 
-    if (jointId == m_finishImplant)
-      return m_graph.GetGeometry().GetPoint(m_finishPoint);
-
-    return m_graph.GetPoint(jointId);
-  }
+  m2::PointD const & GetPoint(Joint::Id jointId);
 
-  void GetOutgoingEdgesList(Joint::Id jointId, vector<JointEdge> & edges) const
+  void GetOutgoingEdgesList(Joint::Id jointId, vector<JointEdge> & edges)
   {
-    GetEdgesList(jointId, true, edges);
+    GetEdgesList(jointId, true /* isOutgoing */, edges);
   }
 
-  void GetIngoingEdgesList(Joint::Id jointId, vector<JointEdge> & edges) const
+  void GetIngoingEdgesList(Joint::Id jointId, vector<JointEdge> & edges)
   {
-    GetEdgesList(jointId, false, edges);
+    GetEdgesList(jointId, false /* isOutgoing */, edges);
   }
 
-  void GetEdgesList(Joint::Id jointId, bool isOutgoing, vector<JointEdge> & edges) const;
-
-  double HeuristicCostEstimate(Joint::Id from, Joint::Id to) const
+  double HeuristicCostEstimate(Joint::Id from, Joint::Id to)
   {
     return m_graph.GetEstimator().CalcHeuristic(GetPoint(from), GetPoint(to));
   }
@@ -55,42 +47,52 @@ public:
   // Add intermediate points to route (those don't correspond to any joint).
   //
   // Also convert joint ids to RoadPoints.
-  void RedressRoute(vector<Joint::Id> const & route, vector<RoadPoint> & roadPoints) const;
+  void RedressRoute(vector<Joint::Id> const & route, vector<RoadPoint> & roadPoints);
 
 private:
-  Joint::Id CalcStartJoint() const;
-  Joint::Id CalcFinishJoint() const;
+  struct FakeJoint final
+  {
+    FakeJoint(IndexGraph const & graph, RoadPoint const & point, Joint::Id fakeId);
+
+    void SetupJointId(IndexGraph const & graph);
+    bool BelongsToGraph() const { return m_jointId != m_fakeId; }
 
-  bool StartIsImplant() const { return m_startJoint == m_startImplant; }
-  bool FinishIsImplant() const { return m_finishJoint == m_finishImplant; }
+    RoadPoint const m_point;
+    Joint::Id const m_fakeId;
+    Joint::Id m_jointId;
+  };
 
   template <typename F>
   void ForEachPoint(Joint::Id jointId, F && f) const
   {
-    if (jointId == m_startImplant)
+    if (jointId == m_start.m_fakeId)
     {
-      f(m_startPoint);
+      f(m_start.m_point);
       return;
     }
 
-    if (jointId == m_finishImplant)
+    if (jointId == m_finish.m_fakeId)
     {
-      f(m_finishPoint);
+      f(m_finish.m_point);
       return;
     }
 
-    m_graph.ForEachPoint(jointId, f);
+    m_graph.ForEachPoint(jointId, forward<F>(f));
   }
 
+  void GetEdgesList(Joint::Id jointId, bool isOutgoing, vector<JointEdge> & edges);
+  void GetFakeEdges(FakeJoint const & from, FakeJoint const & to, bool isOutgoing,
+                    vector<JointEdge> & edges);
+  void GetArrivalFakeEdges(Joint::Id jointId, FakeJoint const & fakeJoint, bool isOutgoing,
+                           vector<JointEdge> & edges);
+
+  // Find two road points lying on the same feature.
+  // If there are several pairs of such points, return pair with minimal distance.
   void FindPointsWithCommonFeature(Joint::Id jointId0, Joint::Id jointId1, RoadPoint & result0,
-                                   RoadPoint & result1) const;
-
-  IndexGraph const & m_graph;
-  RoadPoint const m_startPoint;
-  RoadPoint const m_finishPoint;
-  Joint::Id const m_startImplant;
-  Joint::Id const m_finishImplant;
-  Joint::Id const m_startJoint;
-  Joint::Id const m_finishJoint;
+                                   RoadPoint & result1);
+
+  IndexGraph & m_graph;
+  FakeJoint m_start;
+  FakeJoint m_finish;
 };
 }  // namespace routing
diff --git a/routing/joint.hpp b/routing/joint.hpp
index 7bbd678dd6..06bfce9167 100644
--- a/routing/joint.hpp
+++ b/routing/joint.hpp
@@ -17,7 +17,7 @@ public:
   using Id = uint32_t;
   static Id constexpr kInvalidId = numeric_limits<Id>::max();
 
-  void AddPoint(RoadPoint rp) { m_points.emplace_back(rp); }
+  void AddPoint(RoadPoint const & rp) { m_points.emplace_back(rp); }
 
   size_t GetSize() const { return m_points.size(); }
 
diff --git a/routing/joint_index.cpp b/routing/joint_index.cpp
index 2efd1c5bb8..fe85eac81b 100644
--- a/routing/joint_index.cpp
+++ b/routing/joint_index.cpp
@@ -1,5 +1,7 @@
 #include "routing/joint_index.hpp"
 
+#include "routing/routing_exception.hpp"
+
 namespace routing
 {
 Joint::Id JointIndex::InsertJoint(RoadPoint const & rp)
@@ -10,61 +12,50 @@ Joint::Id JointIndex::InsertJoint(RoadPoint const & rp)
   return jointId;
 }
 
-void JointIndex::AppendToJoint(Joint::Id jointId, RoadPoint rp)
+void JointIndex::AppendToJoint(Joint::Id jointId, RoadPoint const & rp)
 {
   m_dynamicJoints[jointId].AddPoint(rp);
 }
 
 void JointIndex::Build(RoadIndex const & roadIndex, uint32_t numJoints)
 {
+  m_dynamicJoints.clear();
+
   // + 1 is protection for 'End' method from out of bounds.
   // Call End(numJoints-1) requires more size, so add one more item.
   // Therefore m_offsets.size() == numJoints + 1,
   // And m_offsets.back() == m_points.size()
   m_offsets.assign(numJoints + 1, 0);
 
-  // Calculate shifted sizes.
+  // Calculate sizes.
   // Example for numJoints = 6:
-  // Original sizes: 2, 5, 3, 4, 2, 3, 0
-  // Shifted sizes: 0, 2, 5, 3, 4, 2, 3
-  roadIndex.ForEachRoad([this](uint32_t /* featureId */, RoadJointIds const & road) {
-    road.ForEachJoint([this](uint32_t /* pointId */, Joint::Id jointId) {
-      Joint::Id nextId = jointId + 1;
-      ASSERT_LESS(jointId, m_offsets.size(), ());
-      ++m_offsets[nextId];
+  // 2, 5, 3, 4, 2, 3, 0
+  roadIndex.ForEachRoad([this, numJoints](uint32_t /* featureId */, RoadJointIds const & road) {
+    road.ForEachJoint([this, numJoints](uint32_t /* pointId */, Joint::Id jointId) {
+      ASSERT_LESS(jointId, numJoints, ());
+      ++m_offsets[jointId];
     });
   });
 
-  // Calculate twice shifted offsets.
-  // Example: 0, 0, 2, 7, 10, 14, 16
-  uint32_t sum = 0;
-  uint32_t prevSum = 0;
+  // Fill offsets with end bounds.
+  // Example: 2, 7, 10, 14, 16, 19, 19
   for (size_t i = 1; i < m_offsets.size(); ++i)
-  {
-    sum += m_offsets[i];
-    m_offsets[i] = prevSum;
-    prevSum = sum;
-  }
+    m_offsets[i] += m_offsets[i - 1];
 
-  m_points.resize(sum);
+  m_points.resize(m_offsets.back());
 
-  // Now fill points, m_offsets[nextId] is current incrementing begin.
-  // Offsets after this operation: 0, 2, 7, 10, 14, 16, 19
+  // Now fill points.
+  // Offsets after this operation are begin bounds:
+  // 0, 2, 7, 10, 14, 16, 19
   roadIndex.ForEachRoad([this](uint32_t featureId, RoadJointIds const & road) {
     road.ForEachJoint([this, featureId](uint32_t pointId, Joint::Id jointId) {
-      Joint::Id nextId = jointId + 1;
-      ASSERT_LESS(nextId, m_offsets.size(), ());
-      uint32_t & offset = m_offsets[nextId];
+      uint32_t & offset = m_offsets[jointId];
+      --offset;
       m_points[offset] = {featureId, pointId};
-      ++offset;
     });
   });
 
-  if (m_offsets[0] != 0)
-    MYTHROW(RootException, ("Wrong offsets calculation: m_offsets[0] =", m_offsets[0]));
-
-  if (m_offsets.back() != m_points.size())
-    MYTHROW(RootException, ("Wrong offsets calculation: m_offsets.back() =", m_offsets.back(),
-                            ", m_points.size()=", m_points.size()));
+  CHECK_EQUAL(m_offsets[0], 0, ());
+  CHECK_EQUAL(m_offsets.back(), m_points.size(), ());
 }
 }  // namespace routing
diff --git a/routing/joint_index.hpp b/routing/joint_index.hpp
index 0bc95a6b3b..668e8e6f1b 100644
--- a/routing/joint_index.hpp
+++ b/routing/joint_index.hpp
@@ -4,6 +4,8 @@
 #include "routing/road_index.hpp"
 #include "routing/road_point.hpp"
 
+#include "base/assert.hpp"
+
 #include "std/vector.hpp"
 
 namespace routing
@@ -16,7 +18,12 @@ class JointIndex final
 {
 public:
   // Read comments in Build method about -1.
-  uint32_t GetNumJoints() const { return m_offsets.size() - 1; }
+  uint32_t GetNumJoints() const
+  {
+    CHECK_GREATER(m_offsets.size(), 0, ());
+    return m_offsets.size() - 1;
+  }
+
   uint32_t GetNumPoints() const { return m_points.size(); }
   RoadPoint GetPoint(Joint::Id jointId) const { return m_points[Begin(jointId)]; }
 
@@ -37,7 +44,7 @@ public:
 
   void Build(RoadIndex const & roadIndex, uint32_t numJoints);
   Joint::Id InsertJoint(RoadPoint const & rp);
-  void AppendToJoint(Joint::Id jointId, RoadPoint rp);
+  void AppendToJoint(Joint::Id jointId, RoadPoint const & rp);
 
 private:
   // Begin index for jointId entries.
diff --git a/routing/road_graph_router.cpp b/routing/road_graph_router.cpp
index a4a8db19d7..e22de1bcd8 100644
--- a/routing/road_graph_router.cpp
+++ b/routing/road_graph_router.cpp
@@ -1,6 +1,5 @@
 #include "routing/road_graph_router.hpp"
 
-#include "routing/astar_router.hpp"
 #include "routing/bicycle_directions.hpp"
 #include "routing/bicycle_model.hpp"
 #include "routing/car_model.hpp"
@@ -9,6 +8,8 @@
 #include "routing/pedestrian_directions.hpp"
 #include "routing/pedestrian_model.hpp"
 #include "routing/route.hpp"
+#include "routing/routing_helpers.hpp"
+#include "routing/single_mwm_router.hpp"
 
 #include "coding/reader_wrapper.hpp"
 
diff --git a/routing/road_index.cpp b/routing/road_index.cpp
index acc1a9d8e8..6f9d925fe7 100644
--- a/routing/road_index.cpp
+++ b/routing/road_index.cpp
@@ -1,8 +1,6 @@
 #include "routing/road_index.hpp"
 
-#include "base/exception.hpp"
-
-#include "std/utility.hpp"
+#include "routing/routing_exception.hpp"
 
 namespace routing
 {
@@ -20,11 +18,11 @@ void RoadIndex::Import(vector<Joint> const & joints)
   }
 }
 
-pair<Joint::Id, uint32_t> RoadIndex::FindNeighbor(RoadPoint rp, bool forward) const
+pair<Joint::Id, uint32_t> RoadIndex::FindNeighbor(RoadPoint const & rp, bool forward) const
 {
   auto const it = m_roads.find(rp.GetFeatureId());
   if (it == m_roads.cend())
-    MYTHROW(RootException, ("RoadIndex doesn't contains feature", rp.GetFeatureId()));
+    MYTHROW(RoutingException, ("RoadIndex doesn't contains feature", rp.GetFeatureId()));
 
   return it->second.FindNeighbor(rp.GetPointId(), forward);
 }
diff --git a/routing/road_index.hpp b/routing/road_index.hpp
index 1ceb9214aa..f35fca1066 100644
--- a/routing/road_index.hpp
+++ b/routing/road_index.hpp
@@ -47,6 +47,7 @@ public:
   pair<Joint::Id, uint32_t> FindNeighbor(uint32_t pointId, bool forward) const
   {
     uint32_t const size = static_cast<uint32_t>(m_jointIds.size());
+    pair<Joint::Id, uint32_t> result = make_pair(Joint::kInvalidId, 0);
 
     if (forward)
     {
@@ -54,7 +55,10 @@ public:
       {
         Joint::Id const jointId = m_jointIds[i];
         if (jointId != Joint::kInvalidId)
-          return make_pair(jointId, i);
+        {
+          result = {jointId, i};
+          return result;
+        }
       }
     }
     else
@@ -63,11 +67,14 @@ public:
       {
         Joint::Id const jointId = m_jointIds[i];
         if (jointId != Joint::kInvalidId)
-          return make_pair(jointId, i);
+        {
+          result = {jointId, i};
+          return result;
+        }
       }
     }
 
-    return make_pair(Joint::kInvalidId, 0);
+    return result;
   }
 
   template <class Sink>
@@ -102,7 +109,7 @@ class RoadIndex final
 public:
   void Import(vector<Joint> const & joints);
 
-  void AddJoint(RoadPoint rp, Joint::Id jointId)
+  void AddJoint(RoadPoint const & rp, Joint::Id jointId)
   {
     m_roads[rp.GetFeatureId()].AddJoint(rp.GetPointId(), jointId);
   }
@@ -110,7 +117,7 @@ public:
   // Find nearest point with normal joint id.
   // If forward == true: neighbor with larger point id (right neighbor)
   // If forward == false: neighbor with smaller point id (left neighbor)
-  pair<Joint::Id, uint32_t> FindNeighbor(RoadPoint rp, bool forward) const;
+  pair<Joint::Id, uint32_t> FindNeighbor(RoadPoint const & rp, bool forward) const;
 
   template <class Sink>
   void Serialize(Sink & sink) const
@@ -138,7 +145,7 @@ public:
 
   uint32_t GetSize() const { return m_roads.size(); }
 
-  Joint::Id GetJointId(RoadPoint rp) const
+  Joint::Id GetJointId(RoadPoint const & rp) const
   {
     auto const it = m_roads.find(rp.GetFeatureId());
     if (it == m_roads.end())
diff --git a/routing/routing.pro b/routing/routing.pro
index b3c500cfc7..cff8f507b6 100644
--- a/routing/routing.pro
+++ b/routing/routing.pro
@@ -13,7 +13,6 @@ INCLUDEPATH += $$ROOT_DIR/3party/jansson/src \
                $$ROOT_DIR/3party/osrm/osrm-backend/third_party
 
 SOURCES += \
-    astar_router.cpp \
     async_router.cpp \
     base/followed_polyline.cpp \
     bicycle_directions.cpp \
@@ -48,9 +47,11 @@ SOURCES += \
     router.cpp \
     router_delegate.cpp \
     routing_algorithm.cpp \
+    routing_helpers.cpp \
     routing_mapping.cpp \
     routing_serialization.cpp \
     routing_session.cpp \
+    single_mwm_router.cpp \
     speed_camera.cpp \
     turns.cpp \
     turns_generator.cpp \
@@ -61,7 +62,6 @@ SOURCES += \
 
 
 HEADERS += \
-    astar_router.hpp \
     async_router.hpp \
     base/astar_algorithm.hpp \
     base/followed_polyline.hpp \
@@ -100,12 +100,14 @@ HEADERS += \
     router.hpp \
     router_delegate.hpp \
     routing_algorithm.hpp \
+    routing_exception.hpp \
     routing_helpers.hpp \
     routing_mapping.hpp \
     routing_result_graph.hpp \
     routing_serialization.hpp \
     routing_session.hpp \
     routing_settings.hpp \
+    single_mwm_router.hpp \
     speed_camera.hpp \
     turn_candidate.hpp \
     turns.hpp \
diff --git a/routing/routing_algorithm.cpp b/routing/routing_algorithm.cpp
index 28619d2602..b93344f78a 100644
--- a/routing/routing_algorithm.cpp
+++ b/routing/routing_algorithm.cpp
@@ -151,8 +151,9 @@ IRoutingAlgorithm::Result AStarRoutingAlgorithm::CalculateRoute(IRoadGraph const
 
   my::Cancellable const & cancellable = delegate;
   progress.Initialize(startPos.GetPoint(), finalPos.GetPoint());
+  RoadGraph roadGraph(graph);
   TAlgorithmImpl::Result const res = TAlgorithmImpl().FindPath(
-      RoadGraph(graph), startPos, finalPos, path, cancellable, onVisitJunctionFn);
+      roadGraph, startPos, finalPos, path, cancellable, onVisitJunctionFn);
   return Convert(res);
 }
 
@@ -177,8 +178,9 @@ IRoutingAlgorithm::Result AStarBidirectionalRoutingAlgorithm::CalculateRoute(
 
   my::Cancellable const & cancellable = delegate;
   progress.Initialize(startPos.GetPoint(), finalPos.GetPoint());
+  RoadGraph roadGraph(graph);
   TAlgorithmImpl::Result const res = TAlgorithmImpl().FindPathBidirectional(
-      RoadGraph(graph), startPos, finalPos, path, cancellable, onVisitJunctionFn);
+      roadGraph, startPos, finalPos, path, cancellable, onVisitJunctionFn);
   return Convert(res);
 }
 
diff --git a/routing/routing_exception.hpp b/routing/routing_exception.hpp
new file mode 100644
index 0000000000..cf80b58eea
--- /dev/null
+++ b/routing/routing_exception.hpp
@@ -0,0 +1,8 @@
+#pragma once
+
+#include "base/exception.hpp"
+
+namespace routing
+{
+DECLARE_EXCEPTION(RoutingException, RootException);
+}  // namespace routing
diff --git a/routing/routing_helpers.cpp b/routing/routing_helpers.cpp
new file mode 100644
index 0000000000..c7450b9852
--- /dev/null
+++ b/routing/routing_helpers.cpp
@@ -0,0 +1,39 @@
+#include "routing/routing_helpers.hpp"
+
+namespace routing
+{
+void ReconstructRoute(IDirectionsEngine * engine, IRoadGraph const & graph,
+                      my::Cancellable const & cancellable, vector<Junction> & path, Route & route)
+{
+  if (path.empty())
+  {
+    LOG(LERROR, ("Can't reconstruct route from an empty list of positions."));
+    return;
+  }
+
+  // By some reason there're two adjacent positions on a road with
+  // the same end-points. This could happen, for example, when
+  // direction on a road was changed.  But it doesn't matter since
+  // this code reconstructs only geometry of a route.
+  path.erase(unique(path.begin(), path.end()), path.end());
+
+  Route::TTimes times;
+  Route::TTurns turnsDir;
+  vector<Junction> junctions;
+  // @TODO(bykoianko) streetNames is not filled in Generate(). It should be done.
+  Route::TStreets streetNames;
+  if (engine)
+    engine->Generate(graph, path, times, turnsDir, junctions, cancellable);
+
+  vector<m2::PointD> routeGeometry;
+  JunctionsToPoints(junctions, routeGeometry);
+  feature::TAltitudes altitudes;
+  JunctionsToAltitudes(junctions, altitudes);
+
+  route.SetGeometry(routeGeometry.begin(), routeGeometry.end());
+  route.SetSectionTimes(move(times));
+  route.SetTurnInstructions(move(turnsDir));
+  route.SetStreetNames(move(streetNames));
+  route.SetAltitudes(move(altitudes));
+}
+}  // namespace rouing
diff --git a/routing/routing_helpers.hpp b/routing/routing_helpers.hpp
index 76440a457e..e05d4f0093 100644
--- a/routing/routing_helpers.hpp
+++ b/routing/routing_helpers.hpp
@@ -2,7 +2,14 @@
 
 #include "routing/bicycle_model.hpp"
 #include "routing/car_model.hpp"
+#include "routing/directions_engine.hpp"
 #include "routing/pedestrian_model.hpp"
+#include "routing/road_graph.hpp"
+#include "routing/route.hpp"
+
+#include "base/cancellable.hpp"
+
+#include "std/vector.hpp"
 
 namespace routing
 {
@@ -14,4 +21,7 @@ bool IsRoad(TTypes const & types)
          PedestrianModel::AllLimitsInstance().HasRoadType(types) ||
          BicycleModel::AllLimitsInstance().HasRoadType(types);
 }
+
+void ReconstructRoute(IDirectionsEngine * engine, IRoadGraph const & graph,
+                      my::Cancellable const & cancellable, vector<Junction> & path, Route & route);
 }  // namespace rouing
diff --git a/routing/routing_integration_tests/routing_test_tools.cpp b/routing/routing_integration_tests/routing_test_tools.cpp
index 3010f4813c..a982361670 100644
--- a/routing/routing_integration_tests/routing_test_tools.cpp
+++ b/routing/routing_integration_tests/routing_test_tools.cpp
@@ -7,12 +7,12 @@
 #include "geometry/distance_on_sphere.hpp"
 #include "geometry/latlon.hpp"
 
-#include "routing/astar_router.hpp"
 #include "routing/online_absent_fetcher.hpp"
 #include "routing/online_cross_fetcher.hpp"
 #include "routing/road_graph_router.hpp"
 #include "routing/route.hpp"
 #include "routing/router_delegate.hpp"
+#include "routing/single_mwm_router.hpp"
 
 #include "indexer/index.hpp"
 
@@ -83,7 +83,7 @@ namespace integration
     };
 
     auto carRouter = make_unique<CarRouter>(
-        index, countryFileGetter, CreateCarAStarBidirectionalRouter(index));
+        index, countryFileGetter, SingleMwmRouter::CreateCarRouter(index));
     return carRouter;
   }
 
diff --git a/routing/routing_tests/astar_algorithm_test.cpp b/routing/routing_tests/astar_algorithm_test.cpp
index 9cccb3b0da..f3887b3cc7 100644
--- a/routing/routing_tests/astar_algorithm_test.cpp
+++ b/routing/routing_tests/astar_algorithm_test.cpp
@@ -57,7 +57,7 @@ private:
   map<unsigned, vector<Edge>> m_adjs;
 };
 
-void TestAStar(UndirectedGraph const & graph, vector<unsigned> const & expectedRoute, double const & expectedDistance)
+void TestAStar(UndirectedGraph & graph, vector<unsigned> const & expectedRoute, double const & expectedDistance)
 {
   using TAlgorithm = AStarAlgorithm<UndirectedGraph>;
 
diff --git a/routing/routing_tests/index_graph_test.cpp b/routing/routing_tests/index_graph_test.cpp
index 4a853baf8a..4dfb73de64 100644
--- a/routing/routing_tests/index_graph_test.cpp
+++ b/routing/routing_tests/index_graph_test.cpp
@@ -25,7 +25,7 @@ public:
   // GeometryLoader overrides:
   void Load(uint32_t featureId, RoadGeometry & road) const override;
 
-  void AddRoad(uint32_t featureId, bool oneWay, RoadGeometry::Points const & points);
+  void AddRoad(uint32_t featureId, bool oneWay, float speed, RoadGeometry::Points const & points);
 
 private:
   unordered_map<uint32_t, RoadGeometry> m_roads;
@@ -40,17 +40,12 @@ void TestGeometryLoader::Load(uint32_t featureId, RoadGeometry & road) const
   road = it->second;
 }
 
-void TestGeometryLoader::AddRoad(uint32_t featureId, bool oneWay,
+void TestGeometryLoader::AddRoad(uint32_t featureId, bool oneWay, float speed,
                                  RoadGeometry::Points const & points)
 {
   auto it = m_roads.find(featureId);
-  if (it != m_roads.end())
-  {
-    ASSERT(false, ("Already contains feature", featureId));
-    return;
-  }
-
-  m_roads[featureId] = RoadGeometry(oneWay, 1.0 /* speed */, points);
+  CHECK(it == m_roads.end(), ("Already contains feature", featureId));
+  m_roads[featureId] = RoadGeometry(oneWay, speed, points);
 }
 
 Joint MakeJoint(vector<RoadPoint> const & points)
@@ -64,10 +59,10 @@ Joint MakeJoint(vector<RoadPoint> const & points)
 
 shared_ptr<EdgeEstimator> CreateEstimator()
 {
-  return CreateCarEdgeEstimator(make_shared<CarModelFactory>()->GetVehicleModel());
+  return EdgeEstimator::CreateForCar(*make_shared<CarModelFactory>()->GetVehicleModel());
 }
 
-void TestRoute(IndexGraph const & graph, RoadPoint const & start, RoadPoint const & finish,
+void TestRoute(IndexGraph & graph, RoadPoint const & start, RoadPoint const & finish,
                size_t expectedLength, vector<RoadPoint> const * expectedRoute = nullptr)
 {
   LOG(LINFO, ("Test route", start.GetFeatureId(), ",", start.GetPointId(), "=>",
@@ -85,15 +80,15 @@ void TestRoute(IndexGraph const & graph, RoadPoint const & start, RoadPoint cons
   starter.RedressRoute(routingResult.path, roadPoints);
   TEST_EQUAL(roadPoints.size(), expectedLength, ());
 
-  if (expectedRoute != nullptr)
+  if (expectedRoute)
     TEST_EQUAL(roadPoints, *expectedRoute, ());
 }
 
-void TestEdges(IndexGraph const & graph, Joint::Id jointId,
-               vector<Joint::Id> const & expectedTargets, bool forward)
+void TestEdges(IndexGraph & graph, Joint::Id jointId, vector<Joint::Id> const & expectedTargets,
+               bool forward)
 {
   vector<JointEdge> edges;
-  graph.GetEdgesList(jointId, forward, edges);
+  graph.GetEdgeList(jointId, forward, edges);
 
   vector<Joint::Id> targets;
   for (JointEdge const & edge : edges)
@@ -101,16 +96,16 @@ void TestEdges(IndexGraph const & graph, Joint::Id jointId,
 
   sort(targets.begin(), targets.end());
 
-  ASSERT_EQUAL(targets, expectedTargets, ());
+  TEST_EQUAL(targets, expectedTargets, ());
 }
 
-void TestOutgoingEdges(IndexGraph const & graph, Joint::Id jointId,
+void TestOutgoingEdges(IndexGraph & graph, Joint::Id jointId,
                        vector<Joint::Id> const & expectedTargets)
 {
   TestEdges(graph, jointId, expectedTargets, true);
 }
 
-void TestIngoingEdges(IndexGraph const & graph, Joint::Id jointId,
+void TestIngoingEdges(IndexGraph & graph, Joint::Id jointId,
                       vector<Joint::Id> const & expectedTargets)
 {
   TestEdges(graph, jointId, expectedTargets, false);
@@ -119,6 +114,8 @@ void TestIngoingEdges(IndexGraph const & graph, Joint::Id jointId,
 uint32_t AbsDelta(uint32_t v0, uint32_t v1) { return v0 > v1 ? v0 - v1 : v1 - v0; }
 }  // namespace
 
+namespace routing_test
+{
 //                   R4 (one way down)
 //
 // R1     J2--------J3         -1
@@ -137,13 +134,15 @@ UNIT_TEST(EdgesTest)
 {
   unique_ptr<TestGeometryLoader> loader = make_unique<TestGeometryLoader>();
   loader->AddRoad(
-      0 /* featureId */, false,
+      0 /* featureId */, false, 1.0 /* speed */,
       RoadGeometry::Points({{0.0, 0.0}, {1.0, 0.0}, {2.0, 0.0}, {3.0, 0.0}, {4.0, 0.0}}));
-  loader->AddRoad(1 /* featureId */, false, RoadGeometry::Points({{1.0, -1.0}, {3.0, -1.0}}));
-  loader->AddRoad(2 /* featureId */, false, RoadGeometry::Points({{1.0, -1.0}, {3.0, -1.0}}));
-  loader->AddRoad(3 /* featureId */, true,
+  loader->AddRoad(1 /* featureId */, false, 1.0 /* speed */,
+                  RoadGeometry::Points({{1.0, -1.0}, {3.0, -1.0}}));
+  loader->AddRoad(2 /* featureId */, false, 1.0 /* speed */,
+                  RoadGeometry::Points({{1.0, -1.0}, {3.0, -1.0}}));
+  loader->AddRoad(3 /* featureId */, true, 1.0 /* speed */,
                   RoadGeometry::Points({{1.0, 1.0}, {1.0, 0.0}, {1.0, -1.0}}));
-  loader->AddRoad(4 /* featureId */, true,
+  loader->AddRoad(4 /* featureId */, true, 1.0 /* speed */,
                   RoadGeometry::Points({{3.0, -1.0}, {3.0, 0.0}, {3.0, 1.0}}));
 
   IndexGraph graph(move(loader), CreateEstimator());
@@ -172,8 +171,6 @@ UNIT_TEST(EdgesTest)
   TestIngoingEdges(graph, 5, {1, 4});
 }
 
-namespace routing_test
-{
 //  Roads     R1:
 //
 //            -2
@@ -186,10 +183,10 @@ UNIT_TEST(FindPathCross)
 {
   unique_ptr<TestGeometryLoader> loader = make_unique<TestGeometryLoader>();
   loader->AddRoad(
-      0 /* featureId */, false,
+      0 /* featureId */, false, 1.0 /* speed */,
       RoadGeometry::Points({{-2.0, 0.0}, {-1.0, 0.0}, {0.0, 0.0}, {1.0, 0.0}, {2.0, 0.0}}));
   loader->AddRoad(
-      1 /* featureId */, false,
+      1 /* featureId */, false, 1.0 /* speed */,
       RoadGeometry::Points({{0.0, -2.0}, {-1.0, 0.0}, {0.0, 0.0}, {0.0, 1.0}, {0.0, 2.0}}));
 
   IndexGraph graph(move(loader), CreateEstimator());
@@ -244,8 +241,8 @@ UNIT_TEST(FindPathManhattan)
       street.emplace_back(static_cast<double>(i), static_cast<double>(j));
       avenue.emplace_back(static_cast<double>(j), static_cast<double>(i));
     }
-    loader->AddRoad(i, false, street);
-    loader->AddRoad(i + kCitySize, false, avenue);
+    loader->AddRoad(i, false, 1.0 /* speed */, street);
+    loader->AddRoad(i + kCitySize, false, 1.0 /* speed */, avenue);
   }
 
   IndexGraph graph(move(loader), CreateEstimator());
@@ -287,15 +284,15 @@ UNIT_TEST(RedressRace)
   unique_ptr<TestGeometryLoader> loader = make_unique<TestGeometryLoader>();
 
   loader->AddRoad(
-      0 /* featureId */, false,
+      0 /* featureId */, false, 1.0 /* speed */,
       RoadGeometry::Points({{0.0, 0.0}, {1.0, -1.0}, {2.0, -1.0}, {3.0, -1.0}, {4.0, 0.0}}));
 
   loader->AddRoad(
-      1 /* featureId */, false,
+      1 /* featureId */, false, 1.0 /* speed */,
       RoadGeometry::Points({{0.0, 0.0}, {1.0, 0.0}, {2.0, 0.0}, {3.0, 0.0}, {4.0, 0.0}}));
 
   loader->AddRoad(
-      2 /* featureId */, false,
+      2 /* featureId */, false, 1.0 /* speed */,
       RoadGeometry::Points({{0.0, 0.0}, {1.0, 1.0}, {2.0, 1.0}, {3.0, 1.0}, {4.0, 0.0}}));
 
   IndexGraph graph(move(loader), CreateEstimator());
@@ -308,4 +305,34 @@ UNIT_TEST(RedressRace)
   vector<RoadPoint> const expectedRoute({{1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}});
   TestRoute(graph, {0, 0}, {0, 4}, 5, &expectedRoute);
 }
+
+// Roads                                       y:
+//
+//  fast road R0            * - * - *         -1
+//                        /           \
+//  slow road R1      J0 *  - - * - -  * J1    0
+//
+//                 x:    0  1   2   3  4
+//
+UNIT_TEST(RoadSpeed)
+{
+  unique_ptr<TestGeometryLoader> loader = make_unique<TestGeometryLoader>();
+
+  loader->AddRoad(
+      0 /* featureId */, false, 10.0 /* speed */,
+      RoadGeometry::Points({{0.0, 0.0}, {1.0, -1.0}, {2.0, -1.0}, {3.0, -1.0}, {4.0, 0.0}}));
+
+  loader->AddRoad(1 /* featureId */, false, 1.0 /* speed */,
+                  RoadGeometry::Points({{0.0, 0.0}, {2.0, 0.0}, {4.0, 0.0}}));
+
+  IndexGraph graph(move(loader), CreateEstimator());
+
+  vector<Joint> joints;
+  joints.emplace_back(MakeJoint({{0, 0}, {1, 0}}));  // J0
+  joints.emplace_back(MakeJoint({{0, 4}, {1, 2}}));  // J1
+  graph.Import(joints);
+
+  vector<RoadPoint> const expectedRoute({{0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}});
+  TestRoute(graph, {0, 0}, {0, 4}, 5, &expectedRoute);
+}
 }  // namespace routing_test
diff --git a/routing/astar_router.cpp b/routing/single_mwm_router.cpp
index 17c1abd2cf..95461b857f 100644
--- a/routing/astar_router.cpp
+++ b/routing/single_mwm_router.cpp
@@ -1,15 +1,15 @@
-#include "routing/astar_router.hpp"
+#include "routing/single_mwm_router.hpp"
 
 #include "routing/base/astar_algorithm.hpp"
 #include "routing/base/astar_progress.hpp"
 #include "routing/bicycle_directions.hpp"
 #include "routing/bicycle_model.hpp"
 #include "routing/car_model.hpp"
-#include "routing/features_road_graph.hpp"
 #include "routing/index_graph.hpp"
 #include "routing/index_graph_starter.hpp"
 #include "routing/pedestrian_model.hpp"
 #include "routing/route.hpp"
+#include "routing/routing_helpers.hpp"
 #include "routing/turns_generator.hpp"
 
 #include "indexer/feature_altitude.hpp"
@@ -29,8 +29,7 @@ size_t constexpr kMaxRoadCandidates = 6;
 float constexpr kProgressInterval = 2;
 uint32_t constexpr kDrawPointsPeriod = 10;
 
-vector<Junction> ConvertToJunctions(IndexGraphStarter const & starter,
-                                    vector<Joint::Id> const & joints)
+vector<Junction> ConvertToJunctions(IndexGraphStarter & starter, vector<Joint::Id> const & joints)
 {
   vector<RoadPoint> roadPoints;
   starter.RedressRoute(joints, roadPoints);
@@ -38,7 +37,7 @@ vector<Junction> ConvertToJunctions(IndexGraphStarter const & starter,
   vector<Junction> junctions;
   junctions.reserve(roadPoints.size());
 
-  Geometry const & geometry = starter.GetGraph().GetGeometry();
+  Geometry & geometry = starter.GetGraph().GetGeometry();
   // TODO: Use real altitudes for pedestrian and bicycle routing.
   for (RoadPoint const & point : roadPoints)
     junctions.emplace_back(geometry.GetPoint(point), feature::kDefaultAltitudeMeters);
@@ -49,14 +48,13 @@ vector<Junction> ConvertToJunctions(IndexGraphStarter const & starter,
 
 namespace routing
 {
-AStarRouter::AStarRouter(string const & name, Index const & index,
-                         shared_ptr<VehicleModelFactory> vehicleModelFactory,
-                         shared_ptr<EdgeEstimator> estimator,
-                         unique_ptr<IDirectionsEngine> directionsEngine)
+SingleMwmRouter::SingleMwmRouter(string const & name, Index const & index,
+                                 shared_ptr<VehicleModelFactory> vehicleModelFactory,
+                                 shared_ptr<EdgeEstimator> estimator,
+                                 unique_ptr<IDirectionsEngine> directionsEngine)
   : m_name(name)
   , m_index(index)
-  , m_roadGraph(
-        make_unique<FeaturesRoadGraph>(index, IRoadGraph::Mode::ObeyOnewayTag, vehicleModelFactory))
+  , m_roadGraph(index, IRoadGraph::Mode::ObeyOnewayTag, vehicleModelFactory)
   , m_vehicleModelFactory(vehicleModelFactory)
   , m_estimator(estimator)
   , m_directionsEngine(move(directionsEngine))
@@ -67,11 +65,11 @@ AStarRouter::AStarRouter(string const & name, Index const & index,
   ASSERT(m_directionsEngine, ());
 }
 
-IRouter::ResultCode AStarRouter::CalculateRoute(MwmSet::MwmId const & mwmId,
-                                                m2::PointD const & startPoint,
-                                                m2::PointD const & startDirection,
-                                                m2::PointD const & finalPoint,
-                                                RouterDelegate const & delegate, Route & route)
+IRouter::ResultCode SingleMwmRouter::CalculateRoute(MwmSet::MwmId const & mwmId,
+                                                    m2::PointD const & startPoint,
+                                                    m2::PointD const & startDirection,
+                                                    m2::PointD const & finalPoint,
+                                                    RouterDelegate const & delegate, Route & route)
 {
   try
   {
@@ -85,12 +83,16 @@ IRouter::ResultCode AStarRouter::CalculateRoute(MwmSet::MwmId const & mwmId,
   }
 }
 
-IRouter::ResultCode AStarRouter::DoCalculateRoute(MwmSet::MwmId const & mwmId,
-                                                  m2::PointD const & startPoint,
-                                                  m2::PointD const & /* startDirection */,
-                                                  m2::PointD const & finalPoint,
-                                                  RouterDelegate const & delegate, Route & route)
+IRouter::ResultCode SingleMwmRouter::DoCalculateRoute(MwmSet::MwmId const & mwmId,
+                                                      m2::PointD const & startPoint,
+                                                      m2::PointD const & /* startDirection */,
+                                                      m2::PointD const & finalPoint,
+                                                      RouterDelegate const & delegate,
+                                                      Route & route)
 {
+  if (!mwmId.IsAlive())
+    return IRouter::RouteFileNotExist;
+
   string const & country = mwmId.GetInfo()->GetCountryName();
 
   Edge startEdge;
@@ -104,8 +106,8 @@ IRouter::ResultCode AStarRouter::DoCalculateRoute(MwmSet::MwmId const & mwmId,
   RoadPoint const start(startEdge.GetFeatureId().m_index, startEdge.GetSegId());
   RoadPoint const finish(finishEdge.GetFeatureId().m_index, finishEdge.GetSegId());
 
-  IndexGraph graph(CreateGeometryLoader(m_index, mwmId,
-                                        m_vehicleModelFactory->GetVehicleModelForCountry(country)),
+  IndexGraph graph(GeometryLoader::Create(
+                       m_index, mwmId, m_vehicleModelFactory->GetVehicleModelForCountry(country)),
                    m_estimator);
 
   if (!LoadIndex(mwmId, country, graph))
@@ -117,15 +119,15 @@ IRouter::ResultCode AStarRouter::DoCalculateRoute(MwmSet::MwmId const & mwmId,
   progress.Initialize(graph.GetGeometry().GetPoint(start), graph.GetGeometry().GetPoint(finish));
 
   uint32_t drawPointsStep = 0;
-  auto onVisitJunction = [&](Joint::Id const & from, Joint::Id const & target) {
-    m2::PointD const & point = starter.GetPoint(from);
-    m2::PointD const & targetPoint = starter.GetPoint(target);
+  auto onVisitJunction = [&](Joint::Id const & from, Joint::Id const & to) {
+    m2::PointD const & pointFrom = starter.GetPoint(from);
+    m2::PointD const & pointTo = starter.GetPoint(to);
     auto const lastValue = progress.GetLastValue();
-    auto const newValue = progress.GetProgressForBidirectedAlgo(point, targetPoint);
+    auto const newValue = progress.GetProgressForBidirectedAlgo(pointFrom, pointTo);
     if (newValue - lastValue > kProgressInterval)
       delegate.OnProgress(newValue);
     if (drawPointsStep % kDrawPointsPeriod == 0)
-      delegate.OnPointCheck(point);
+      delegate.OnPointCheck(pointFrom);
     ++drawPointsStep;
   };
 
@@ -142,16 +144,16 @@ IRouter::ResultCode AStarRouter::DoCalculateRoute(MwmSet::MwmId const & mwmId,
   case AStarAlgorithm<IndexGraphStarter>::Result::Cancelled: return IRouter::Cancelled;
   case AStarAlgorithm<IndexGraphStarter>::Result::OK:
     vector<Junction> path = ConvertToJunctions(starter, routingResult.path);
-    ReconstructRoute(m_directionsEngine.get(), *m_roadGraph, delegate, path, route);
+    ReconstructRoute(m_directionsEngine.get(), m_roadGraph, delegate, path, route);
     return IRouter::NoError;
   }
 }
 
-bool AStarRouter::FindClosestEdge(MwmSet::MwmId const & mwmId, m2::PointD const & point,
-                                  Edge & closestEdge) const
+bool SingleMwmRouter::FindClosestEdge(MwmSet::MwmId const & mwmId, m2::PointD const & point,
+                                      Edge & closestEdge) const
 {
   vector<pair<Edge, Junction>> candidates;
-  m_roadGraph->FindClosestEdges(point, kMaxRoadCandidates, candidates);
+  m_roadGraph.FindClosestEdges(point, kMaxRoadCandidates, candidates);
 
   double minDistance = numeric_limits<double>::max();
   size_t minIndex = candidates.size();
@@ -179,7 +181,8 @@ bool AStarRouter::FindClosestEdge(MwmSet::MwmId const & mwmId, m2::PointD const
   return true;
 }
 
-bool AStarRouter::LoadIndex(MwmSet::MwmId const & mwmId, string const & country, IndexGraph & graph)
+bool SingleMwmRouter::LoadIndex(MwmSet::MwmId const & mwmId, string const & country,
+                                IndexGraph & graph)
 {
   MwmSet::MwmHandle mwmHandle = m_index.GetMwmHandleById(mwmId);
   if (!mwmHandle.IsAlive())
@@ -206,16 +209,17 @@ bool AStarRouter::LoadIndex(MwmSet::MwmId const & mwmId, string const & country,
   }
 }
 
-unique_ptr<AStarRouter> CreateCarAStarBidirectionalRouter(Index & index)
+// static
+unique_ptr<SingleMwmRouter> SingleMwmRouter::CreateCarRouter(Index const & index)
 {
   auto vehicleModelFactory = make_shared<CarModelFactory>();
   // @TODO Bicycle turn generation engine is used now. It's ok for the time being.
   // But later a special car turn generation engine should be implemented.
   auto directionsEngine = make_unique<BicycleDirectionsEngine>(index);
-  auto estimator = CreateCarEdgeEstimator(vehicleModelFactory->GetVehicleModel());
+  auto estimator = EdgeEstimator::CreateForCar(*vehicleModelFactory->GetVehicleModel());
   auto router =
-      make_unique<AStarRouter>("astar-bidirectional-car", index, move(vehicleModelFactory),
-                               estimator, move(directionsEngine));
+      make_unique<SingleMwmRouter>("astar-bidirectional-car", index, move(vehicleModelFactory),
+                                   estimator, move(directionsEngine));
   return router;
 }
 }  // namespace routing
diff --git a/routing/astar_router.hpp b/routing/single_mwm_router.hpp
index e61906bca3..96cd241453 100644
--- a/routing/astar_router.hpp
+++ b/routing/single_mwm_router.hpp
@@ -2,7 +2,7 @@
 
 #include "routing/directions_engine.hpp"
 #include "routing/edge_estimator.hpp"
-#include "routing/road_graph.hpp"
+#include "routing/features_road_graph.hpp"
 #include "routing/router.hpp"
 #include "routing/vehicle_model.hpp"
 
@@ -16,12 +16,13 @@ namespace routing
 {
 class IndexGraph;
 
-class AStarRouter
+class SingleMwmRouter
 {
 public:
-  AStarRouter(string const & name, Index const & index,
-              shared_ptr<VehicleModelFactory> vehicleModelFactory,
-              shared_ptr<EdgeEstimator> estimator, unique_ptr<IDirectionsEngine> directionsEngine);
+  SingleMwmRouter(string const & name, Index const & index,
+                  shared_ptr<VehicleModelFactory> vehicleModelFactory,
+                  shared_ptr<EdgeEstimator> estimator,
+                  unique_ptr<IDirectionsEngine> directionsEngine);
 
   string const & GetName() const { return m_name; }
 
@@ -30,6 +31,8 @@ public:
                                      m2::PointD const & finalPoint, RouterDelegate const & delegate,
                                      Route & route);
 
+  static unique_ptr<SingleMwmRouter> CreateCarRouter(Index const & index);
+
 private:
   IRouter::ResultCode DoCalculateRoute(MwmSet::MwmId const & mwmId, m2::PointD const & startPoint,
                                        m2::PointD const & startDirection,
@@ -39,13 +42,11 @@ private:
                        Edge & closestEdge) const;
   bool LoadIndex(MwmSet::MwmId const & mwmId, string const & country, IndexGraph & graph);
 
-  string m_name;
+  string const m_name;
   Index const & m_index;
-  unique_ptr<IRoadGraph> m_roadGraph;
+  FeaturesRoadGraph m_roadGraph;
   shared_ptr<VehicleModelFactory> m_vehicleModelFactory;
   shared_ptr<EdgeEstimator> m_estimator;
   unique_ptr<IDirectionsEngine> m_directionsEngine;
 };
-
-unique_ptr<AStarRouter> CreateCarAStarBidirectionalRouter(Index & index);
 }  // namespace routing
diff --git a/xcode/routing/routing.xcodeproj/project.pbxproj b/xcode/routing/routing.xcodeproj/project.pbxproj
index a0b85e1146..bfcb836c97 100644
--- a/xcode/routing/routing.xcodeproj/project.pbxproj
+++ b/xcode/routing/routing.xcodeproj/project.pbxproj
@@ -7,8 +7,12 @@
 	objects = {
 
 /* Begin PBXBuildFile section */
-		0C5FEC501DDE19130017688C /* astar_router.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0C5FEC4E1DDE19130017688C /* astar_router.cpp */; };
-		0C5FEC511DDE19130017688C /* astar_router.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 0C5FEC4F1DDE19130017688C /* astar_router.hpp */; };
+		0C0DF9211DE898B70055A22F /* index_graph_starter.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0C0DF91F1DE898B70055A22F /* index_graph_starter.cpp */; };
+		0C0DF9221DE898B70055A22F /* index_graph_starter.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 0C0DF9201DE898B70055A22F /* index_graph_starter.hpp */; };
+		0C0DF9251DE898CF0055A22F /* single_mwm_router.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0C0DF9231DE898CF0055A22F /* single_mwm_router.cpp */; };
+		0C0DF9261DE898CF0055A22F /* single_mwm_router.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 0C0DF9241DE898CF0055A22F /* single_mwm_router.hpp */; };
+		0C0DF9291DE898FF0055A22F /* routing_exception.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 0C0DF9271DE898FF0055A22F /* routing_exception.hpp */; };
+		0C0DF92A1DE898FF0055A22F /* routing_helpers.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0C0DF9281DE898FF0055A22F /* routing_helpers.cpp */; };
 		0C5FEC541DDE191E0017688C /* edge_estimator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0C5FEC521DDE191E0017688C /* edge_estimator.cpp */; };
 		0C5FEC551DDE191E0017688C /* edge_estimator.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 0C5FEC531DDE191E0017688C /* edge_estimator.hpp */; };
 		0C5FEC5E1DDE192A0017688C /* geometry.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0C5FEC561DDE192A0017688C /* geometry.cpp */; };
@@ -235,8 +239,12 @@
 /* End PBXBuildFile section */
 
 /* Begin PBXFileReference section */
-		0C5FEC4E1DDE19130017688C /* astar_router.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = astar_router.cpp; sourceTree = "<group>"; };
-		0C5FEC4F1DDE19130017688C /* astar_router.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = astar_router.hpp; sourceTree = "<group>"; };
+		0C0DF91F1DE898B70055A22F /* index_graph_starter.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = index_graph_starter.cpp; sourceTree = "<group>"; };
+		0C0DF9201DE898B70055A22F /* index_graph_starter.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = index_graph_starter.hpp; sourceTree = "<group>"; };
+		0C0DF9231DE898CF0055A22F /* single_mwm_router.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = single_mwm_router.cpp; sourceTree = "<group>"; };
+		0C0DF9241DE898CF0055A22F /* single_mwm_router.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = single_mwm_router.hpp; sourceTree = "<group>"; };
+		0C0DF9271DE898FF0055A22F /* routing_exception.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = routing_exception.hpp; sourceTree = "<group>"; };
+		0C0DF9281DE898FF0055A22F /* routing_helpers.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = routing_helpers.cpp; sourceTree = "<group>"; };
 		0C5FEC521DDE191E0017688C /* edge_estimator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = edge_estimator.cpp; sourceTree = "<group>"; };
 		0C5FEC531DDE191E0017688C /* edge_estimator.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = edge_estimator.hpp; sourceTree = "<group>"; };
 		0C5FEC561DDE192A0017688C /* geometry.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = geometry.cpp; sourceTree = "<group>"; };
@@ -655,8 +663,6 @@
 		675343FA1A3F640D00A0A8C3 /* routing */ = {
 			isa = PBXGroup;
 			children = (
-				0C5FEC4E1DDE19130017688C /* astar_router.cpp */,
-				0C5FEC4F1DDE19130017688C /* astar_router.hpp */,
 				0C5FEC521DDE191E0017688C /* edge_estimator.cpp */,
 				0C5FEC531DDE191E0017688C /* edge_estimator.hpp */,
 				56EA2FD41D8FD8590083F01A /* routing_helpers.hpp */,
@@ -667,6 +673,8 @@
 				0C5FEC591DDE192A0017688C /* index_graph.hpp */,
 				0C5FEC5A1DDE192A0017688C /* joint_index.cpp */,
 				0C5FEC5B1DDE192A0017688C /* joint_index.hpp */,
+				0C0DF91F1DE898B70055A22F /* index_graph_starter.cpp */,
+				0C0DF9201DE898B70055A22F /* index_graph_starter.hpp */,
 				0C5FEC5C1DDE192A0017688C /* joint.cpp */,
 				0C5FEC5D1DDE192A0017688C /* joint.hpp */,
 				56099E2D1CC8FBDA00A7772A /* osrm_path_segment_factory.hpp */,
@@ -685,6 +693,10 @@
 				0C5FEC661DDE193F0017688C /* road_index.cpp */,
 				0C5FEC671DDE193F0017688C /* road_index.hpp */,
 				0C5FEC681DDE193F0017688C /* road_point.hpp */,
+				0C0DF9271DE898FF0055A22F /* routing_exception.hpp */,
+				0C0DF9281DE898FF0055A22F /* routing_helpers.cpp */,
+				0C0DF9231DE898CF0055A22F /* single_mwm_router.cpp */,
+				0C0DF9241DE898CF0055A22F /* single_mwm_router.hpp */,
 				6741AA9A1BF35331002C974C /* turns_notification_manager.cpp */,
 				6741AA9B1BF35331002C974C /* turns_notification_manager.hpp */,
 				A1876BC41BB19C4300C9C743 /* speed_camera.cpp */,
@@ -789,9 +801,11 @@
 				6753441A1A3F644F00A0A8C3 /* osrm2feature_map.hpp in Headers */,
 				6741AA9D1BF35331002C974C /* turns_notification_manager.hpp in Headers */,
 				674F9BD71B0A580E00704FFA /* turns_generator.hpp in Headers */,
+				0C0DF9261DE898CF0055A22F /* single_mwm_router.hpp in Headers */,
 				A120B3461B4A7BE5002F3808 /* cross_mwm_road_graph.hpp in Headers */,
 				6753441C1A3F644F00A0A8C3 /* route.hpp in Headers */,
 				A1616E2C1B6B60AB003F078E /* router_delegate.hpp in Headers */,
+				0C0DF9291DE898FF0055A22F /* routing_exception.hpp in Headers */,
 				A17B42991BCFBD0E00A1EAE4 /* osrm_helpers.hpp in Headers */,
 				67C7D42E1B4EB48F00FE41AA /* turns_sound_settings.hpp in Headers */,
 				56099E341CC9247E00A7772A /* bicycle_directions.hpp in Headers */,
@@ -800,7 +814,6 @@
 				670EE55F1B6001E7001E8064 /* routing_settings.hpp in Headers */,
 				671F58BE1B874EC80032311E /* followed_polyline.hpp in Headers */,
 				67C7D42C1B4EB48F00FE41AA /* pedestrian_model.hpp in Headers */,
-				0C5FEC511DDE19130017688C /* astar_router.hpp in Headers */,
 				0C5FEC6A1DDE193F0017688C /* road_index.hpp in Headers */,
 				674F9BCD1B0A580E00704FFA /* features_road_graph.hpp in Headers */,
 				670EE5741B664796001E8064 /* pedestrian_directions.hpp in Headers */,
@@ -809,6 +822,7 @@
 				670EE5721B664796001E8064 /* directions_engine.hpp in Headers */,
 				A1876BC71BB19C4300C9C743 /* speed_camera.hpp in Headers */,
 				56EA2FD51D8FD8590083F01A /* routing_helpers.hpp in Headers */,
+				0C0DF9221DE898B70055A22F /* index_graph_starter.hpp in Headers */,
 				56099E2F1CC8FBDA00A7772A /* osrm_path_segment_factory.hpp in Headers */,
 				67C7D42A1B4EB48F00FE41AA /* car_model.hpp in Headers */,
 				670D049F1B0B4A970013A7AC /* nearest_edge_finder.hpp in Headers */,
@@ -1047,6 +1061,8 @@
 				A1616E2B1B6B60AB003F078E /* router_delegate.cpp in Sources */,
 				6741AA9C1BF35331002C974C /* turns_notification_manager.cpp in Sources */,
 				67C7D42B1B4EB48F00FE41AA /* pedestrian_model.cpp in Sources */,
+				0C0DF9251DE898CF0055A22F /* single_mwm_router.cpp in Sources */,
+				0C0DF9211DE898B70055A22F /* index_graph_starter.cpp in Sources */,
 				A120B3471B4A7BE5002F3808 /* cross_mwm_router.cpp in Sources */,
 				670EE5731B664796001E8064 /* pedestrian_directions.cpp in Sources */,
 				6753441B1A3F644F00A0A8C3 /* route.cpp in Sources */,
@@ -1056,7 +1072,6 @@
 				674F9BD61B0A580E00704FFA /* turns_generator.cpp in Sources */,
 				A17B42981BCFBD0E00A1EAE4 /* osrm_helpers.cpp in Sources */,
 				563B91C51CC4F1DC00222BC1 /* bicycle_model.cpp in Sources */,
-				0C5FEC501DDE19130017688C /* astar_router.cpp in Sources */,
 				674F9BD21B0A580E00704FFA /* road_graph_router.cpp in Sources */,
 				A1876BC61BB19C4300C9C743 /* speed_camera.cpp in Sources */,
 				0C5FEC691DDE193F0017688C /* road_index.cpp in Sources */,
@@ -1067,6 +1082,7 @@
 				56099E331CC9247E00A7772A /* bicycle_directions.cpp in Sources */,
 				674A28B11B1605D2001A525C /* osrm_engine.cpp in Sources */,
 				674F9BD41B0A580E00704FFA /* road_graph.cpp in Sources */,
+				0C0DF92A1DE898FF0055A22F /* routing_helpers.cpp in Sources */,
 				67AB92E61B7B3E6E00AB5194 /* turns_tts_text.cpp in Sources */,
 				0C5FEC601DDE192A0017688C /* index_graph.cpp in Sources */,
 				0C5FEC6D1DDE19A40017688C /* index_graph_test.cpp in Sources */,