From 310e1416ef68fe610ffdec4d03d692a4878a7069 Mon Sep 17 00:00:00 2001 From: Vladimir Byko-Ianko Date: Tue, 27 Mar 2018 11:06:31 +0300 Subject: Moving routing_algorithm.hpp and cpp to routing_tests. --- routing/CMakeLists.txt | 2 - routing/routing_algorithm.cpp | 196 ---------------------------- routing/routing_algorithm.hpp | 55 -------- routing/routing_tests/CMakeLists.txt | 2 + routing/routing_tests/astar_router_test.cpp | 2 +- routing/routing_tests/routing_algorithm.cpp | 196 ++++++++++++++++++++++++++++ routing/routing_tests/routing_algorithm.hpp | 55 ++++++++ 7 files changed, 254 insertions(+), 254 deletions(-) delete mode 100644 routing/routing_algorithm.cpp delete mode 100644 routing/routing_algorithm.hpp create mode 100644 routing/routing_tests/routing_algorithm.cpp create mode 100644 routing/routing_tests/routing_algorithm.hpp (limited to 'routing') diff --git a/routing/CMakeLists.txt b/routing/CMakeLists.txt index 1d86df5670..5f6e1d90d3 100644 --- a/routing/CMakeLists.txt +++ b/routing/CMakeLists.txt @@ -90,8 +90,6 @@ set( router.hpp router_delegate.cpp router_delegate.hpp - routing_algorithm.cpp - routing_algorithm.hpp routing_exceptions.hpp routing_helpers.cpp routing_helpers.hpp diff --git a/routing/routing_algorithm.cpp b/routing/routing_algorithm.cpp deleted file mode 100644 index cc02d28a1c..0000000000 --- a/routing/routing_algorithm.cpp +++ /dev/null @@ -1,196 +0,0 @@ -#include "routing/routing_algorithm.hpp" - -#include "routing/base/astar_algorithm.hpp" -#include "routing/base/astar_progress.hpp" -#include "routing/road_graph.hpp" - -#include "base/assert.hpp" - -#include "geometry/mercator.hpp" - -namespace routing -{ - -namespace -{ -uint32_t constexpr kVisitPeriod = 4; -float constexpr kProgressInterval = 2; - -double constexpr KMPH2MPS = 1000.0 / (60 * 60); - -inline double TimeBetweenSec(Junction const & j1, Junction const & j2, double speedMPS) -{ - ASSERT(speedMPS > 0.0, ()); - ASSERT_NOT_EQUAL(j1.GetAltitude(), feature::kInvalidAltitude, ()); - ASSERT_NOT_EQUAL(j2.GetAltitude(), feature::kInvalidAltitude, ()); - - double const distanceM = MercatorBounds::DistanceOnEarth(j1.GetPoint(), j2.GetPoint()); - double const altitudeDiffM = - static_cast(j2.GetAltitude()) - static_cast(j1.GetAltitude()); - return sqrt(distanceM * distanceM + altitudeDiffM * altitudeDiffM) / speedMPS; -} - -/// A class which represents an weighted edge used by RoadGraph. -class WeightedEdge -{ -public: - WeightedEdge(Junction const & target, double weight) : target(target), weight(weight) {} - - inline Junction const & GetTarget() const { return target; } - - inline double GetWeight() const { return weight; } - -private: - Junction const target; - double const weight; -}; - -/// A wrapper around IRoadGraph, which makes it possible to use IRoadGraph with astar algorithms. -class RoadGraph -{ -public: - using Vertex = Junction; - using Edge = WeightedEdge; - using Weight = double; - - RoadGraph(IRoadGraph const & roadGraph) - : m_roadGraph(roadGraph) - , m_maxSpeedMPS(roadGraph.GetMaxSpeedKMPH() * KMPH2MPS) - {} - - void GetOutgoingEdgesList(Junction const & v, vector & adj) const - { - IRoadGraph::TEdgeVector edges; - m_roadGraph.GetOutgoingEdges(v, edges); - - adj.clear(); - adj.reserve(edges.size()); - - for (auto const & e : edges) - { - ASSERT_EQUAL(v, e.GetStartJunction(), ()); - - double const speedMPS = m_roadGraph.GetSpeedKMPH(e) * KMPH2MPS; - adj.emplace_back(e.GetEndJunction(), TimeBetweenSec(e.GetStartJunction(), e.GetEndJunction(), speedMPS)); - } - } - - void GetIngoingEdgesList(Junction const & v, vector & adj) const - { - IRoadGraph::TEdgeVector edges; - m_roadGraph.GetIngoingEdges(v, edges); - - adj.clear(); - adj.reserve(edges.size()); - - for (auto const & e : edges) - { - ASSERT_EQUAL(v, e.GetEndJunction(), ()); - - double const speedMPS = m_roadGraph.GetSpeedKMPH(e) * KMPH2MPS; - adj.emplace_back(e.GetStartJunction(), TimeBetweenSec(e.GetStartJunction(), e.GetEndJunction(), speedMPS)); - } - } - - double HeuristicCostEstimate(Junction const & v, Junction const & w) const - { - return TimeBetweenSec(v, w, m_maxSpeedMPS); - } - -private: - IRoadGraph const & m_roadGraph; - double const m_maxSpeedMPS; -}; - -typedef AStarAlgorithm TAlgorithmImpl; - -IRoutingAlgorithm::Result Convert(TAlgorithmImpl::Result value) -{ - switch (value) - { - case TAlgorithmImpl::Result::OK: return IRoutingAlgorithm::Result::OK; - case TAlgorithmImpl::Result::NoPath: return IRoutingAlgorithm::Result::NoPath; - case TAlgorithmImpl::Result::Cancelled: return IRoutingAlgorithm::Result::Cancelled; - } - ASSERT(false, ("Unexpected TAlgorithmImpl::Result value:", value)); - return IRoutingAlgorithm::Result::NoPath; -} -} // namespace - -string DebugPrint(IRoutingAlgorithm::Result const & value) -{ - switch (value) - { - case IRoutingAlgorithm::Result::OK: - return "OK"; - case IRoutingAlgorithm::Result::NoPath: - return "NoPath"; - case IRoutingAlgorithm::Result::Cancelled: - return "Cancelled"; - } - return string(); -} - -// *************************** AStar routing algorithm implementation ************************************* - -IRoutingAlgorithm::Result AStarRoutingAlgorithm::CalculateRoute(IRoadGraph const & graph, - Junction const & startPos, - Junction const & finalPos, - RouterDelegate const & delegate, - RoutingResult & path) -{ - AStarProgress progress(0, 95); - uint32_t visitCount = 0; - - auto onVisitJunctionFn = [&](Junction const & junction, Junction const & /* target */) { - if (++visitCount % kVisitPeriod != 0) - return; - - delegate.OnPointCheck(junction.GetPoint()); - auto const lastValue = progress.GetLastValue(); - auto const newValue = progress.GetProgressForDirectedAlgo(junction.GetPoint()); - if (newValue - lastValue > kProgressInterval) - delegate.OnProgress(newValue); - - }; - - base::Cancellable const & cancellable = delegate; - progress.Initialize(startPos.GetPoint(), finalPos.GetPoint()); - RoadGraph roadGraph(graph); - TAlgorithmImpl::Params params(roadGraph, startPos, finalPos, nullptr /* prevRoute */, cancellable, - onVisitJunctionFn, {} /* checkLength */); - TAlgorithmImpl::Result const res = TAlgorithmImpl().FindPath(params, path); - return Convert(res); -} - -// *************************** AStar-bidirectional routing algorithm implementation *********************** - -IRoutingAlgorithm::Result AStarBidirectionalRoutingAlgorithm::CalculateRoute( - IRoadGraph const & graph, Junction const & startPos, Junction const & finalPos, - RouterDelegate const & delegate, RoutingResult & path) -{ - AStarProgress progress(0, 95); - uint32_t visitCount = 0; - - auto onVisitJunctionFn = [&](Junction const & junction, Junction const & target) { - if (++visitCount % kVisitPeriod != 0) - return; - - delegate.OnPointCheck(junction.GetPoint()); - auto const lastValue = progress.GetLastValue(); - auto const newValue = - progress.GetProgressForBidirectedAlgo(junction.GetPoint(), target.GetPoint()); - if (newValue - lastValue > kProgressInterval) - delegate.OnProgress(newValue); - }; - - base::Cancellable const & cancellable = delegate; - progress.Initialize(startPos.GetPoint(), finalPos.GetPoint()); - RoadGraph roadGraph(graph); - TAlgorithmImpl::Params params(roadGraph, startPos, finalPos, {} /* prevRoute */, cancellable, - onVisitJunctionFn, {} /* checkLength */); - TAlgorithmImpl::Result const res = TAlgorithmImpl().FindPathBidirectional(params, path); - return Convert(res); -} - -} // namespace routing diff --git a/routing/routing_algorithm.hpp b/routing/routing_algorithm.hpp deleted file mode 100644 index e1eb72467b..0000000000 --- a/routing/routing_algorithm.hpp +++ /dev/null @@ -1,55 +0,0 @@ -#pragma once - -#include "routing/base/routing_result.hpp" -#include "routing/road_graph.hpp" -#include "routing/router.hpp" - -#include "base/cancellable.hpp" - -#include "std/functional.hpp" -#include "std/string.hpp" -#include "std/vector.hpp" - -namespace routing -{ - -// IRoutingAlgorithm is an abstract interface of a routing algorithm, -// which searches the optimal way between two junctions on the graph -class IRoutingAlgorithm -{ -public: - enum class Result - { - OK, - NoPath, - Cancelled - }; - - virtual Result CalculateRoute(IRoadGraph const & graph, Junction const & startPos, - Junction const & finalPos, RouterDelegate const & delegate, - RoutingResult & path) = 0; -}; - -string DebugPrint(IRoutingAlgorithm::Result const & result); - -// AStar routing algorithm implementation -class AStarRoutingAlgorithm : public IRoutingAlgorithm -{ -public: - // IRoutingAlgorithm overrides: - Result CalculateRoute(IRoadGraph const & graph, Junction const & startPos, - Junction const & finalPos, RouterDelegate const & delegate, - RoutingResult & path) override; -}; - -// AStar-bidirectional routing algorithm implementation -class AStarBidirectionalRoutingAlgorithm : public IRoutingAlgorithm -{ -public: - // IRoutingAlgorithm overrides: - Result CalculateRoute(IRoadGraph const & graph, Junction const & startPos, - Junction const & finalPos, RouterDelegate const & delegate, - RoutingResult & path) override; -}; - -} // namespace routing diff --git a/routing/routing_tests/CMakeLists.txt b/routing/routing_tests/CMakeLists.txt index 5a1f98e9ab..856cbf6d9d 100644 --- a/routing/routing_tests/CMakeLists.txt +++ b/routing/routing_tests/CMakeLists.txt @@ -24,6 +24,8 @@ set( road_graph_builder.hpp road_graph_nearest_edges_test.cpp route_tests.cpp + routing_algorithm.cpp + routing_algorithm.hpp routing_helpers_tests.cpp routing_session_test.cpp turns_generator_test.cpp diff --git a/routing/routing_tests/astar_router_test.cpp b/routing/routing_tests/astar_router_test.cpp index 1b41e723e0..3584aefa32 100644 --- a/routing/routing_tests/astar_router_test.cpp +++ b/routing/routing_tests/astar_router_test.cpp @@ -1,8 +1,8 @@ #include "testing/testing.hpp" #include "routing/routing_tests/road_graph_builder.hpp" +#include "routing/routing_tests/routing_algorithm.hpp" -#include "routing/routing_algorithm.hpp" #include "routing/features_road_graph.hpp" #include "routing/route.hpp" #include "routing/router_delegate.hpp" diff --git a/routing/routing_tests/routing_algorithm.cpp b/routing/routing_tests/routing_algorithm.cpp new file mode 100644 index 0000000000..f7821d899a --- /dev/null +++ b/routing/routing_tests/routing_algorithm.cpp @@ -0,0 +1,196 @@ +#include "routing/routing_tests/routing_algorithm.hpp" + +#include "routing/base/astar_algorithm.hpp" +#include "routing/base/astar_progress.hpp" +#include "routing/road_graph.hpp" + +#include "base/assert.hpp" + +#include "geometry/mercator.hpp" + +namespace routing +{ + +namespace +{ +uint32_t constexpr kVisitPeriod = 4; +float constexpr kProgressInterval = 2; + +double constexpr KMPH2MPS = 1000.0 / (60 * 60); + +inline double TimeBetweenSec(Junction const & j1, Junction const & j2, double speedMPS) +{ + ASSERT(speedMPS > 0.0, ()); + ASSERT_NOT_EQUAL(j1.GetAltitude(), feature::kInvalidAltitude, ()); + ASSERT_NOT_EQUAL(j2.GetAltitude(), feature::kInvalidAltitude, ()); + + double const distanceM = MercatorBounds::DistanceOnEarth(j1.GetPoint(), j2.GetPoint()); + double const altitudeDiffM = + static_cast(j2.GetAltitude()) - static_cast(j1.GetAltitude()); + return sqrt(distanceM * distanceM + altitudeDiffM * altitudeDiffM) / speedMPS; +} + +/// A class which represents an weighted edge used by RoadGraph. +class WeightedEdge +{ +public: + WeightedEdge(Junction const & target, double weight) : target(target), weight(weight) {} + + inline Junction const & GetTarget() const { return target; } + + inline double GetWeight() const { return weight; } + +private: + Junction const target; + double const weight; +}; + +/// A wrapper around IRoadGraph, which makes it possible to use IRoadGraph with astar algorithms. +class RoadGraph +{ +public: + using Vertex = Junction; + using Edge = WeightedEdge; + using Weight = double; + + RoadGraph(IRoadGraph const & roadGraph) + : m_roadGraph(roadGraph) + , m_maxSpeedMPS(roadGraph.GetMaxSpeedKMPH() * KMPH2MPS) + {} + + void GetOutgoingEdgesList(Junction const & v, vector & adj) const + { + IRoadGraph::TEdgeVector edges; + m_roadGraph.GetOutgoingEdges(v, edges); + + adj.clear(); + adj.reserve(edges.size()); + + for (auto const & e : edges) + { + ASSERT_EQUAL(v, e.GetStartJunction(), ()); + + double const speedMPS = m_roadGraph.GetSpeedKMPH(e) * KMPH2MPS; + adj.emplace_back(e.GetEndJunction(), TimeBetweenSec(e.GetStartJunction(), e.GetEndJunction(), speedMPS)); + } + } + + void GetIngoingEdgesList(Junction const & v, vector & adj) const + { + IRoadGraph::TEdgeVector edges; + m_roadGraph.GetIngoingEdges(v, edges); + + adj.clear(); + adj.reserve(edges.size()); + + for (auto const & e : edges) + { + ASSERT_EQUAL(v, e.GetEndJunction(), ()); + + double const speedMPS = m_roadGraph.GetSpeedKMPH(e) * KMPH2MPS; + adj.emplace_back(e.GetStartJunction(), TimeBetweenSec(e.GetStartJunction(), e.GetEndJunction(), speedMPS)); + } + } + + double HeuristicCostEstimate(Junction const & v, Junction const & w) const + { + return TimeBetweenSec(v, w, m_maxSpeedMPS); + } + +private: + IRoadGraph const & m_roadGraph; + double const m_maxSpeedMPS; +}; + +typedef AStarAlgorithm TAlgorithmImpl; + +IRoutingAlgorithm::Result Convert(TAlgorithmImpl::Result value) +{ + switch (value) + { + case TAlgorithmImpl::Result::OK: return IRoutingAlgorithm::Result::OK; + case TAlgorithmImpl::Result::NoPath: return IRoutingAlgorithm::Result::NoPath; + case TAlgorithmImpl::Result::Cancelled: return IRoutingAlgorithm::Result::Cancelled; + } + ASSERT(false, ("Unexpected TAlgorithmImpl::Result value:", value)); + return IRoutingAlgorithm::Result::NoPath; +} +} // namespace + +string DebugPrint(IRoutingAlgorithm::Result const & value) +{ + switch (value) + { + case IRoutingAlgorithm::Result::OK: + return "OK"; + case IRoutingAlgorithm::Result::NoPath: + return "NoPath"; + case IRoutingAlgorithm::Result::Cancelled: + return "Cancelled"; + } + return string(); +} + +// *************************** AStar routing algorithm implementation ************************************* + +IRoutingAlgorithm::Result AStarRoutingAlgorithm::CalculateRoute(IRoadGraph const & graph, + Junction const & startPos, + Junction const & finalPos, + RouterDelegate const & delegate, + RoutingResult & path) +{ + AStarProgress progress(0, 95); + uint32_t visitCount = 0; + + auto onVisitJunctionFn = [&](Junction const & junction, Junction const & /* target */) { + if (++visitCount % kVisitPeriod != 0) + return; + + delegate.OnPointCheck(junction.GetPoint()); + auto const lastValue = progress.GetLastValue(); + auto const newValue = progress.GetProgressForDirectedAlgo(junction.GetPoint()); + if (newValue - lastValue > kProgressInterval) + delegate.OnProgress(newValue); + + }; + + base::Cancellable const & cancellable = delegate; + progress.Initialize(startPos.GetPoint(), finalPos.GetPoint()); + RoadGraph roadGraph(graph); + TAlgorithmImpl::Params params(roadGraph, startPos, finalPos, nullptr /* prevRoute */, cancellable, + onVisitJunctionFn, {} /* checkLength */); + TAlgorithmImpl::Result const res = TAlgorithmImpl().FindPath(params, path); + return Convert(res); +} + +// *************************** AStar-bidirectional routing algorithm implementation *********************** + +IRoutingAlgorithm::Result AStarBidirectionalRoutingAlgorithm::CalculateRoute( + IRoadGraph const & graph, Junction const & startPos, Junction const & finalPos, + RouterDelegate const & delegate, RoutingResult & path) +{ + AStarProgress progress(0, 95); + uint32_t visitCount = 0; + + auto onVisitJunctionFn = [&](Junction const & junction, Junction const & target) { + if (++visitCount % kVisitPeriod != 0) + return; + + delegate.OnPointCheck(junction.GetPoint()); + auto const lastValue = progress.GetLastValue(); + auto const newValue = + progress.GetProgressForBidirectedAlgo(junction.GetPoint(), target.GetPoint()); + if (newValue - lastValue > kProgressInterval) + delegate.OnProgress(newValue); + }; + + base::Cancellable const & cancellable = delegate; + progress.Initialize(startPos.GetPoint(), finalPos.GetPoint()); + RoadGraph roadGraph(graph); + TAlgorithmImpl::Params params(roadGraph, startPos, finalPos, {} /* prevRoute */, cancellable, + onVisitJunctionFn, {} /* checkLength */); + TAlgorithmImpl::Result const res = TAlgorithmImpl().FindPathBidirectional(params, path); + return Convert(res); +} + +} // namespace routing diff --git a/routing/routing_tests/routing_algorithm.hpp b/routing/routing_tests/routing_algorithm.hpp new file mode 100644 index 0000000000..e1eb72467b --- /dev/null +++ b/routing/routing_tests/routing_algorithm.hpp @@ -0,0 +1,55 @@ +#pragma once + +#include "routing/base/routing_result.hpp" +#include "routing/road_graph.hpp" +#include "routing/router.hpp" + +#include "base/cancellable.hpp" + +#include "std/functional.hpp" +#include "std/string.hpp" +#include "std/vector.hpp" + +namespace routing +{ + +// IRoutingAlgorithm is an abstract interface of a routing algorithm, +// which searches the optimal way between two junctions on the graph +class IRoutingAlgorithm +{ +public: + enum class Result + { + OK, + NoPath, + Cancelled + }; + + virtual Result CalculateRoute(IRoadGraph const & graph, Junction const & startPos, + Junction const & finalPos, RouterDelegate const & delegate, + RoutingResult & path) = 0; +}; + +string DebugPrint(IRoutingAlgorithm::Result const & result); + +// AStar routing algorithm implementation +class AStarRoutingAlgorithm : public IRoutingAlgorithm +{ +public: + // IRoutingAlgorithm overrides: + Result CalculateRoute(IRoadGraph const & graph, Junction const & startPos, + Junction const & finalPos, RouterDelegate const & delegate, + RoutingResult & path) override; +}; + +// AStar-bidirectional routing algorithm implementation +class AStarBidirectionalRoutingAlgorithm : public IRoutingAlgorithm +{ +public: + // IRoutingAlgorithm overrides: + Result CalculateRoute(IRoadGraph const & graph, Junction const & startPos, + Junction const & finalPos, RouterDelegate const & delegate, + RoutingResult & path) override; +}; + +} // namespace routing -- cgit v1.2.3