1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
|
#pragma once
#include "routing/edge_estimator.hpp"
#include "routing/index_graph.hpp"
#include "routing/index_graph_loader.hpp"
#include "routing/index_graph_starter.hpp"
#include "routing/num_mwm_id.hpp"
#include "routing/restrictions_serialization.hpp"
#include "routing/road_access.hpp"
#include "routing/road_point.hpp"
#include "routing/segment.hpp"
#include "routing/base/astar_algorithm.hpp"
#include "traffic/traffic_info.hpp"
#include "indexer/classificator_loader.hpp"
#include "geometry/point2d.hpp"
#include "std/algorithm.hpp"
#include "std/cstdint.hpp"
#include "std/map.hpp"
#include "std/shared_ptr.hpp"
#include "std/unique_ptr.hpp"
#include "std/unordered_map.hpp"
#include "std/utility.hpp"
#include "std/vector.hpp"
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.
NumMwmId constexpr kTestNumMwmId = 777;
struct RestrictionTest
{
RestrictionTest() { classificator::Load(); }
void Init(unique_ptr<WorldGraph> graph) { m_graph = move(graph); }
void SetStarter(IndexGraphStarter::FakeVertex const & start,
IndexGraphStarter::FakeVertex const & finish)
{
m_starter = make_unique<IndexGraphStarter>(start, finish, *m_graph);
}
void SetRestrictions(RestrictionVec && restrictions)
{
m_graph->GetIndexGraph(kTestNumMwmId).SetRestrictions(move(restrictions));
}
unique_ptr<WorldGraph> m_graph;
unique_ptr<IndexGraphStarter> m_starter;
};
class TestGeometryLoader final : public routing::GeometryLoader
{
public:
// GeometryLoader overrides:
void Load(uint32_t featureId, routing::RoadGeometry & road) const override;
void AddRoad(uint32_t featureId, bool oneWay, float speed,
routing::RoadGeometry::Points const & points);
private:
unordered_map<uint32_t, routing::RoadGeometry> m_roads;
};
class ZeroGeometryLoader final : public routing::GeometryLoader
{
public:
// GeometryLoader overrides:
void Load(uint32_t featureId, routing::RoadGeometry & road) const override;
};
class TestIndexGraphLoader final : public IndexGraphLoader
{
public:
// IndexGraphLoader overrides:
IndexGraph & GetIndexGraph(NumMwmId mwmId) override;
virtual void Clear() override;
void AddGraph(NumMwmId mwmId, unique_ptr<IndexGraph> graph);
private:
unordered_map<NumMwmId, unique_ptr<IndexGraph>> m_graphs;
};
// An estimator that uses the information from the supported |segmentWeights| map
// and completely ignores road geometry. The underlying graph is assumed
// to be directed, i.e. it is not guaranteed that each segment has its reverse
// in the map.
class WeightedEdgeEstimator final : public EdgeEstimator
{
public:
WeightedEdgeEstimator(map<Segment, double> const & segmentWeights)
: m_segmentWeights(segmentWeights)
{
}
// EdgeEstimator overrides:
double CalcSegmentWeight(Segment const & segment, RoadGeometry const & /* road */) const override;
double CalcHeuristic(m2::PointD const & /* from */, m2::PointD const & /* to */) const override;
double CalcLeapWeight(m2::PointD const & /* from */,
m2::PointD const & /* to */) const override;
double GetUTurnPenalty() const override;
bool LeapIsAllowed(NumMwmId /* mwmId */) const override;
private:
map<Segment, double> m_segmentWeights;
};
// A simple class to test graph algorithms for the index graph
// that do not depend on road geometry (but may depend on the
// lengths of roads).
class TestIndexGraphTopology final
{
public:
using Vertex = uint32_t;
using Edge = pair<Vertex, Vertex>;
// Creates an empty graph on |numVertices| vertices.
TestIndexGraphTopology(uint32_t numVertices);
// Adds a weighted directed edge to the graph. Multi-edges are not supported.
// *NOTE* The edges are added lazily, i.e. edge requests are only stored here
// and the graph itself is built only after a call to FindPath.
void AddDirectedEdge(Vertex from, Vertex to, double weight);
// Blocks a previously added edge without removing it from the graph.
void BlockEdge(Vertex from, Vertex to);
// Finds a path between the start and finish vertices. Returns true iff a path exists.
bool FindPath(Vertex start, Vertex finish, double & pathWeight, vector<Edge> & pathEdges) const;
private:
struct EdgeRequest
{
uint32_t m_id = 0;
Vertex m_from = 0;
Vertex m_to = 0;
double m_weight = 0.0;
bool m_isBlocked = false;
EdgeRequest(uint32_t id, Vertex from, Vertex to, double weight)
: m_id(id), m_from(from), m_to(to), m_weight(weight)
{
}
};
// Builder builds a graph from edge requests.
struct Builder
{
Builder(uint32_t numVertices) : m_numVertices(numVertices) {}
unique_ptr<WorldGraph> PrepareIndexGraph();
void BuildJoints();
void BuildGraphFromRequests(vector<EdgeRequest> const & requests);
void BuildSegmentFromEdge(EdgeRequest const & request);
uint32_t const m_numVertices;
map<Edge, double> m_edgeWeights;
map<Segment, double> m_segmentWeights;
map<Segment, Edge> m_segmentToEdge;
map<Vertex, vector<Segment>> m_outgoingSegments;
map<Vertex, vector<Segment>> m_ingoingSegments;
vector<Joint> m_joints;
RoadAccess m_roadAccess;
};
void AddDirectedEdge(vector<EdgeRequest> & edgeRequests, Vertex from, Vertex to,
double weight) const;
uint32_t const m_numVertices;
vector<EdgeRequest> m_edgeRequests;
};
unique_ptr<WorldGraph> BuildWorldGraph(unique_ptr<TestGeometryLoader> loader,
shared_ptr<EdgeEstimator> estimator,
vector<Joint> const & joints);
unique_ptr<WorldGraph> BuildWorldGraph(unique_ptr<ZeroGeometryLoader> loader,
shared_ptr<EdgeEstimator> estimator,
vector<Joint> const & joints);
routing::Joint MakeJoint(vector<routing::RoadPoint> const & points);
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);
void TestRouteGeometry(
routing::IndexGraphStarter & starter,
routing::AStarAlgorithm<routing::IndexGraphStarter>::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,
routing::IndexGraphStarter::FakeVertex const & start,
routing::IndexGraphStarter::FakeVertex const & finish,
RestrictionVec && restrictions, RestrictionTest & restrictionTest);
// Tries to find a unique path from |from| to |to| in |graph|.
// If |expectedPathFound| is true, |expectedWeight| and |expectedEdges| must
// specify the weight and edges of the unique shortest path.
// If |expectedPathFound| is false, |expectedWeight| and |expectedEdges| may
// take arbitrary values.
void TestTopologyGraph(TestIndexGraphTopology const & graph, TestIndexGraphTopology::Vertex from,
TestIndexGraphTopology::Vertex to, bool expectedPathFound,
double const expectedWeight,
vector<TestIndexGraphTopology::Edge> const & expectedEdges);
} // namespace routing_test
|
