diff options
author | Mikhail Gorbushin <m.gorbushin@corp.mail.ru> | 2019-03-22 19:32:24 +0300 |
---|---|---|
committer | Vladimir Byko-Ianko <bykoianko@gmail.com> | 2019-04-01 17:12:51 +0300 |
commit | 9cc034a71703395ea9ee5f9da344bb9e20fcd260 (patch) | |
tree | 7bacd908672870c6441a81464722ceecc7f8a3ce /routing | |
parent | a896d48a199a2bbfe3b1d8856b24918755ba1a97 (diff) |
[routing] create interface for graph to AStar
Diffstat (limited to 'routing')
-rw-r--r-- | routing/base/astar_algorithm.hpp | 84 | ||||
-rw-r--r-- | routing/base/astar_graph.hpp | 23 | ||||
-rw-r--r-- | routing/index_graph_starter.hpp | 18 | ||||
-rw-r--r-- | routing/index_graph_starter_joints.hpp | 26 | ||||
-rw-r--r-- | routing/index_router.cpp | 41 | ||||
-rw-r--r-- | routing/index_router.hpp | 24 | ||||
-rw-r--r-- | routing/routing_tests/applying_traffic_test.cpp | 18 | ||||
-rw-r--r-- | routing/routing_tests/astar_algorithm_test.cpp | 53 | ||||
-rw-r--r-- | routing/routing_tests/cumulative_restriction_test.cpp | 24 | ||||
-rw-r--r-- | routing/routing_tests/index_graph_test.cpp | 23 | ||||
-rw-r--r-- | routing/routing_tests/index_graph_tools.cpp | 30 | ||||
-rw-r--r-- | routing/routing_tests/index_graph_tools.hpp | 42 | ||||
-rw-r--r-- | routing/routing_tests/restriction_test.cpp | 62 | ||||
-rw-r--r-- | routing/routing_tests/routing_algorithm.cpp | 29 |
14 files changed, 298 insertions, 199 deletions
diff --git a/routing/base/astar_algorithm.hpp b/routing/base/astar_algorithm.hpp index d09e3707c5..c1b8105a19 100644 --- a/routing/base/astar_algorithm.hpp +++ b/routing/base/astar_algorithm.hpp @@ -1,5 +1,6 @@ #pragma once +#include "routing/base/astar_graph.hpp" #include "routing/base/astar_weight.hpp" #include "routing/base/routing_result.hpp" @@ -15,13 +16,12 @@ namespace routing { -template <typename Graph> +template <typename Vertex, typename Edge, typename Weight> class AStarAlgorithm { public: - using Vertex = typename Graph::Vertex; - using Edge = typename Graph::Edge; - using Weight = typename Graph::Weight; + + using Graph = AStarGraph<Vertex, Edge, Weight>; enum class Result { @@ -178,8 +178,8 @@ public: // Adjust route to the previous one. // Expects |params.m_checkLengthCallback| to check wave propagation limit. template <typename P> - typename AStarAlgorithm<Graph>::Result AdjustRoute(P & params, - RoutingResult<Vertex, Weight> & result) const; + typename AStarAlgorithm<Vertex, Edge, Weight>::Result AdjustRoute(P & params, + RoutingResult<Vertex, Weight> & result) const; private: // Periodicity of switching a wave of bidirectional algorithm. @@ -295,20 +295,20 @@ private: std::vector<Vertex> & path); }; -template <typename Graph> -constexpr typename Graph::Weight AStarAlgorithm<Graph>::kEpsilon; -template <typename Graph> -constexpr typename Graph::Weight AStarAlgorithm<Graph>::kInfiniteDistance; -template <typename Graph> -constexpr typename Graph::Weight AStarAlgorithm<Graph>::kZeroDistance; +template <typename Vertex, typename Edge, typename Weight> +constexpr Weight AStarAlgorithm<Vertex, Edge, Weight>::kEpsilon; +template <typename Vertex, typename Edge, typename Weight> +constexpr Weight AStarAlgorithm<Vertex, Edge, Weight>::kInfiniteDistance; +template <typename Vertex, typename Edge, typename Weight> +constexpr Weight AStarAlgorithm<Vertex, Edge, Weight>::kZeroDistance; -template <typename Graph> +template <typename Vertex, typename Edge, typename Weight> template <typename VisitVertex, typename AdjustEdgeWeight, typename FilterStates> -void AStarAlgorithm<Graph>::PropagateWave(Graph & graph, Vertex const & startVertex, +void AStarAlgorithm<Vertex, Edge, Weight>::PropagateWave(Graph & graph, Vertex const & startVertex, VisitVertex && visitVertex, AdjustEdgeWeight && adjustEdgeWeight, FilterStates && filterStates, - AStarAlgorithm<Graph>::Context & context) const + AStarAlgorithm<Vertex, Edge, Weight>::Context & context) const { context.Clear(); @@ -355,11 +355,11 @@ void AStarAlgorithm<Graph>::PropagateWave(Graph & graph, Vertex const & startVer } } -template <typename Graph> +template <typename Vertex, typename Edge, typename Weight> template <typename VisitVertex> -void AStarAlgorithm<Graph>::PropagateWave(Graph & graph, Vertex const & startVertex, +void AStarAlgorithm<Vertex, Edge, Weight>::PropagateWave(Graph & graph, Vertex const & startVertex, VisitVertex && visitVertex, - AStarAlgorithm<Graph>::Context & context) const + AStarAlgorithm<Vertex, Edge, Weight>::Context & context) const { auto const adjustEdgeWeight = [](Vertex const & /* vertex */, Edge const & edge) { return edge.GetWeight(); @@ -379,10 +379,10 @@ void AStarAlgorithm<Graph>::PropagateWave(Graph & graph, Vertex const & startVer // http://research.microsoft.com/pubs/154937/soda05.pdf // http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf -template <typename Graph> +template <typename Vertex, typename Edge, typename Weight> template <typename P> -typename AStarAlgorithm<Graph>::Result AStarAlgorithm<Graph>::FindPath( - P & params, RoutingResult<Vertex, Weight> & result) const +typename AStarAlgorithm<Vertex, Edge, Weight>::Result +AStarAlgorithm<Vertex, Edge, Weight>::FindPath(P & params, RoutingResult<Vertex, Weight> & result) const { result.Clear(); @@ -455,10 +455,11 @@ typename AStarAlgorithm<Graph>::Result AStarAlgorithm<Graph>::FindPath( return resultCode; } -template <typename Graph> +template <typename Vertex, typename Edge, typename Weight> template <typename P> -typename AStarAlgorithm<Graph>::Result AStarAlgorithm<Graph>::FindPathBidirectional( - P & params, RoutingResult<Vertex, Weight> & result) const +typename AStarAlgorithm<Vertex, Edge, Weight>::Result +AStarAlgorithm<Vertex, Edge, Weight>::FindPathBidirectional(P & params, + RoutingResult<Vertex, Weight> & result) const { auto & graph = params.m_graph; auto const & finalVertex = params.m_finalVertex; @@ -599,10 +600,11 @@ typename AStarAlgorithm<Graph>::Result AStarAlgorithm<Graph>::FindPathBidirectio return Result::NoPath; } -template <typename Graph> +template <typename Vertex, typename Edge, typename Weight> template <typename P> -typename AStarAlgorithm<Graph>::Result AStarAlgorithm<Graph>::AdjustRoute( - P & params, RoutingResult<Vertex, Weight> & result) const +typename AStarAlgorithm<Vertex, Edge, Weight>::Result + AStarAlgorithm<Vertex, Edge, Weight>::AdjustRoute(P & params, RoutingResult<Vertex, + Weight> & result) const { CHECK(params.m_prevRoute, ()); auto & graph = params.m_graph; @@ -697,10 +699,10 @@ typename AStarAlgorithm<Graph>::Result AStarAlgorithm<Graph>::AdjustRoute( } // static -template <typename Graph> -void AStarAlgorithm<Graph>::ReconstructPath(Vertex const & v, - std::map<Vertex, Vertex> const & parent, - std::vector<Vertex> & path) +template <typename Vertex, typename Edge, typename Weight> +void AStarAlgorithm<Vertex, Edge, Weight>::ReconstructPath(Vertex const & v, + std::map<Vertex, Vertex> const & parent, + std::vector<Vertex> & path) { path.clear(); Vertex cur = v; @@ -716,11 +718,12 @@ void AStarAlgorithm<Graph>::ReconstructPath(Vertex const & v, } // static -template <typename Graph> -void AStarAlgorithm<Graph>::ReconstructPathBidirectional(Vertex const & v, Vertex const & w, - std::map<Vertex, Vertex> const & parentV, - std::map<Vertex, Vertex> const & parentW, - std::vector<Vertex> & path) +template <typename Vertex, typename Edge, typename Weight> +void +AStarAlgorithm<Vertex, Edge, Weight>::ReconstructPathBidirectional(Vertex const & v, Vertex const & w, + std::map<Vertex, Vertex> const & parentV, + std::map<Vertex, Vertex> const & parentW, + std::vector<Vertex> & path) { std::vector<Vertex> pathV; ReconstructPath(v, parentV, pathV); @@ -732,10 +735,11 @@ void AStarAlgorithm<Graph>::ReconstructPathBidirectional(Vertex const & v, Verte path.insert(path.end(), pathW.rbegin(), pathW.rend()); } -template <typename Graph> -void AStarAlgorithm<Graph>::Context::ReconstructPath(Vertex const & v, - std::vector<Vertex> & path) const +template <typename Vertex, typename Edge, typename Weight> +void +AStarAlgorithm<Vertex, Edge, Weight>::Context::ReconstructPath(Vertex const & v, + std::vector<Vertex> & path) const { - AStarAlgorithm<Graph>::ReconstructPath(v, m_parents, path); + AStarAlgorithm<Vertex, Edge, Weight>::ReconstructPath(v, m_parents, path); } } // namespace routing diff --git a/routing/base/astar_graph.hpp b/routing/base/astar_graph.hpp new file mode 100644 index 0000000000..1647c96db7 --- /dev/null +++ b/routing/base/astar_graph.hpp @@ -0,0 +1,23 @@ +#pragma once + +#include <vector> + +namespace routing +{ +template <typename VertexType, typename EdgeType, typename WeightType> +class AStarGraph +{ +public: + + using Vertex = VertexType; + using Edge = EdgeType; + using Weight = WeightType; + + virtual Weight HeuristicCostEstimate(Vertex const & from, Vertex const & to) = 0; + + virtual void GetOutgoingEdgesList(Vertex const & v, std::vector<Edge> & edges) = 0; + virtual void GetIngoingEdgesList(Vertex const & v, std::vector<Edge> & edges) = 0; + + virtual ~AStarGraph() = default; +}; +} // namespace routing diff --git a/routing/index_graph_starter.hpp b/routing/index_graph_starter.hpp index 29398cf1d4..b21bc86007 100644 --- a/routing/index_graph_starter.hpp +++ b/routing/index_graph_starter.hpp @@ -1,6 +1,8 @@ #pragma once +#include "routing/base/astar_graph.hpp" #include "routing/base/routing_result.hpp" + #include "routing/fake_ending.hpp" #include "routing/fake_feature_ids.hpp" #include "routing/fake_graph.hpp" @@ -26,13 +28,13 @@ namespace routing class FakeEdgesContainer; // IndexGraphStarter adds fake start and finish vertices for AStarAlgorithm. -class IndexGraphStarter final +class IndexGraphStarter : public AStarGraph<IndexGraph::Vertex, IndexGraph::Edge, IndexGraph::Weight> { public: // AStarAlgorithm types aliases: - using Vertex = IndexGraph::Vertex; - using Edge = IndexGraph::Edge; - using Weight = IndexGraph::Weight; + using Vertex = AStarGraph::Vertex; + using Edge = AStarGraph::Edge; + using Weight = AStarGraph::Weight; friend class FakeEdgesContainer; @@ -91,17 +93,17 @@ public: void GetEdgesList(Segment const & segment, bool isOutgoing, std::vector<SegmentEdge> & edges) const; - void GetOutgoingEdgesList(Vertex const & segment, std::vector<Edge> & edges) const + void GetOutgoingEdgesList(Vertex const & segment, std::vector<Edge> & edges) override { GetEdgesList(segment, true /* isOutgoing */, edges); } - void GetIngoingEdgesList(Vertex const & segment, std::vector<Edge> & edges) const + void GetIngoingEdgesList(Vertex const & segment, std::vector<Edge> & edges) override { GetEdgesList(segment, false /* isOutgoing */, edges); } - RouteWeight HeuristicCostEstimate(Vertex const & from, Vertex const & to) const + RouteWeight HeuristicCostEstimate(Vertex const & from, Vertex const & to) override { return m_graph.HeuristicCostEstimate(GetPoint(from, true /* front */), GetPoint(to, true /* front */)); @@ -120,6 +122,8 @@ public: RouteWeight CalcSegmentWeight(Segment const & segment) const; double CalcSegmentETA(Segment const & segment) const; + ~IndexGraphStarter() override = default; + private: // Start or finish ending information. struct Ending diff --git a/routing/index_graph_starter_joints.hpp b/routing/index_graph_starter_joints.hpp index 2533cb7e54..e27bde15ec 100644 --- a/routing/index_graph_starter_joints.hpp +++ b/routing/index_graph_starter_joints.hpp @@ -1,5 +1,7 @@ #pragma once +#include "routing/base/astar_graph.hpp" + #include "routing/fake_feature_ids.hpp" #include "routing/index_graph_starter.hpp" #include "routing/joint_segment.hpp" @@ -21,12 +23,12 @@ namespace routing { template <typename Graph> -class IndexGraphStarterJoints +class IndexGraphStarterJoints : public AStarGraph<JointSegment, JointEdge, RouteWeight> { public: - using Vertex = JointSegment; - using Edge = JointEdge; - using Weight = RouteWeight; + using Vertex = AStarGraph::Vertex; + using Edge = AStarGraph::Edge; + using Weight = AStarGraph::Weight; explicit IndexGraphStarterJoints(Graph & graph) : m_graph(graph) {} IndexGraphStarterJoints(Graph & graph, @@ -40,24 +42,24 @@ public: JointSegment const & GetStartJoint() const { return m_startJoint; } JointSegment const & GetFinishJoint() const { return m_endJoint; } - - // These functions are A* interface. - RouteWeight HeuristicCostEstimate(JointSegment const & from, JointSegment const & to); - m2::PointD const & GetPoint(JointSegment const & jointSegment, bool start); - void GetOutgoingEdgesList(JointSegment const & vertex, std::vector<JointEdge> & edges) + // AStarGraph overridings + // @{ + RouteWeight HeuristicCostEstimate(JointSegment const & from, JointSegment const & to) override; + + void GetOutgoingEdgesList(JointSegment const & vertex, std::vector<JointEdge> & edges) override { GetEdgeList(vertex, true /* isOutgoing */, edges); } - void GetIngoingEdgesList(JointSegment const & vertex, std::vector<JointEdge> & edges) + void GetIngoingEdgesList(JointSegment const & vertex, std::vector<JointEdge> & edges) override { GetEdgeList(vertex, false /* isOutgoing */, edges); } + // @} WorldGraphMode GetMode() const { return m_graph.GetMode(); } - // End of A* interface. /// \brief Reconstructs JointSegment by segment after building the route. std::vector<Segment> ReconstructJoint(JointSegment const & joint); @@ -73,6 +75,8 @@ public: Segment const & GetSegmentOfFakeJoint(JointSegment const & joint, bool start); + ~IndexGraphStarterJoints() override = default; + private: static auto constexpr kInvalidId = JointSegment::kInvalidId; static auto constexpr kInvisibleEndId = kInvalidId - 1; diff --git a/routing/index_router.cpp b/routing/index_router.cpp index 18abca1d89..a3d1f90feb 100644 --- a/routing/index_router.cpp +++ b/routing/index_router.cpp @@ -572,7 +572,8 @@ RouterResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoints, auto checkLength = [&starter](RouteWeight const & weight) { return starter.CheckLength(weight); }; base::HighResTimer timer; - if (starter.GetGraph().GetMode() == WorldGraphMode::Joints) + WorldGraphMode mode = starter.GetGraph().GetMode(); + if (mode == WorldGraph::Mode::Joints) { IndexGraphStarterJoints<IndexGraphStarter> jointStarter(starter, starter.GetStartSegment(), starter.GetFinishSegment()); RoutingResult<JointSegment, RouteWeight> routingResult; @@ -594,12 +595,16 @@ RouterResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoints, delegate.OnPointCheck(pointFrom); }; - AStarAlgorithm<IndexGraphStarterJoints<IndexGraphStarter>>::Params params( + using Vertex = IndexGraphStarterJoints::Vertex; + using Edge = IndexGraphStarterJoints::Edge; + using Weight = IndexGraphStarterJoints::Weight; + + AStarAlgorithm<Vertex, Edge, Weight>::Params params( jointStarter, jointStarter.GetStartJoint(), jointStarter.GetFinishJoint(), nullptr /* prevRoute */, delegate, onVisitJunctionJoints, checkLength); set<NumMwmId> const mwmIds = starter.GetMwms(); - RouterResultCode const result = FindPath<IndexGraphStarterJoints<IndexGraphStarter>>(params, mwmIds, routingResult); + RouterResultCode const result = FindPath<Vertex, Edge, Weight>(params, mwmIds, routingResult, mode); if (result != RouterResultCode::NoError) return result; @@ -607,13 +612,17 @@ RouterResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoints, } else { + using Vertex = IndexGraphStarter::Vertex; + using Edge = IndexGraphStarter::Edge; + using Weight = IndexGraphStarter::Weight; + RoutingResult<Segment, RouteWeight> routingResult; - AStarAlgorithm<IndexGraphStarter>::Params params( + AStarAlgorithm<Vertex, Edge, Weight>::Params params( starter, starter.GetStartSegment(), starter.GetFinishSegment(), nullptr /* prevRoute */, delegate, onVisitJunction, checkLength); set<NumMwmId> const mwmIds = starter.GetMwms(); - RouterResultCode const result = FindPath<IndexGraphStarter>(params, mwmIds, routingResult); + RouterResultCode const result = FindPath<Vertex, Edge, Weight>(params, mwmIds, routingResult, mode); if (result != RouterResultCode::NoError) return result; @@ -695,13 +704,17 @@ RouterResultCode IndexRouter::AdjustRoute(Checkpoints const & checkpoints, return weight <= RouteWeight(kAdjustLimitSec) && starter.CheckLength(weight); }; - AStarAlgorithm<IndexGraphStarter> algorithm; - AStarAlgorithm<IndexGraphStarter>::Params params(starter, starter.GetStartSegment(), - {} /* finalVertex */, &prevEdges, delegate, - onVisitJunction, checkLength); + using Vertex = IndexGraphStarter::Vertex; + using Edge = IndexGraphStarter::Edge; + using Weight = IndexGraphStarter::Weight; + + AStarAlgorithm<Vertex, Edge, Weight> algorithm; + AStarAlgorithm<Vertex, Edge, Weight>::Params params(starter, starter.GetStartSegment(), + {} /* finalVertex */, &prevEdges, delegate, + onVisitJunction, checkLength); RoutingResult<Segment, RouteWeight> result; auto const resultCode = - ConvertResult<IndexGraphStarter>(algorithm.AdjustRoute(params, result)); + ConvertResult<Vertex, Edge, Weight>(algorithm.AdjustRoute(params, result)); if (resultCode != RouterResultCode::NoError) return resultCode; @@ -903,12 +916,16 @@ RouterResultCode IndexRouter::ProcessLeapsJoints(vector<Segment> const & input, fillMwmIds(start, end, mwmIds); - AStarAlgorithm<IndexGraphStarterJoints<IndexGraphStarter>>::Params params( + using Vertex = IndexGraphStarterJoints::Vertex; + using Edge = IndexGraphStarterJoints::Edge; + using Weight = IndexGraphStarterJoints::Weight; + + AStarAlgorithm<Vertex, Edge, Weight>::Params params( jointStarter, jointStarter.GetStartJoint(), jointStarter.GetFinishJoint(), nullptr /* prevRoute */, delegate, {} /* onVisitedVertexCallback */, checkLength); - return FindPath<IndexGraphStarterJoints<IndexGraphStarter>>(params, mwmIds, routingResult); + return FindPath<Vertex, Edge, Weight>(params, mwmIds, routingResult, mode); }; deque<vector<Segment>> paths; diff --git a/routing/index_router.hpp b/routing/index_router.hpp index 82aebd1466..e2b5e44aa8 100644 --- a/routing/index_router.hpp +++ b/routing/index_router.hpp @@ -128,31 +128,31 @@ private: void FillSpeedCamProhibitedMwms(std::vector<Segment> const & segments, std::vector<platform::CountryFile> & speedCamProhibitedMwms) const; - template <typename Graph> - RouterResultCode ConvertResult(typename AStarAlgorithm<Graph>::Result result) const + template <typename Vertex, typename Edge, typename Weight> + RouterResultCode ConvertResult(typename AStarAlgorithm<Vertex, Edge, Weight>::Result result) const { switch (result) { - case AStarAlgorithm<Graph>::Result::NoPath: return RouterResultCode::RouteNotFound; - case AStarAlgorithm<Graph>::Result::Cancelled: return RouterResultCode::Cancelled; - case AStarAlgorithm<Graph>::Result::OK: return RouterResultCode::NoError; + case AStarAlgorithm<Vertex, Edge, Weight>::Result::NoPath: return RouterResultCode::RouteNotFound; + case AStarAlgorithm<Vertex, Edge, Weight>::Result::Cancelled: return RouterResultCode::Cancelled; + case AStarAlgorithm<Vertex, Edge, Weight>::Result::OK: return RouterResultCode::NoError; } UNREACHABLE(); } - template <typename Graph> + template <typename Vertex, typename Edge, typename Weight> RouterResultCode FindPath( - typename AStarAlgorithm<Graph>::Params & params, std::set<NumMwmId> const & mwmIds, - RoutingResult<typename Graph::Vertex, typename Graph::Weight> & routingResult) const + typename AStarAlgorithm<Vertex, Edge, Weight>::Params & params, std::set<NumMwmId> const & mwmIds, + RoutingResult<Vertex, Weight> & routingResult, WorldGraph::Mode mode) const { - AStarAlgorithm<Graph> algorithm; - if (params.m_graph.GetMode() == WorldGraphMode::LeapsOnly) + AStarAlgorithm<Vertex, Edge, Weight> algorithm; + if (mode == WorldGraphMode::LeapsOnly) { return ConvertTransitResult(mwmIds, - ConvertResult<Graph>(algorithm.FindPath(params, routingResult))); + ConvertResult<Vertex, Edge, Weight>(algorithm.FindPath(params, routingResult))); } return ConvertTransitResult( - mwmIds, ConvertResult<Graph>(algorithm.FindPathBidirectional(params, routingResult))); + mwmIds, ConvertResult<Vertex, Edge, Weight>(algorithm.FindPathBidirectional(params, routingResult))); } VehicleType m_vehicleType; diff --git a/routing/routing_tests/applying_traffic_test.cpp b/routing/routing_tests/applying_traffic_test.cpp index 275eb0e623..31a7fe738b 100644 --- a/routing/routing_tests/applying_traffic_test.cpp +++ b/routing/routing_tests/applying_traffic_test.cpp @@ -119,6 +119,8 @@ private: shared_ptr<TrafficStash> m_trafficStash; }; +using Algorithm = AStarAlgorithm<Segment, SegmentEdge, RouteWeight>; + // Route through XX graph without any traffic info. UNIT_CLASS_TEST(ApplyingTrafficTest, XXGraph_EmptyTrafficColoring) { @@ -130,7 +132,7 @@ UNIT_CLASS_TEST(ApplyingTrafficTest, XXGraph_EmptyTrafficColoring) auto const finish = MakeFakeEnding(6, 0, m2::PointD(3.0, 3.0), *graph); auto starter = MakeStarter(start, finish, *graph); vector<m2::PointD> const expectedGeom = {{2 /* x */, -1 /* y */}, {2, 0}, {1, 1}, {2, 2}, {3, 3}}; - TestRouteGeometry(*starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); + TestRouteGeometry(*starter, Algorithm::Result::OK, expectedGeom); } // Route through XX graph with SpeedGroup::G0 on F3. @@ -147,7 +149,7 @@ UNIT_CLASS_TEST(ApplyingTrafficTest, XXGraph_G0onF3) auto const finish = MakeFakeEnding(6, 0, m2::PointD(3.0, 3.0), *graph); auto starter = MakeStarter(start, finish, *graph); vector<m2::PointD> const expectedGeom = {{2 /* x */, -1 /* y */}, {2, 0}, {3, 0}, {3, 1}, {2, 2}, {3, 3}}; - TestRouteGeometry(*starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); + TestRouteGeometry(*starter, Algorithm::Result::OK, expectedGeom); } // Route through XX graph with SpeedGroup::TempBlock on F3. @@ -164,7 +166,7 @@ UNIT_CLASS_TEST(ApplyingTrafficTest, XXGraph_TempBlockonF3) auto const finish = MakeFakeEnding(6, 0, m2::PointD(3.0, 3.0), *graph); auto starter = MakeStarter(start, finish, *graph); vector<m2::PointD> const expectedGeom = {{2 /* x */, -1 /* y */}, {2, 0}, {3, 0}, {3, 1}, {2, 2}, {3, 3}}; - TestRouteGeometry(*starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); + TestRouteGeometry(*starter, Algorithm::Result::OK, expectedGeom); } // Route through XX graph with SpeedGroup::G0 in reverse direction on F3. @@ -181,7 +183,7 @@ UNIT_CLASS_TEST(ApplyingTrafficTest, XXGraph_G0onF3ReverseDir) auto const finish = MakeFakeEnding(6, 0, m2::PointD(3.0, 3.0), *graph); auto starter = MakeStarter(start, finish, *graph); vector<m2::PointD> const expectedGeom = {{2 /* x */, -1 /* y */}, {2, 0}, {1, 1}, {2, 2}, {3, 3}}; - TestRouteGeometry(*starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); + TestRouteGeometry(*starter, Algorithm::Result::OK, expectedGeom); } // Route through XX graph SpeedGroup::G1 on F3 and F6, SpeedGroup::G4 on F8 and F4. @@ -204,7 +206,7 @@ UNIT_CLASS_TEST(ApplyingTrafficTest, XXGraph_G0onF3andF6andG4onF8andF4) auto const finish = MakeFakeEnding(6, 0, m2::PointD(3.0, 3.0), *graph); auto starter = MakeStarter(start, finish, *graph); vector<m2::PointD> const expectedGeom = {{2 /* x */, -1 /* y */}, {2, 0}, {3, 0}, {3, 1}, {2, 2}, {3, 3}}; - TestRouteGeometry(*starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); + TestRouteGeometry(*starter, Algorithm::Result::OK, expectedGeom); } // Route through XX graph with changing traffic. @@ -220,7 +222,7 @@ UNIT_CLASS_TEST(ApplyingTrafficTest, XXGraph_ChangingTraffic) auto starter = MakeStarter(start, finish, *graph); vector<m2::PointD> const noTrafficGeom = {{2 /* x */, -1 /* y */}, {2, 0}, {1, 1}, {2, 2}, {3, 3}}; { - TestRouteGeometry(*starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, noTrafficGeom); + TestRouteGeometry(*starter, Algorithm::Result::OK, noTrafficGeom); } // Heavy traffic (SpeedGroup::G0) on F3. @@ -230,7 +232,7 @@ UNIT_CLASS_TEST(ApplyingTrafficTest, XXGraph_ChangingTraffic) SetTrafficColoring(make_shared<TrafficInfo::Coloring const>(coloringHeavyF3)); { vector<m2::PointD> const heavyF3Geom = {{2 /* x */, -1 /* y */}, {2, 0}, {3, 0}, {3, 1}, {2, 2}, {3, 3}}; - TestRouteGeometry(*starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, heavyF3Geom); + TestRouteGeometry(*starter, Algorithm::Result::OK, heavyF3Geom); } // Overloading traffic jam on F3. Middle traffic (SpeedGroup::G3) on F1, F3, F4, F7 and F8. @@ -247,7 +249,7 @@ UNIT_CLASS_TEST(ApplyingTrafficTest, XXGraph_ChangingTraffic) SpeedGroup::G3}}; SetTrafficColoring(make_shared<TrafficInfo::Coloring const>(coloringMiddleF1F3F4F7F8)); { - TestRouteGeometry(*starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, noTrafficGeom); + TestRouteGeometry(*starter, Algorithm::Result::OK, noTrafficGeom); } } } // namespace diff --git a/routing/routing_tests/astar_algorithm_test.cpp b/routing/routing_tests/astar_algorithm_test.cpp index 83b2d709f3..60a4488346 100644 --- a/routing/routing_tests/astar_algorithm_test.cpp +++ b/routing/routing_tests/astar_algorithm_test.cpp @@ -1,6 +1,7 @@ #include "testing/testing.hpp" #include "routing/base/astar_algorithm.hpp" +#include "routing/base/astar_graph.hpp" #include "routing/base/routing_result.hpp" #include "std/map.hpp" @@ -23,12 +24,12 @@ struct Edge double w; }; -class UndirectedGraph +class UndirectedGraph : public AStarGraph<unsigned, routing_test::Edge, double> { public: - using Vertex = unsigned; - using Edge = routing_test::Edge; - using Weight = double; + using Vertex = AStarGraph::Vertex; + using Edge = AStarGraph::Edge; + using Weight = AStarGraph::Weight; void AddEdge(unsigned u, unsigned v, unsigned w) { @@ -44,38 +45,38 @@ public: adj = it->second; } - void GetIngoingEdgesList(unsigned v, vector<Edge> & adj) const + void GetIngoingEdgesList(Vertex const & v, vector<Edge> & adj) override { GetAdjacencyList(v, adj); } - void GetOutgoingEdgesList(unsigned v, vector<Edge> & adj) const + void GetOutgoingEdgesList(Vertex const & v, vector<Edge> & adj) override { GetAdjacencyList(v, adj); } - double HeuristicCostEstimate(unsigned v, unsigned w) const { return 0; } + double HeuristicCostEstimate(Vertex const & v, Vertex const & w) override { return 0; } private: map<unsigned, vector<Edge>> m_adjs; }; -using TAlgorithm = AStarAlgorithm<UndirectedGraph>; +using Algorithm = AStarAlgorithm<unsigned, routing_test::Edge, double>; void TestAStar(UndirectedGraph & graph, vector<unsigned> const & expectedRoute, double const & expectedDistance) { - TAlgorithm algo; + Algorithm algo; - TAlgorithm::ParamsForTests params(graph, 0u /* startVertex */, 4u /* finishVertex */, + Algorithm::ParamsForTests params(graph, 0u /* startVertex */, 4u /* finishVertex */, nullptr /* prevRoute */, {} /* checkLengthCallback */); RoutingResult<unsigned /* Vertex */, double /* Weight */> actualRoute; - TEST_EQUAL(TAlgorithm::Result::OK, algo.FindPath(params, actualRoute), ()); + TEST_EQUAL(Algorithm::Result::OK, algo.FindPath(params, actualRoute), ()); TEST_EQUAL(expectedRoute, actualRoute.m_path, ()); TEST_ALMOST_EQUAL_ULPS(expectedDistance, actualRoute.m_distance, ()); actualRoute.m_path.clear(); - TEST_EQUAL(TAlgorithm::Result::OK, algo.FindPathBidirectional(params, actualRoute), ()); + TEST_EQUAL(Algorithm::Result::OK, algo.FindPathBidirectional(params, actualRoute), ()); TEST_EQUAL(expectedRoute, actualRoute.m_path, ()); TEST_ALMOST_EQUAL_ULPS(expectedDistance, actualRoute.m_distance, ()); } @@ -107,19 +108,19 @@ UNIT_TEST(AStarAlgorithm_CheckLength) graph.AddEdge(2, 4, 10); graph.AddEdge(3, 4, 3); - TAlgorithm algo; - TAlgorithm::ParamsForTests params(graph, 0u /* startVertex */, 4u /* finishVertex */, + Algorithm algo; + Algorithm::ParamsForTests params(graph, 0u /* startVertex */, 4u /* finishVertex */, nullptr /* prevRoute */, [](double weight) { return weight < 23; }); RoutingResult<unsigned /* Vertex */, double /* Weight */> routingResult; - TAlgorithm::Result result = algo.FindPath(params, routingResult); + Algorithm::Result result = algo.FindPath(params, routingResult); // Best route weight is 23 so we expect to find no route with restriction |weight < 23|. - TEST_EQUAL(result, TAlgorithm::Result::NoPath, ()); + TEST_EQUAL(result, Algorithm::Result::NoPath, ()); routingResult = {}; result = algo.FindPathBidirectional(params, routingResult); // Best route weight is 23 so we expect to find no route with restriction |weight < 23|. - TEST_EQUAL(result, TAlgorithm::Result::NoPath, ()); + TEST_EQUAL(result, Algorithm::Result::NoPath, ()); } UNIT_TEST(AdjustRoute) @@ -136,14 +137,14 @@ UNIT_TEST(AdjustRoute) // Each edge contains {vertexId, weight}. vector<Edge> const prevRoute = {{0, 0}, {1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 1}}; - TAlgorithm algo; - TAlgorithm::ParamsForTests params(graph, 6 /* startVertex */, {} /* finishVertex */, &prevRoute, + Algorithm algo; + Algorithm::ParamsForTests params(graph, 6 /* startVertex */, {} /* finishVertex */, &prevRoute, [](double weight) { return weight <= 1.0; }); RoutingResult<unsigned /* Vertex */, double /* Weight */> result; auto const code = algo.AdjustRoute(params, result); vector<unsigned> const expectedRoute = {6, 2, 3, 4, 5}; - TEST_EQUAL(code, TAlgorithm::Result::OK, ()); + TEST_EQUAL(code, Algorithm::Result::OK, ()); TEST_EQUAL(result.m_path, expectedRoute, ()); TEST_EQUAL(result.m_distance, 4.0, ()); } @@ -158,13 +159,13 @@ UNIT_TEST(AdjustRouteNoPath) // Each edge contains {vertexId, weight}. vector<Edge> const prevRoute = {{0, 0}, {1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 1}}; - TAlgorithm algo; - TAlgorithm::ParamsForTests params(graph, 6 /* startVertex */, {} /* finishVertex */, &prevRoute, + Algorithm algo; + Algorithm::ParamsForTests params(graph, 6 /* startVertex */, {} /* finishVertex */, &prevRoute, [](double weight) { return weight <= 1.0; }); RoutingResult<unsigned /* Vertex */, double /* Weight */> result; auto const code = algo.AdjustRoute(params, result); - TEST_EQUAL(code, TAlgorithm::Result::NoPath, ()); + TEST_EQUAL(code, Algorithm::Result::NoPath, ()); TEST(result.m_path.empty(), ()); } @@ -180,13 +181,13 @@ UNIT_TEST(AdjustRouteOutOfLimit) // Each edge contains {vertexId, weight}. vector<Edge> const prevRoute = {{0, 0}, {1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 1}}; - TAlgorithm algo; - TAlgorithm::ParamsForTests params(graph, 6 /* startVertex */, {} /* finishVertex */, &prevRoute, + Algorithm algo; + Algorithm::ParamsForTests params(graph, 6 /* startVertex */, {} /* finishVertex */, &prevRoute, [](double weight) { return weight <= 1.0; }); RoutingResult<unsigned /* Vertex */, double /* Weight */> result; auto const code = algo.AdjustRoute(params, result); - TEST_EQUAL(code, TAlgorithm::Result::NoPath, ()); + TEST_EQUAL(code, Algorithm::Result::NoPath, ()); TEST(result.m_path.empty(), ()); } } // namespace routing_test diff --git a/routing/routing_tests/cumulative_restriction_test.cpp b/routing/routing_tests/cumulative_restriction_test.cpp index b76ef755a2..4706b37a9b 100644 --- a/routing/routing_tests/cumulative_restriction_test.cpp +++ b/routing/routing_tests/cumulative_restriction_test.cpp @@ -70,6 +70,8 @@ unique_ptr<SingleVehicleWorldGraph> BuildXYGraph() return BuildWorldGraph(move(loader), estimator, joints); } +using Algorithm = AStarAlgorithm<Segment, SegmentEdge, RouteWeight>; + // Route through XY graph without any restrictions. UNIT_TEST(XYGraph) { @@ -79,7 +81,7 @@ UNIT_TEST(XYGraph) auto const finish = MakeFakeEnding(5, 0, m2::PointD(2, 3), *graph); auto starter = MakeStarter(start, finish, *graph); vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, {1, 1}, {2, 2}, {2, 3}}; - TestRouteGeometry(*starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); + TestRouteGeometry(*starter, Algorithm::Result::OK, expectedGeom); } // Route through XY graph with one restriciton (type only) from F1 to F3. @@ -94,7 +96,7 @@ UNIT_CLASS_TEST(RestrictionTest, XYGraph_RestrictionF1F3Only) vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, {1, 1}, {2, 2}, {2, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(1 /* featureId */, 0 /* segmentIdx */, m2::PointD(2, 0), *m_graph), MakeFakeEnding(5, 0, m2::PointD(2, 3), *m_graph), move(restrictionsNo), *this); } @@ -111,7 +113,7 @@ UNIT_CLASS_TEST(RestrictionTest, XYGraph_RestrictionF3F5Only) vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, {1, 1}, {2, 2}, {2, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(1 /* featureId */, 0 /* segmentIdx */, m2::PointD(2, 0), *m_graph), MakeFakeEnding(5, 0, m2::PointD(2, 3), *m_graph), move(restrictionsNo), *this); } @@ -130,7 +132,7 @@ UNIT_CLASS_TEST(RestrictionTest, XYGraph_PermutationsF3F5OnlyF1F3Only) vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, {1, 1}, {2, 2}, {2, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(1 /* featureId */, 0 /* segmentIdx */, m2::PointD(2, 0), *m_graph), MakeFakeEnding(5, 0, m2::PointD(2, 3), *m_graph), move(restrictionsNo), *this); } @@ -153,7 +155,7 @@ UNIT_CLASS_TEST(RestrictionTest, XYGraph_PermutationsF3F5OnlyAndF0F2No) vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, {1, 1}, {2, 2}, {2, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(1 /* featureId */, 0 /* segmentIdx */, m2::PointD(2, 0), *m_graph), MakeFakeEnding(5, 0, m2::PointD(2, 3), *m_graph), move(restrictionsNo), *this); } @@ -174,7 +176,7 @@ UNIT_CLASS_TEST(RestrictionTest, XYGraph_RestrictionF3F5OnlyAndF1F3No) restrictionsNo); TestRestrictions( - {} /* expectedGeom */, AStarAlgorithm<IndexGraphStarter>::Result::NoPath, + {} /* expectedGeom */, Algorithm::Result::NoPath, MakeFakeEnding(1 /* featureId */, 0 /* segmentIdx */, m2::PointD(2, 0), *m_graph), MakeFakeEnding(5, 0, m2::PointD(2, 3), *m_graph), move(restrictionsNo), *this); } @@ -296,7 +298,7 @@ UNIT_CLASS_TEST(RestrictionTest, XXGraph) RestrictionVec restrictions = {}; vector<m2::PointD> const expectedGeom = {{2 /* x */, -1 /* y */}, {2, 0}, {1, 1}, {2, 2}, {3, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(9 /* featureId */, 0 /* segmentIdx */, m2::PointD(2, -1), *m_graph), MakeFakeEnding(6, 0, m2::PointD(3, 3), *m_graph), move(restrictions), *this); } @@ -316,7 +318,7 @@ UNIT_CLASS_TEST(RestrictionTest, XXGraph_PermutationsF1F3OnlyAndF3F6Only) vector<m2::PointD> const expectedGeom = {{2 /* x */, -1 /* y */}, {2, 0}, {1, 1}, {2, 2}, {3, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(9 /* featureId */, 0 /* segmentIdx */, m2::PointD(2, -1), *m_graph), MakeFakeEnding(6, 0, m2::PointD(3, 3), *m_graph), move(restrictionsNo), *this); } @@ -331,7 +333,7 @@ UNIT_CLASS_TEST(RestrictionTest, XXGraph_RestrictionF1F3No) {2 /* x */, -1 /* y */}, {2, 0}, {3, 0}, {3, 1}, {2, 2}, {3, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(9 /* featureId */, 0 /* segmentIdx */, m2::PointD(2, -1), *m_graph), MakeFakeEnding(6, 0, m2::PointD(3, 3), *m_graph), move(restrictions), *this); } @@ -356,7 +358,7 @@ UNIT_CLASS_TEST(RestrictionTest, XXGraph_PermutationsF1F3NoF7F8OnlyF8F4OnlyF4F6O vector<m2::PointD> const expectedGeom = { {2 /* x */, -1 /* y */}, {2, 0}, {3, 0}, {3, 1}, {2, 2}, {3, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(9 /* featureId */, 0 /* segmentIdx */, m2::PointD(2, -1), *m_graph), MakeFakeEnding(6, 0, m2::PointD(3, 3), *m_graph), move(restrictionsNo), *this); } @@ -369,7 +371,7 @@ UNIT_CLASS_TEST(RestrictionTest, XXGraph_CheckOnlyRestriction) m2::PointD const finish(3.0, 0.2); auto const test = [&](vector<m2::PointD> const & expectedGeom, RestrictionVec && restrictionsNo) { TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(0 /* featureId */, 0 /* segmentIdx */, start, *m_graph), MakeFakeEnding(3 /* featureId */, 0 /* segmentIdx */, finish, *m_graph), move(restrictionsNo), *this); diff --git a/routing/routing_tests/index_graph_test.cpp b/routing/routing_tests/index_graph_test.cpp index b39e17ed5b..b2c6b102a4 100644 --- a/routing/routing_tests/index_graph_test.cpp +++ b/routing/routing_tests/index_graph_test.cpp @@ -1,6 +1,8 @@ #include "testing/testing.hpp" #include "routing/base/astar_algorithm.hpp" +#include "routing/base/astar_graph.hpp" + #include "routing/edge_estimator.hpp" #include "routing/fake_ending.hpp" #include "routing/index_graph.hpp" @@ -23,12 +25,11 @@ #include "base/assert.hpp" #include "base/math.hpp" -#include "std/algorithm.hpp" -#include "std/cstdint.hpp" -#include "std/shared_ptr.hpp" -#include "std/unique_ptr.hpp" -#include "std/unordered_map.hpp" -#include "std/vector.hpp" +#include <algorithm> +#include <cstdint> +#include <memory> +#include <unordered_map> +#include <vector> using namespace std; @@ -39,6 +40,8 @@ using namespace routing_test; using TestEdge = TestIndexGraphTopology::Edge; +using AlgorithmForIndexGraphStarter = AStarAlgorithm<Segment, SegmentEdge, RouteWeight>; + double constexpr kUnknownWeight = -1.0; void TestRoute(FakeEnding const & start, FakeEnding const & finish, size_t expectedLength, @@ -48,7 +51,7 @@ void TestRoute(FakeEnding const & start, FakeEnding const & finish, size_t expec vector<Segment> route; double timeSec; auto const resultCode = CalculateRoute(*starter, route, timeSec); - TEST_EQUAL(resultCode, AStarAlgorithm<IndexGraphStarter>::Result::OK, ()); + TEST_EQUAL(resultCode, AlgorithmForIndexGraphStarter::Result::OK, ()); TEST_GREATER(route.size(), 2, ()); @@ -465,7 +468,7 @@ UNIT_TEST(OneSegmentWayBackward) vector<Segment> route; double timeSec; auto const resultCode = CalculateRoute(*starter, route, timeSec); - TEST_EQUAL(resultCode, AStarAlgorithm<IndexGraphStarter>::Result::NoPath, ()); + TEST_EQUAL(resultCode, AlgorithmForIndexGraphStarter::Result::NoPath, ()); } // Roads y: @@ -505,7 +508,7 @@ UNIT_TEST(FakeSegmentCoordinates) m2::PointD(3, 0), *worldGraph); auto starter = MakeStarter(start, finish, *worldGraph); - TestRouteGeometry(*starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); + TestRouteGeometry(*starter, AlgorithmForIndexGraphStarter::Result::OK, expectedGeom); } } } @@ -848,6 +851,6 @@ UNIT_TEST(FinishNearZeroEdge) vector<m2::PointD> const expectedGeom = { {1.0 /* x */, 0.0 /* y */}, {2.0, 0.0}, {4.0, 0.0}, {5.0, 0.0}}; - TestRouteGeometry(*starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); + TestRouteGeometry(*starter, AlgorithmForIndexGraphStarter::Result::OK, expectedGeom); } } // namespace routing_test diff --git a/routing/routing_tests/index_graph_tools.cpp b/routing/routing_tests/index_graph_tools.cpp index 07dd2d54c0..52f7799216 100644 --- a/routing/routing_tests/index_graph_tools.cpp +++ b/routing/routing_tests/index_graph_tools.cpp @@ -157,6 +157,8 @@ void TestIndexGraphTopology::SetVertexAccess(Vertex v, RoadAccess::Type type) CHECK(found, ("Cannot set access for vertex that is not in the graph", v)); } +using AlgorithmForWorldGraph = AStarAlgorithm<Segment, SegmentEdge, RouteWeight>; + bool TestIndexGraphTopology::FindPath(Vertex start, Vertex finish, double & pathWeight, vector<Edge> & pathEdges) const { @@ -192,9 +194,11 @@ bool TestIndexGraphTopology::FindPath(Vertex start, Vertex finish, double & path auto const worldGraph = builder.PrepareIndexGraph(); CHECK(worldGraph != nullptr, ()); - AStarAlgorithm<WorldGraph> algorithm; + AlgorithmForWorldGraph algorithm; + + WorldGraphForAStar graphForAStar(*worldGraph); - AStarAlgorithm<WorldGraph>::ParamsForTests params(*worldGraph, startSegment, finishSegment, + AlgorithmForWorldGraph::ParamsForTests params(graphForAStar, startSegment, finishSegment, nullptr /* prevRoute */, {} /* checkLengthCallback */); RoutingResult<Segment, RouteWeight> routingResult; @@ -210,9 +214,9 @@ bool TestIndexGraphTopology::FindPath(Vertex start, Vertex finish, double & path ("Distances differ:", routingResult.m_distance, unidirectionalRoutingResult.m_distance)); } - if (resultCode == AStarAlgorithm<WorldGraph>::Result::NoPath) + if (resultCode == AlgorithmForWorldGraph::Result::NoPath) return false; - CHECK_EQUAL(resultCode, AStarAlgorithm<WorldGraph>::Result::OK, ()); + CHECK_EQUAL(resultCode, AlgorithmForWorldGraph::Result::OK, ()); CHECK_GREATER_OR_EQUAL(routingResult.m_path.size(), 2, ()); CHECK_EQUAL(routingResult.m_path.front(), startSegment, ()); @@ -379,14 +383,14 @@ shared_ptr<EdgeEstimator> CreateEstimatorForCar(shared_ptr<TrafficStash> traffic return EdgeEstimator::Create(VehicleType::Car, *carModel, trafficStash); } -AStarAlgorithm<IndexGraphStarter>::Result CalculateRoute(IndexGraphStarter & starter, - vector<Segment> & roadPoints, - double & timeSec) +AStarAlgorithm<Segment, SegmentEdge, RouteWeight>::Result +CalculateRoute(IndexGraphStarter & starter, vector<Segment> & roadPoints, + double & timeSec) { - AStarAlgorithm<IndexGraphStarter> algorithm; + AStarAlgorithm<Segment, SegmentEdge, RouteWeight> algorithm; RoutingResult<Segment, RouteWeight> routingResult; - AStarAlgorithm<IndexGraphStarter>::ParamsForTests params( + AStarAlgorithm<Segment, SegmentEdge, RouteWeight>::ParamsForTests params( starter, starter.GetStartSegment(), starter.GetFinishSegment(), nullptr /* prevRoute */, [&](RouteWeight const & weight) { return starter.CheckLength(weight); }); @@ -398,7 +402,7 @@ AStarAlgorithm<IndexGraphStarter>::Result CalculateRoute(IndexGraphStarter & sta } void TestRouteGeometry(IndexGraphStarter & starter, - AStarAlgorithm<IndexGraphStarter>::Result expectedRouteResult, + AStarAlgorithm<Segment, SegmentEdge, RouteWeight>::Result expectedRouteResult, vector<m2::PointD> const & expectedRouteGeom) { vector<Segment> routeSegs; @@ -407,7 +411,7 @@ void TestRouteGeometry(IndexGraphStarter & starter, TEST_EQUAL(resultCode, expectedRouteResult, ()); - if (AStarAlgorithm<IndexGraphStarter>::Result::NoPath == expectedRouteResult && + if (AStarAlgorithm<Segment, SegmentEdge, RouteWeight>::Result::NoPath == expectedRouteResult && expectedRouteGeom.empty()) { // The route goes through a restriction. So there's no choice for building route @@ -415,7 +419,7 @@ void TestRouteGeometry(IndexGraphStarter & starter, return; } - if (resultCode != AStarAlgorithm<IndexGraphStarter>::Result::OK) + if (resultCode != AStarAlgorithm<Segment, SegmentEdge, RouteWeight>::Result::OK) return; CHECK(!routeSegs.empty(), ()); @@ -445,7 +449,7 @@ void TestRouteGeometry(IndexGraphStarter & starter, } void TestRestrictions(vector<m2::PointD> const & expectedRouteGeom, - AStarAlgorithm<IndexGraphStarter>::Result expectedRouteResult, + AStarAlgorithm<Segment, SegmentEdge, RouteWeight>::Result expectedRouteResult, FakeEnding const & start, FakeEnding const & finish, RestrictionVec && restrictions, RestrictionTest & restrictionTest) { diff --git a/routing/routing_tests/index_graph_tools.hpp b/routing/routing_tests/index_graph_tools.hpp index adf2e91081..ec82c117ff 100644 --- a/routing/routing_tests/index_graph_tools.hpp +++ b/routing/routing_tests/index_graph_tools.hpp @@ -41,9 +41,39 @@ namespace routing_test using namespace routing; // The value doesn't matter, it doesn't associated with any real mwm id. -// It just a noticeable value to detect the source of such id while debuggging unit tests. +// It just a noticeable value to detect the source of such id while debuging unit tests. NumMwmId constexpr kTestNumMwmId = 777; +class WorldGraphForAStar : public AStarGraph<Segment, SegmentEdge, RouteWeight> +{ +public: + using Vertex = AStarGraph::Vertex; + using Edge = AStarGraph::Edge; + using Weight = AStarGraph::Weight; + + explicit WorldGraphForAStar(WorldGraph & graph) : m_graph(graph) {} + + Weight HeuristicCostEstimate(Vertex const & from, Vertex const & to) override + { + return m_graph.HeuristicCostEstimate(from, to); + } + + void GetOutgoingEdgesList(Vertex const & v, std::vector<Edge> & edges) override + { + m_graph.GetOutgoingEdgesList(v, edges); + } + + void GetIngoingEdgesList(Vertex const & v, std::vector<Edge> & edges) override + { + m_graph.GetIngoingEdgesList(v, edges); + } + + ~WorldGraphForAStar() override = default; + +private: + WorldGraph & m_graph; +}; + struct RestrictionTest { RestrictionTest() { classificator::Load(); } @@ -231,19 +261,19 @@ shared_ptr<routing::EdgeEstimator> CreateEstimatorForCar( traffic::TrafficCache const & trafficCache); shared_ptr<routing::EdgeEstimator> CreateEstimatorForCar(shared_ptr<TrafficStash> trafficStash); -routing::AStarAlgorithm<routing::IndexGraphStarter>::Result CalculateRoute( - routing::IndexGraphStarter & starter, vector<routing::Segment> & roadPoints, double & timeSec); +AStarAlgorithm<Segment, SegmentEdge, RouteWeight>::Result CalculateRoute( + IndexGraphStarter & starter, vector<Segment> & roadPoints, double & timeSec); void TestRouteGeometry( - routing::IndexGraphStarter & starter, - routing::AStarAlgorithm<routing::IndexGraphStarter>::Result expectedRouteResult, + IndexGraphStarter & starter, + AStarAlgorithm<Segment, SegmentEdge, RouteWeight>::Result expectedRouteResult, vector<m2::PointD> const & expectedRouteGeom); /// \brief Applies |restrictions| to graph in |restrictionTest| and /// tests the resulting route. /// \note restrictionTest should have a valid |restrictionTest.m_graph|. void TestRestrictions(vector<m2::PointD> const & expectedRouteGeom, - AStarAlgorithm<IndexGraphStarter>::Result expectedRouteResult, + AStarAlgorithm<Segment, SegmentEdge, RouteWeight>::Result expectedRouteResult, FakeEnding const & start, FakeEnding const & finish, RestrictionVec && restrictions, RestrictionTest & restrictionTest); diff --git a/routing/routing_tests/restriction_test.cpp b/routing/routing_tests/restriction_test.cpp index 09c250270e..598a1234e2 100644 --- a/routing/routing_tests/restriction_test.cpp +++ b/routing/routing_tests/restriction_test.cpp @@ -62,6 +62,8 @@ unique_ptr<SingleVehicleWorldGraph> BuildCrossGraph() return BuildWorldGraph(move(loader), estimator, joints); } +using Algorithm = AStarAlgorithm<Segment, SegmentEdge, RouteWeight>; + UNIT_CLASS_TEST(RestrictionTest, CrossGraph_NoUTurn) { Init(BuildCrossGraph()); @@ -70,7 +72,7 @@ UNIT_CLASS_TEST(RestrictionTest, CrossGraph_NoUTurn) vector<m2::PointD> const expectedGeom = { {-1.0 /* x */, 0.0 /* y */}, {0.0, 0.0}, {1.0, 0.0}, {1.0, 1.0}, {1.0, 2.0}}; - TestRouteGeometry(*m_starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); + TestRouteGeometry(*m_starter, Algorithm::Result::OK, expectedGeom); } UNIT_CLASS_TEST(RestrictionTest, CrossGraph_UTurn) @@ -85,7 +87,7 @@ UNIT_CLASS_TEST(RestrictionTest, CrossGraph_UTurn) {1.0, 0.0}, {1.0, 1.0}, {1.0, 2.0}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(0 /* featureId */, 0 /* segmentIdx */, m2::PointD(-1, 0), *m_graph), MakeFakeEnding(7, 0, m2::PointD(1, 2), *m_graph), move(restrictions), *this); } @@ -145,7 +147,7 @@ UNIT_CLASS_TEST(RestrictionTest, TriangularGraph) vector<m2::PointD> const expectedGeom = {{3 /* x */, 0 /* y */}, {2, 0}, {1, 1}, {0, 2}, {0, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(5 /* featureId */, 0 /* segmentIdx */, m2::PointD(3, 0), *m_graph), MakeFakeEnding(4, 0, m2::PointD(0, 3), *m_graph), {}, *this); } @@ -160,7 +162,7 @@ UNIT_CLASS_TEST(RestrictionTest, TriangularGraph_RestrictionNoF2F1) {3 /* x */, 0 /* y */}, {2, 0}, {1, 0}, {0, 0}, {0, 2}, {0, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(5 /* featureId */, 0 /* senmentIdx */, m2::PointD(3, 0), *m_graph), MakeFakeEnding(4, 0, m2::PointD(0, 3), *m_graph), move(restrictions), *this); } @@ -174,7 +176,7 @@ UNIT_CLASS_TEST(RestrictionTest, TriangularGraph_RestrictionNoF5F2) {3 /* x */, 0 /* y */}, {2, 0}, {1, 0}, {0, 0}, {0, 2}, {0, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(5 /* featureId */, 0 /* segmentIdx */, m2::PointD(3, 0), *m_graph), MakeFakeEnding(4, 0, m2::PointD(0, 3), *m_graph), move(restrictions), *this); } @@ -191,7 +193,7 @@ UNIT_CLASS_TEST(RestrictionTest, TriangularGraph_RestrictionOnlyF5F3) {3 /* x */, 0 /* y */}, {2, 0}, {1, 0}, {0, 0}, {0, 2}, {0, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(5 /* featureId */, 0 /* segmentIdx */, m2::PointD(3, 0), *m_graph), MakeFakeEnding(4, 0, m2::PointD(0, 3), *m_graph), move(restrictionsNo), *this); } @@ -213,7 +215,7 @@ UNIT_CLASS_TEST(RestrictionTest, TriangularGraph_RestrictionNoF5F2RestrictionOnl {3 /* x */, 0 /* y */}, {2, 0}, {1, 0}, {0, 0}, {0, 2}, {0, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(5 /* featureId */, 0 /* segmentIdx */, m2::PointD(3, 0), *m_graph), MakeFakeEnding(4, 0, m2::PointD(0, 3), *m_graph), move(restrictionsNo), *this); } @@ -267,7 +269,7 @@ UNIT_CLASS_TEST(RestrictionTest, TwowayCornerGraph) vector<m2::PointD> const expectedGeom = {{3 /* x */, 0 /* y */}, {2, 0}, {1, 1}, {0, 2}, {0, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(3 /* featureId */, 0 /* segmentIdx */, m2::PointD(3, 0), *m_graph), MakeFakeEnding(4, 0, m2::PointD(0, 3), *m_graph), {}, *this); } @@ -281,7 +283,7 @@ UNIT_CLASS_TEST(RestrictionTest, TwowayCornerGraph_RestrictionF3F2No) {3 /* x */, 0 /* y */}, {2, 0}, {1, 0}, {0, 0}, {0, 1}, {0, 2}, {0, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(3 /* featureId */, 0 /* segmentIdx */, m2::PointD(3, 0), *m_graph), MakeFakeEnding(4, 0, m2::PointD(0, 3), *m_graph), move(restrictions), *this); } @@ -298,7 +300,7 @@ UNIT_CLASS_TEST(RestrictionTest, TwowayCornerGraph_RestrictionF3F1Only) {3 /* x */, 0 /* y */}, {2, 0}, {1, 0}, {0, 0}, {0, 1}, {0, 2}, {0, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(3 /* featureId */, 0 /* segmentIdx */, m2::PointD(3, 0), *m_graph), MakeFakeEnding(4, 0, m2::PointD(0, 3), *m_graph), move(restrictionsNo), *this); } @@ -373,7 +375,7 @@ UNIT_CLASS_TEST(RestrictionTest, TwoSquaresGraph) vector<m2::PointD> const expectedGeom = {{3 /* x */, 0 /* y */}, {2, 0}, {1, 1}, {0, 2}, {0, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(10 /* featureId */, 0 /* segmentIdx */, m2::PointD(3, 0), *m_graph), MakeFakeEnding(11, 0, m2::PointD(0, 3), *m_graph), {}, *this); } @@ -391,7 +393,7 @@ UNIT_CLASS_TEST(RestrictionTest, TwoSquaresGraph_RestrictionF10F3Only) {3 /* x */, 0 /* y */}, {2, 0}, {1, 0}, {1, 1}, {0, 2}, {0, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(10 /* featureId */, 0 /* segmentIdx */, m2::PointD(3, 0), *m_graph), MakeFakeEnding(11, 0, m2::PointD(0, 3), *m_graph), move(restrictionsNo), *this); } @@ -410,7 +412,7 @@ UNIT_CLASS_TEST(RestrictionTest, TwoSquaresGraph_RestrictionF10F3OnlyF3F4Only) {3 /* x */, 0 /* y */}, {2, 0}, {1, 0}, {0, 0}, {0, 2}, {0, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(10 /* featureId */, 0 /* segmentIdx */, m2::PointD(3, 0), *m_graph), MakeFakeEnding(11, 0, m2::PointD(0, 3), *m_graph), move(restrictionsNo), *this); } @@ -429,7 +431,7 @@ UNIT_CLASS_TEST(RestrictionTest, TwoSquaresGraph_RestrictionF2F8NoRestrictionF9F vector<m2::PointD> const expectedGeom = {{3 /* x */, 0 /* y */}, {2, 0}, {1, 1}, {0, 2}, {0, 3}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(10 /* featureId */, 0 /* segmentIdx */, m2::PointD(3, 0), *m_graph), MakeFakeEnding(11, 0, m2::PointD(0, 3), *m_graph), move(restrictionsNo), *this); } @@ -487,7 +489,7 @@ UNIT_TEST(FlagGraph) MakeStarter(MakeFakeEnding(0 /* featureId */, 0 /* segmentIdx */, m2::PointD(2, 0), *graph), MakeFakeEnding(6, 0, m2::PointD(0.5, 1), *graph), *graph); vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, {1, 0}, {1, 1}, {0.5, 1}}; - TestRouteGeometry(*starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); + TestRouteGeometry(*starter, Algorithm::Result::OK, expectedGeom); } // Route through flag graph with one restriciton (type no) from F0 to F3. @@ -500,7 +502,7 @@ UNIT_CLASS_TEST(RestrictionTest, FlagGraph_RestrictionF0F3No) {2 /* x */, 0 /* y */}, {1, 0}, {0, 0}, {0, 1}, {0.5, 1}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(0 /* featureId */, 0 /* segmentIdx */, m2::PointD(2, 0), *m_graph), MakeFakeEnding(6, 0, m2::PointD(0.5, 1), *m_graph), move(restrictions), *this); } @@ -514,7 +516,7 @@ UNIT_CLASS_TEST(RestrictionTest, FlagGraph_RestrictionF0F1Only) vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, {1, 0}, {1, 1}, {0.5, 1}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(0 /* featureId */, 0 /* segmentIdx */, m2::PointD(2, 0), *m_graph), MakeFakeEnding(6, 0, m2::PointD(0.5, 1), *m_graph), move(restrictions), *this); } @@ -537,7 +539,7 @@ UNIT_CLASS_TEST(RestrictionTest, FlagGraph_PermutationsF1F3NoF7F8OnlyF8F4OnlyF4F vector<m2::PointD> const expectedGeom = { {2 /* x */, 0 /* y */}, {1, 0}, {0, 0}, {0, 1}, {0.5, 1}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(0 /* featureId */, 0 /* segmentIdx */, m2::PointD(2, 0), *m_graph), MakeFakeEnding(6, 0, m2::PointD(0.5, 1), *m_graph), move(restrictionsNo), *this); } @@ -592,7 +594,7 @@ UNIT_TEST(PosterGraph) MakeFakeEnding(6, 0, m2::PointD(2, 1), *graph), *graph); vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, {1, 0}, {1, 1}, {2, 1}}; - TestRouteGeometry(*starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); + TestRouteGeometry(*starter, Algorithm::Result::OK, expectedGeom); } // Route through poster graph with restrictions F0-F3 (type no). @@ -605,7 +607,7 @@ UNIT_CLASS_TEST(RestrictionTest, PosterGraph_RestrictionF0F3No) {2 /* x */, 0 /* y */}, {1, 0}, {0, 0}, {0, 1}, {0.5, 1}, {1, 1}, {2, 1}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(0 /* featureId */, 0 /* segmentIdx */, m2::PointD(2, 0), *m_graph), MakeFakeEnding(6, 0, m2::PointD(2, 1), *m_graph), move(restrictions), *this); } @@ -624,7 +626,7 @@ UNIT_CLASS_TEST(RestrictionTest, PosterGraph_RestrictionF0F1Only) vector<m2::PointD> const expectedGeom = { {2 /* x */, 0 /* y */}, {1, 0}, {0, 0}, {0, 1}, {0.5, 1}, {1, 1}, {2, 1}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(0 /* featureId */, 0 /* segmentIdx */, m2::PointD(2, 0), *m_graph), MakeFakeEnding(6, 0, m2::PointD(2, 1), *m_graph), move(restrictionsNo), *this); } @@ -671,7 +673,7 @@ UNIT_TEST(TwoWayGraph) MakeFakeEnding(2, 0, m2::PointD(4, 0), *graph), *graph); vector<m2::PointD> const expectedGeom = {{-1 /* x */, 0 /* y */}, {0, 0}, {1, 0}, {3, 0}, {4, 0}}; - TestRouteGeometry(*starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); + TestRouteGeometry(*starter, Algorithm::Result::OK, expectedGeom); } // 1 *---F4----* @@ -720,7 +722,7 @@ UNIT_TEST(SquaresGraph) MakeStarter(MakeFakeEnding(0 /* featureId */, 0 /* segmentIdx */, m2::PointD(3, 0), *graph), MakeFakeEnding(5, 0, m2::PointD(0, 0), *graph), *graph); vector<m2::PointD> const expectedGeom = {{3 /* x */, 0 /* y */}, {2, 0}, {1, 0}, {0, 0}}; - TestRouteGeometry(*starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); + TestRouteGeometry(*starter, Algorithm::Result::OK, expectedGeom); } // It's a test on correct working in case when because of adding restrictions @@ -740,7 +742,7 @@ UNIT_CLASS_TEST(RestrictionTest, SquaresGraph_RestrictionF0F1OnlyF1F5Only) vector<m2::PointD> const expectedGeom = {{3 /* x */, 0 /* y */}, {2, 0}, {1, 0}, {0, 0}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(0 /* featureId */, 0 /* segmentIdx */, m2::PointD(3, 0), *m_graph), MakeFakeEnding(5, 0, m2::PointD(0, 0), *m_graph), move(restrictionsNo), *this); } @@ -782,7 +784,7 @@ UNIT_CLASS_TEST(RestrictionTest, LineGraph_RestrictionF1F1No) {0 /* x */, 0 /* y */}, {1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(0 /* featureId */, 0 /* segmentIdx */, m2::PointD(0, 0), *m_graph), MakeFakeEnding(2, 0, m2::PointD(5, 0), *m_graph), move(restrictions), *this); } @@ -835,7 +837,7 @@ UNIT_CLASS_TEST(RestrictionTest, FGraph_RestrictionF0F2Only) vector<m2::PointD> const expectedGeom = {{0 /* x */, 0 /* y */}, {0, 1}, {1, 1}}; TestRestrictions( - expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedGeom, Algorithm::Result::OK, MakeFakeEnding(0 /* featureId */, 0 /* segmentIdx */, m2::PointD(0, 0), *m_graph), MakeFakeEnding(1, 0, m2::PointD(1, 1), *m_graph), move(restrictionsNo), *this); } @@ -889,7 +891,7 @@ UNIT_CLASS_TEST(RestrictionTest, NonPassThroughStart) SetStarter(MakeFakeEnding(0 /* featureId */, 0 /* segmentIdx */, m2::PointD(0, 0), *m_graph), MakeFakeEnding(2, 0, m2::PointD(3, 0), *m_graph)); - TestRouteGeometry(*m_starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); + TestRouteGeometry(*m_starter, Algorithm::Result::OK, expectedGeom); } UNIT_CLASS_TEST(RestrictionTest, NonPassThroughShortWay) @@ -901,7 +903,7 @@ UNIT_CLASS_TEST(RestrictionTest, NonPassThroughShortWay) SetStarter(MakeFakeEnding(0 /* featureId */, 0 /* segmentIdx */, m2::PointD(0, 0), *m_graph), MakeFakeEnding(2, 0, m2::PointD(3, 0), *m_graph)); - TestRouteGeometry(*m_starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); + TestRouteGeometry(*m_starter, Algorithm::Result::OK, expectedGeom); } UNIT_CLASS_TEST(RestrictionTest, NonPassThroughWay) @@ -911,7 +913,7 @@ UNIT_CLASS_TEST(RestrictionTest, NonPassThroughWay) SetStarter(MakeFakeEnding(0 /* featureId */, 0 /* segmentIdx */, m2::PointD(0, 0), *m_graph), MakeFakeEnding(2, 0, m2::PointD(3, 0), *m_graph)); - TestRouteGeometry(*m_starter, AStarAlgorithm<IndexGraphStarter>::Result::NoPath, {}); + TestRouteGeometry(*m_starter, Algorithm::Result::NoPath, {}); } UNIT_CLASS_TEST(RestrictionTest, NontransiStartAndShortWay) @@ -923,6 +925,6 @@ UNIT_CLASS_TEST(RestrictionTest, NontransiStartAndShortWay) SetStarter(MakeFakeEnding(0 /* featureId */, 0 /* segmentIdx */, m2::PointD(0, 0), *m_graph), MakeFakeEnding(2, 0, m2::PointD(3, 0), *m_graph)); - TestRouteGeometry(*m_starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); + TestRouteGeometry(*m_starter, Algorithm::Result::OK, expectedGeom); } } // namespace routing_test diff --git a/routing/routing_tests/routing_algorithm.cpp b/routing/routing_tests/routing_algorithm.cpp index 63854258f4..f5d385318a 100644 --- a/routing/routing_tests/routing_algorithm.cpp +++ b/routing/routing_tests/routing_algorithm.cpp @@ -1,6 +1,7 @@ #include "routing/routing_tests/routing_algorithm.hpp" #include "routing/base/astar_algorithm.hpp" +#include "routing/base/astar_graph.hpp" #include "routing/maxspeeds.hpp" #include "routing/routing_helpers.hpp" @@ -44,19 +45,21 @@ private: double const weight; }; +using Algorithm = AStarAlgorithm<Junction, WeightedEdge, double>; + /// A wrapper around IRoadGraph, which makes it possible to use IRoadGraph with astar algorithms. -class RoadGraph +class RoadGraph : public AStarGraph<Junction, WeightedEdge, double> { public: - using Vertex = Junction; - using Edge = WeightedEdge; - using Weight = double; + using Vertex = AStarGraph::Vertex; + using Edge = AStarGraph::Edge; + using Weight = AStarGraph::Weight; explicit RoadGraph(IRoadGraph const & roadGraph) : m_roadGraph(roadGraph), m_maxSpeedMPS(KMPH2MPS(roadGraph.GetMaxSpeedKMpH())) {} - void GetOutgoingEdgesList(Junction const & v, vector<WeightedEdge> & adj) const + void GetOutgoingEdgesList(Vertex const & v, vector<Edge> & adj) override { IRoadGraph::TEdgeVector edges; m_roadGraph.GetOutgoingEdges(v, edges); @@ -74,7 +77,7 @@ public: } } - void GetIngoingEdgesList(Junction const & v, vector<WeightedEdge> & adj) const + void GetIngoingEdgesList(Vertex const & v, vector<Edge> & adj) override { IRoadGraph::TEdgeVector edges; m_roadGraph.GetIngoingEdges(v, edges); @@ -92,7 +95,7 @@ public: } } - double HeuristicCostEstimate(Junction const & v, Junction const & w) const + double HeuristicCostEstimate(Vertex const & v, Vertex const & w) override { return TimeBetweenSec(v, w, m_maxSpeedMPS); } @@ -102,13 +105,13 @@ private: double const m_maxSpeedMPS; }; -TestAStarBidirectionalAlgo::Result Convert(AStarAlgorithm<RoadGraph>::Result value) +TestAStarBidirectionalAlgo::Result Convert(Algorithm::Result value) { switch (value) { - case AStarAlgorithm<RoadGraph>::Result::OK: return TestAStarBidirectionalAlgo::Result::OK; - case AStarAlgorithm<RoadGraph>::Result::NoPath: return TestAStarBidirectionalAlgo::Result::NoPath; - case AStarAlgorithm<RoadGraph>::Result::Cancelled: return TestAStarBidirectionalAlgo::Result::Cancelled; + case Algorithm::Result::OK: return TestAStarBidirectionalAlgo::Result::OK; + case Algorithm::Result::NoPath: return TestAStarBidirectionalAlgo::Result::NoPath; + case Algorithm::Result::Cancelled: return TestAStarBidirectionalAlgo::Result::Cancelled; } UNREACHABLE(); @@ -139,9 +142,9 @@ TestAStarBidirectionalAlgo::Result TestAStarBidirectionalAlgo::CalculateRoute( { RoadGraph roadGraph(graph); base::Cancellable const cancellable; - AStarAlgorithm<RoadGraph>::Params params(roadGraph, startPos, finalPos, {} /* prevRoute */, + Algorithm::Params params(roadGraph, startPos, finalPos, {} /* prevRoute */, cancellable, {} /* onVisitJunctionFn */, {} /* checkLength */); - AStarAlgorithm<RoadGraph>::Result const res = AStarAlgorithm<RoadGraph>().FindPathBidirectional(params, path); + Algorithm::Result const res = Algorithm().FindPathBidirectional(params, path); return Convert(res); } } // namespace routing |