1 /***************************************************************************
2 testqgsnetworkanalysis.cpp
3 --------------------------
4 Date : November 2017
5 Copyright : (C) 2017 by Nyall Dawson
6 Email : nyall dot dawson at gmail dot com
7 ***************************************************************************
8 * *
9 * This program is free software; you can redistribute it and/or modify *
10 * it under the terms of the GNU General Public License as published by *
11 * the Free Software Foundation; either version 2 of the License, or *
12 * (at your option) any later version. *
13 * *
14 ***************************************************************************/
15 #include "qgstest.h"
16
17 //header for class being tested
18 #include "qgsgeometrysnapper.h"
19 #include "qgsgeometry.h"
20 #include <qgsapplication.h>
21 #include "qgsvectordataprovider.h"
22 #include "qgsvectorlayer.h"
23 #include "qgsvectorlayerdirector.h"
24 #include "qgsnetworkdistancestrategy.h"
25 #include "qgsgraphbuilder.h"
26 #include "qgsgraph.h"
27 #include "qgsgraphanalyzer.h"
28
29 class TestQgsNetworkAnalysis : public QObject
30 {
31 Q_OBJECT
32
33 public:
34
35 private slots:
36 void initTestCase();// will be called before the first testfunction is executed.
37 void cleanupTestCase();// will be called after the last testfunction was executed.
38 void init() ;// will be called before each testfunction is executed.
39 void cleanup() ;// will be called after every testfunction.
40 void testGraph();
41 void testBuild();
42 void testBuildTolerance();
43 void dijkkjkjkskkjsktra();
44 void testRouteFail();
45 void testRouteFail2();
46
47 private:
48 std::unique_ptr< QgsVectorLayer > buildNetwork();
49
50
51 };
52
53 class TestNetworkStrategy : public QgsNetworkStrategy
54 {
requiredAttributes() const55 QSet< int > requiredAttributes() const override
56 {
57 return QSet< int >() << 0;
58 }
cost(double,const QgsFeature & f) const59 QVariant cost( double, const QgsFeature &f ) const override
60 {
61 return f.attribute( 0 );
62 }
63 };
64
initTestCase()65 void TestQgsNetworkAnalysis::initTestCase()
66 {
67 //
68 // Runs once before any tests are run
69 //
70 // init QGIS's paths - true means that all path will be inited from prefix
71 QgsApplication::init();
72 QgsApplication::initQgis();
73 }
cleanupTestCase()74 void TestQgsNetworkAnalysis::cleanupTestCase()
75 {
76 QgsApplication::exitQgis();
77 }
init()78 void TestQgsNetworkAnalysis::init()
79 {
80
81 }
cleanup()82 void TestQgsNetworkAnalysis::cleanup()
83 {
84
85 }
86
testGraph()87 void TestQgsNetworkAnalysis::testGraph()
88 {
89 QgsGraph graph;
90 QCOMPARE( graph.vertexCount(), 0 );
91 QCOMPARE( graph.edgeCount(), 0 );
92 graph.addVertex( QgsPointXY( 1, 2 ) );
93 QCOMPARE( graph.vertexCount(), 1 );
94 QCOMPARE( graph.vertex( 0 ).point(), QgsPointXY( 1, 2 ) );
95 QVERIFY( graph.vertex( 0 ).outgoingEdges().empty() );
96 QVERIFY( graph.vertex( 0 ).incomingEdges().empty() );
97 QCOMPARE( graph.findVertex( QgsPointXY( 1, 2 ) ), 0 );
98 graph.addVertex( QgsPointXY( 3, 4 ) );
99 QCOMPARE( graph.vertexCount(), 2 );
100 QCOMPARE( graph.vertex( 1 ).point(), QgsPointXY( 3, 4 ) );
101 QVERIFY( graph.vertex( 1 ).outgoingEdges().empty() );
102 QVERIFY( graph.vertex( 1 ).incomingEdges().empty() );
103 QCOMPARE( graph.findVertex( QgsPointXY( 1, 2 ) ), 0 );
104 QCOMPARE( graph.findVertex( QgsPointXY( 3, 4 ) ), 1 );
105 QCOMPARE( graph.edgeCount(), 0 );
106
107 graph.addEdge( 0, 1, QVector< QVariant >() << 9 );
108 QCOMPARE( graph.edgeCount(), 1 );
109 QCOMPARE( graph.edge( 0 ).cost( 0 ).toInt(), 9 );
110 QCOMPARE( graph.edge( 0 ).fromVertex(), 0 );
111 QCOMPARE( graph.edge( 0 ).toVertex(), 1 );
112 QCOMPARE( graph.vertex( 0 ).incomingEdges(), QList< int >() );
113 QCOMPARE( graph.vertex( 0 ).outgoingEdges(), QList< int >() << 0 );
114 QCOMPARE( graph.vertex( 1 ).incomingEdges(), QList< int >() << 0 );
115 QCOMPARE( graph.vertex( 1 ).outgoingEdges(), QList< int >() );
116
117 graph.addVertex( QgsPointXY( 7, 8 ) );
118 QCOMPARE( graph.vertexCount(), 3 );
119 QCOMPARE( graph.vertex( 2 ).point(), QgsPointXY( 7, 8 ) );
120 QVERIFY( graph.vertex( 2 ).outgoingEdges().empty() );
121 QVERIFY( graph.vertex( 2 ).incomingEdges().empty() );
122 QCOMPARE( graph.edgeCount(), 1 );
123 graph.addEdge( 1, 2, QVector< QVariant >() << 8 );
124
125 QCOMPARE( graph.edge( 1 ).cost( 0 ).toInt(), 8 );
126 QCOMPARE( graph.edge( 1 ).fromVertex(), 1 );
127 QCOMPARE( graph.edge( 1 ).toVertex(), 2 );
128 QCOMPARE( graph.vertex( 1 ).incomingEdges(), QList< int >() << 0 );
129 QCOMPARE( graph.vertex( 1 ).outgoingEdges(), QList< int >() << 1 );
130 QCOMPARE( graph.vertex( 2 ).incomingEdges(), QList< int >() << 1 );
131 QCOMPARE( graph.vertex( 2 ).outgoingEdges(), QList< int >() );
132 }
133
buildNetwork()134 std::unique_ptr<QgsVectorLayer> TestQgsNetworkAnalysis::buildNetwork()
135 {
136 std::unique_ptr< QgsVectorLayer > l = std::make_unique< QgsVectorLayer >( QStringLiteral( "LineString?crs=epsg:4326&field=cost:int" ), QStringLiteral( "x" ), QStringLiteral( "memory" ) );
137
138 QgsFeature ff( 0 );
139 const QgsGeometry refGeom = QgsGeometry::fromWkt( QStringLiteral( "LineString(0 0, 10 0, 10 10)" ) );
140 ff.setGeometry( refGeom );
141 ff.setAttributes( QgsAttributes() << 1 );
142 QgsFeatureList flist;
143 flist << ff;
144 l->dataProvider()->addFeatures( flist );
145
146 return l;
147 }
148
149
testBuild()150 void TestQgsNetworkAnalysis::testBuild()
151 {
152 std::unique_ptr<QgsVectorLayer> network = buildNetwork();
153 std::unique_ptr< QgsVectorLayerDirector > director = std::make_unique< QgsVectorLayerDirector > ( network.get(),
154 -1, QString(), QString(), QString(), QgsVectorLayerDirector::DirectionBoth );
155 std::unique_ptr< QgsNetworkDistanceStrategy > strategy = std::make_unique< QgsNetworkDistanceStrategy >();
156 director->addStrategy( strategy.release() );
157 std::unique_ptr< QgsGraphBuilder > builder = std::make_unique< QgsGraphBuilder > ( network->sourceCrs(), true, 0 );
158
159 QVector<QgsPointXY > snapped;
160 director->makeGraph( builder.get(), QVector<QgsPointXY>() << QgsPointXY( 0, 0 ) << QgsPointXY( 10, 10 ), snapped );
161 QCOMPARE( snapped, QVector<QgsPointXY>() << QgsPointXY( 0, 0 ) << QgsPointXY( 10, 10 ) );
162 std::unique_ptr< QgsGraph > graph( builder->takeGraph() );
163 QCOMPARE( graph->vertexCount(), 3 );
164 QCOMPARE( graph->edgeCount(), 4 );
165 QCOMPARE( graph->vertex( 0 ).point(), QgsPointXY( 0, 0 ) );
166 QCOMPARE( graph->vertex( 0 ).outgoingEdges(), QList< int >() << 0 );
167 QCOMPARE( graph->edge( 0 ).fromVertex(), 0 );
168 QCOMPARE( graph->edge( 0 ).toVertex(), 1 );
169 QCOMPARE( graph->vertex( 0 ).incomingEdges(), QList< int >() << 1 );
170 QCOMPARE( graph->edge( 1 ).fromVertex(), 1 );
171 QCOMPARE( graph->edge( 1 ).toVertex(), 0 );
172 QCOMPARE( graph->vertex( 1 ).point(), QgsPointXY( 10, 0 ) );
173 QCOMPARE( graph->vertex( 1 ).outgoingEdges(), QList< int >() << 1 << 2 );
174 QCOMPARE( graph->vertex( 1 ).incomingEdges(), QList< int >() << 0 << 3 );
175 QCOMPARE( graph->edge( 3 ).fromVertex(), 2 );
176 QCOMPARE( graph->edge( 3 ).toVertex(), 1 );
177 QCOMPARE( graph->edge( 2 ).fromVertex(), 1 );
178 QCOMPARE( graph->edge( 2 ).toVertex(), 2 );
179 QCOMPARE( graph->vertex( 2 ).point(), QgsPointXY( 10, 10 ) );
180 QCOMPARE( graph->vertex( 2 ).outgoingEdges(), QList< int >() << 3 );
181 QCOMPARE( graph->vertex( 2 ).incomingEdges(), QList< int >() << 2 );
182
183 builder = std::make_unique< QgsGraphBuilder > ( network->sourceCrs(), true, 0 );
184 director->makeGraph( builder.get(), QVector<QgsPointXY>() << QgsPointXY( 10, 0 ) << QgsPointXY( 10, 10 ), snapped );
185 QCOMPARE( snapped, QVector<QgsPointXY>() << QgsPointXY( 10, 0 ) << QgsPointXY( 10, 10 ) );
186
187 builder = std::make_unique< QgsGraphBuilder > ( network->sourceCrs(), true, 0 );
188 director->makeGraph( builder.get(), QVector<QgsPointXY>(), snapped );
189 QCOMPARE( snapped, QVector<QgsPointXY>() );
190
191 builder = std::make_unique< QgsGraphBuilder > ( network->sourceCrs(), true, 0 );
192 director->makeGraph( builder.get(), QVector<QgsPointXY>() << QgsPointXY( 0.2, 0.1 ) << QgsPointXY( 10.1, 9 ), snapped );
193 QCOMPARE( snapped, QVector<QgsPointXY>() << QgsPointXY( 0.2, 0.0 ) << QgsPointXY( 10.0, 9 ) );
194 graph.reset( builder->takeGraph() );
195 QCOMPARE( graph->vertexCount(), 5 );
196 QCOMPARE( graph->edgeCount(), 8 );
197
198 }
199
testBuildTolerance()200 void TestQgsNetworkAnalysis::testBuildTolerance()
201 {
202 std::unique_ptr<QgsVectorLayer> network = buildNetwork();
203 // has already a linestring LineString(0 0, 10 0, 10 10)
204
205 QgsFeature ff( 0 );
206 // 0.1 distance gap
207 const QgsGeometry refGeom = QgsGeometry::fromWkt( QStringLiteral( "LineString(10.1 10, 20 10 )" ) );
208 ff.setGeometry( refGeom );
209 QgsFeatureList flist;
210 flist << ff;
211 network->dataProvider()->addFeatures( flist );
212
213 std::unique_ptr< QgsVectorLayerDirector > director = std::make_unique< QgsVectorLayerDirector > ( network.get(),
214 -1, QString(), QString(), QString(), QgsVectorLayerDirector::DirectionBoth );
215 std::unique_ptr< QgsNetworkDistanceStrategy > strategy = std::make_unique< QgsNetworkDistanceStrategy >();
216 director->addStrategy( strategy.release() );
217 std::unique_ptr< QgsGraphBuilder > builder = std::make_unique< QgsGraphBuilder > ( network->sourceCrs(), true, 0 );
218
219 QVector<QgsPointXY > snapped;
220 director->makeGraph( builder.get(), QVector<QgsPointXY>(), snapped );
221 std::unique_ptr< QgsGraph > graph( builder->takeGraph() );
222 QCOMPARE( graph->vertexCount(), 5 );
223 QCOMPARE( graph->edgeCount(), 6 );
224 QCOMPARE( graph->vertex( 0 ).point(), QgsPointXY( 0, 0 ) );
225 QCOMPARE( graph->vertex( 0 ).outgoingEdges(), QList< int >() << 0 );
226 QCOMPARE( graph->edge( 0 ).fromVertex(), 0 );
227 QCOMPARE( graph->edge( 0 ).toVertex(), 1 );
228 QCOMPARE( graph->vertex( 0 ).incomingEdges(), QList< int >() << 1 );
229 QCOMPARE( graph->edge( 1 ).fromVertex(), 1 );
230 QCOMPARE( graph->edge( 1 ).toVertex(), 0 );
231 QCOMPARE( graph->vertex( 1 ).point(), QgsPointXY( 10, 0 ) );
232 QCOMPARE( graph->vertex( 1 ).outgoingEdges(), QList< int >() << 1 << 2 );
233 QCOMPARE( graph->vertex( 1 ).incomingEdges(), QList< int >() << 0 << 3 );
234 QCOMPARE( graph->edge( 3 ).fromVertex(), 2 );
235 QCOMPARE( graph->edge( 3 ).toVertex(), 1 );
236 QCOMPARE( graph->edge( 2 ).fromVertex(), 1 );
237 QCOMPARE( graph->edge( 2 ).toVertex(), 2 );
238 QCOMPARE( graph->vertex( 2 ).point(), QgsPointXY( 10, 10 ) );
239 QCOMPARE( graph->vertex( 2 ).outgoingEdges(), QList< int >() << 3 );
240 QCOMPARE( graph->vertex( 2 ).incomingEdges(), QList< int >() << 2 );
241 QCOMPARE( graph->vertex( 3 ).point(), QgsPointXY( 10.1, 10 ) );
242 QCOMPARE( graph->vertex( 3 ).outgoingEdges(), QList< int >() << 4 );
243 QCOMPARE( graph->vertex( 3 ).incomingEdges(), QList< int >() << 5 );
244 QCOMPARE( graph->vertex( 4 ).point(), QgsPointXY( 20, 10 ) );
245 QCOMPARE( graph->edge( 5 ).fromVertex(), 4 );
246 QCOMPARE( graph->edge( 5 ).toVertex(), 3 );
247 QCOMPARE( graph->edge( 4 ).fromVertex(), 3 );
248 QCOMPARE( graph->edge( 4 ).toVertex(), 4 );
249
250 // with tolerance
251 const double tolerance = 0.11;
252
253 builder = std::make_unique< QgsGraphBuilder > ( network->sourceCrs(), true, tolerance );
254 director->makeGraph( builder.get(), QVector<QgsPointXY>(), snapped );
255 graph.reset( builder->takeGraph() );
256 QCOMPARE( graph->vertexCount(), 4 );
257 QCOMPARE( graph->edgeCount(), 6 );
258 QCOMPARE( graph->vertex( 0 ).point(), QgsPointXY( 0, 0 ) );
259 QCOMPARE( graph->vertex( 0 ).outgoingEdges(), QList< int >() << 0 );
260 QCOMPARE( graph->edge( 0 ).fromVertex(), 0 );
261 QCOMPARE( graph->edge( 0 ).toVertex(), 1 );
262 QCOMPARE( graph->vertex( 0 ).incomingEdges(), QList< int >() << 1 );
263 QCOMPARE( graph->edge( 1 ).fromVertex(), 1 );
264 QCOMPARE( graph->edge( 1 ).toVertex(), 0 );
265 QCOMPARE( graph->vertex( 1 ).point(), QgsPointXY( 10, 0 ) );
266 QCOMPARE( graph->vertex( 1 ).outgoingEdges(), QList< int >() << 1 << 2 );
267 QCOMPARE( graph->vertex( 1 ).incomingEdges(), QList< int >() << 0 << 3 );
268 QCOMPARE( graph->edge( 3 ).fromVertex(), 2 );
269 QCOMPARE( graph->edge( 3 ).toVertex(), 1 );
270 QCOMPARE( graph->edge( 2 ).fromVertex(), 1 );
271 QCOMPARE( graph->edge( 2 ).toVertex(), 2 );
272 QCOMPARE( graph->vertex( 2 ).point(), QgsPointXY( 10, 10 ) );
273 QCOMPARE( graph->vertex( 2 ).outgoingEdges(), QList< int >() << 3 << 4 );
274 QCOMPARE( graph->vertex( 2 ).incomingEdges(), QList< int >() << 2 << 5 );
275 QCOMPARE( graph->vertex( 3 ).point(), QgsPointXY( 20, 10 ) );
276 QCOMPARE( graph->vertex( 3 ).outgoingEdges(), QList< int >() << 5 );
277 QCOMPARE( graph->vertex( 3 ).incomingEdges(), QList< int >() << 4 );
278 QCOMPARE( graph->edge( 5 ).fromVertex(), 3 );
279 QCOMPARE( graph->edge( 5 ).toVertex(), 2 );
280 QCOMPARE( graph->edge( 4 ).fromVertex(), 2 );
281 QCOMPARE( graph->edge( 4 ).toVertex(), 3 );
282 }
283
dijkkjkjkskkjsktra()284 void TestQgsNetworkAnalysis::dijkkjkjkskkjsktra()
285 {
286 std::unique_ptr<QgsVectorLayer> network = buildNetwork();
287 // has already a linestring LineString(0 0, 10 0, 10 10)
288
289 // add some more lines to network
290 QgsFeature ff( 0 );
291 QgsFeatureList flist;
292
293 ff.setGeometry( QgsGeometry::fromWkt( QStringLiteral( "LineString(10 10, 20 10 )" ) ) );
294 ff.setAttributes( QgsAttributes() << 2 );
295 flist << ff;
296 ff.setGeometry( QgsGeometry::fromWkt( QStringLiteral( "LineString(10 20, 10 10 )" ) ) );
297 ff.setAttributes( QgsAttributes() << 3 );
298 flist << ff;
299 ff.setGeometry( QgsGeometry::fromWkt( QStringLiteral( "LineString(20 -10, 20 10 )" ) ) );
300 ff.setAttributes( QgsAttributes() << 4 );
301 flist << ff;
302 network->dataProvider()->addFeatures( flist );
303
304 /*
305 Out network is:
306 Numbers in brackets are cost for segment
307
308 20 o
309 |
310 v (3)
311 | (2)
312 10 o---->----o
313 | |
314 (1) ^ ^
315 (1) | |
316 0 o---->-----. |(4)
317 |
318 ^
319 |
320 -10 o
321
322 0 10 20
323
324 */
325
326 // build graph
327 std::unique_ptr< QgsVectorLayerDirector > director = std::make_unique< QgsVectorLayerDirector > ( network.get(),
328 -1, QString(), QString(), QString(), QgsVectorLayerDirector::DirectionBoth );
329 std::unique_ptr< QgsNetworkStrategy > strategy = std::make_unique< TestNetworkStrategy >();
330 director->addStrategy( strategy.release() );
331 std::unique_ptr< QgsGraphBuilder > builder = std::make_unique< QgsGraphBuilder > ( network->sourceCrs(), true, 0 );
332
333 QVector<QgsPointXY > snapped;
334 director->makeGraph( builder.get(), QVector<QgsPointXY>(), snapped );
335 std::unique_ptr< QgsGraph > graph( builder->takeGraph() );
336
337 int startVertexIdx = graph->findVertex( QgsPointXY( 20, -10 ) );
338 QVERIFY( startVertexIdx != -1 );
339
340 // both directions
341 QVector<int> resultTree;
342 QVector<double> resultCost;
343 QgsGraphAnalyzer::dijkstra( graph.get(), startVertexIdx, 0, &resultTree, &resultCost );
344
345 int point_0_0_idx = graph->findVertex( QgsPointXY( 0, 0 ) );
346 QVERIFY( point_0_0_idx != -1 );
347 int point_10_0_idx = graph->findVertex( QgsPointXY( 10, 0 ) );
348 QVERIFY( point_10_0_idx != -1 );
349 int point_10_10_idx = graph->findVertex( QgsPointXY( 10, 10 ) );
350 QVERIFY( point_10_10_idx != -1 );
351 int point_10_20_idx = graph->findVertex( QgsPointXY( 10, 20 ) );
352 QVERIFY( point_10_20_idx != -1 );
353 int point_20_10_idx = graph->findVertex( QgsPointXY( 20, 10 ) );
354 QVERIFY( point_20_10_idx != -1 );
355
356 QCOMPARE( resultTree.at( startVertexIdx ), -1 );
357 QCOMPARE( resultCost.at( startVertexIdx ), 0.0 );
358
359 QVERIFY( resultTree.at( point_20_10_idx ) != -1 );
360 QCOMPARE( resultCost.at( point_20_10_idx ), 4.0 );
361 QCOMPARE( graph->edge( resultTree.at( point_20_10_idx ) ).fromVertex(), startVertexIdx );
362 QCOMPARE( graph->edge( resultTree.at( point_20_10_idx ) ).toVertex(), point_20_10_idx );
363 QVERIFY( resultTree.at( point_10_10_idx ) != -1 );
364 QCOMPARE( resultCost.at( point_10_10_idx ), 6.0 );
365 QCOMPARE( graph->edge( resultTree.at( point_10_10_idx ) ).fromVertex(), point_20_10_idx );
366 QCOMPARE( graph->edge( resultTree.at( point_10_10_idx ) ).toVertex(), point_10_10_idx );
367 QVERIFY( resultTree.at( point_10_20_idx ) != -1 );
368 QCOMPARE( resultCost.at( point_10_20_idx ), 9.0 );
369 QCOMPARE( graph->edge( resultTree.at( point_10_20_idx ) ).fromVertex(), point_10_10_idx );
370 QCOMPARE( graph->edge( resultTree.at( point_10_20_idx ) ).toVertex(), point_10_20_idx );
371 QVERIFY( resultTree.at( point_10_0_idx ) != -1 );
372 QCOMPARE( resultCost.at( point_10_0_idx ), 7.0 );
373 QCOMPARE( graph->edge( resultTree.at( point_10_0_idx ) ).fromVertex(), point_10_10_idx );
374 QCOMPARE( graph->edge( resultTree.at( point_10_0_idx ) ).toVertex(), point_10_0_idx );
375 QVERIFY( resultTree.at( point_0_0_idx ) != -1 );
376 QCOMPARE( resultCost.at( point_0_0_idx ), 8.0 );
377 QCOMPARE( graph->edge( resultTree.at( point_0_0_idx ) ).fromVertex(), point_10_0_idx );
378 QCOMPARE( graph->edge( resultTree.at( point_0_0_idx ) ).toVertex(), point_0_0_idx );
379
380 // forward direction
381 director = std::make_unique< QgsVectorLayerDirector > ( network.get(),
382 -1, QString(), QString(), QString(), QgsVectorLayerDirector::DirectionForward );
383 strategy = std::make_unique< TestNetworkStrategy >();
384 director->addStrategy( strategy.release() );
385 builder = std::make_unique< QgsGraphBuilder > ( network->sourceCrs(), true, 0 );
386 director->makeGraph( builder.get(), QVector<QgsPointXY>(), snapped );
387 graph.reset( builder->takeGraph() );
388 startVertexIdx = graph->findVertex( QgsPointXY( 0, 0 ) );
389 QVERIFY( startVertexIdx != -1 );
390 resultTree.clear();
391 resultCost.clear();
392 QgsGraphAnalyzer::dijkstra( graph.get(), startVertexIdx, 0, &resultTree, &resultCost );
393 point_0_0_idx = graph->findVertex( QgsPointXY( 0, 0 ) );
394 QVERIFY( point_0_0_idx != -1 );
395 point_10_0_idx = graph->findVertex( QgsPointXY( 10, 0 ) );
396 QVERIFY( point_10_0_idx != -1 );
397 point_10_10_idx = graph->findVertex( QgsPointXY( 10, 10 ) );
398 QVERIFY( point_10_10_idx != -1 );
399 point_10_20_idx = graph->findVertex( QgsPointXY( 10, 20 ) );
400 QVERIFY( point_10_20_idx != -1 );
401 point_20_10_idx = graph->findVertex( QgsPointXY( 20, 10 ) );
402 QVERIFY( point_20_10_idx != -1 );
403 int point_20_n10_idx = graph->findVertex( QgsPointXY( 20, -10 ) );
404 QVERIFY( point_20_n10_idx != -1 );
405
406 QCOMPARE( resultTree.at( startVertexIdx ), -1 );
407 QCOMPARE( resultCost.at( startVertexIdx ), 0.0 );
408 QVERIFY( resultTree.at( point_10_0_idx ) != -1 );
409 QCOMPARE( resultCost.at( point_10_0_idx ), 1.0 );
410 QCOMPARE( graph->edge( resultTree.at( point_10_0_idx ) ).fromVertex(), startVertexIdx );
411 QCOMPARE( graph->edge( resultTree.at( point_10_0_idx ) ).toVertex(), point_10_0_idx );
412 QVERIFY( resultTree.at( point_10_10_idx ) != -1 );
413 QCOMPARE( resultCost.at( point_10_10_idx ), 2.0 );
414 QCOMPARE( graph->edge( resultTree.at( point_10_10_idx ) ).fromVertex(), point_10_0_idx );
415 QCOMPARE( graph->edge( resultTree.at( point_10_10_idx ) ).toVertex(), point_10_10_idx );
416 QCOMPARE( resultTree.at( point_10_20_idx ), -1 ); // unreachable
417 QVERIFY( resultTree.at( point_20_10_idx ) != -1 );
418 QCOMPARE( resultCost.at( point_20_10_idx ), 4.0 );
419 QCOMPARE( graph->edge( resultTree.at( point_20_10_idx ) ).fromVertex(), point_10_10_idx );
420 QCOMPARE( graph->edge( resultTree.at( point_20_10_idx ) ).toVertex(), point_20_10_idx );
421 QCOMPARE( resultTree.at( point_20_n10_idx ), -1 ); // unreachable
422
423 // backward direction
424 director = std::make_unique< QgsVectorLayerDirector > ( network.get(),
425 -1, QString(), QString(), QString(), QgsVectorLayerDirector::DirectionBackward );
426 strategy = std::make_unique< TestNetworkStrategy >();
427 director->addStrategy( strategy.release() );
428 builder = std::make_unique< QgsGraphBuilder > ( network->sourceCrs(), true, 0 );
429 director->makeGraph( builder.get(), QVector<QgsPointXY>(), snapped );
430 graph.reset( builder->takeGraph() );
431 startVertexIdx = graph->findVertex( QgsPointXY( 10, 10 ) );
432 QVERIFY( startVertexIdx != -1 );
433 resultTree.clear();
434 resultCost.clear();
435 QgsGraphAnalyzer::dijkstra( graph.get(), startVertexIdx, 0, &resultTree, &resultCost );
436 point_0_0_idx = graph->findVertex( QgsPointXY( 0, 0 ) );
437 QVERIFY( point_0_0_idx != -1 );
438 point_10_0_idx = graph->findVertex( QgsPointXY( 10, 0 ) );
439 QVERIFY( point_10_0_idx != -1 );
440 point_10_10_idx = graph->findVertex( QgsPointXY( 10, 10 ) );
441 QVERIFY( point_10_10_idx != -1 );
442 point_10_20_idx = graph->findVertex( QgsPointXY( 10, 20 ) );
443 QVERIFY( point_10_20_idx != -1 );
444 point_20_10_idx = graph->findVertex( QgsPointXY( 20, 10 ) );
445 QVERIFY( point_20_10_idx != -1 );
446 point_20_n10_idx = graph->findVertex( QgsPointXY( 20, -10 ) );
447 QVERIFY( point_20_n10_idx != -1 );
448
449 QCOMPARE( resultTree.at( startVertexIdx ), -1 );
450 QCOMPARE( resultCost.at( startVertexIdx ), 0.0 );
451 QCOMPARE( resultTree.at( point_20_10_idx ), -1 );
452 QCOMPARE( resultTree.at( point_20_n10_idx ), -1 );
453 QVERIFY( resultTree.at( point_10_20_idx ) != -1 );
454 QCOMPARE( resultCost.at( point_10_20_idx ), 3.0 );
455 QCOMPARE( graph->edge( resultTree.at( point_10_20_idx ) ).fromVertex(), startVertexIdx );
456 QCOMPARE( graph->edge( resultTree.at( point_10_20_idx ) ).toVertex(), point_10_20_idx );
457 QVERIFY( resultTree.at( point_10_0_idx ) != -1 );
458 QCOMPARE( resultCost.at( point_10_0_idx ), 1.0 );
459 QCOMPARE( graph->edge( resultTree.at( point_10_0_idx ) ).fromVertex(), startVertexIdx );
460 QCOMPARE( graph->edge( resultTree.at( point_10_0_idx ) ).toVertex(), point_10_0_idx );
461 QVERIFY( resultTree.at( point_0_0_idx ) != -1 );
462 QCOMPARE( resultCost.at( point_0_0_idx ), 2.0 );
463 QCOMPARE( graph->edge( resultTree.at( point_0_0_idx ) ).fromVertex(), point_10_0_idx );
464 QCOMPARE( graph->edge( resultTree.at( point_0_0_idx ) ).toVertex(), point_0_0_idx );
465 }
466
testRouteFail()467 void TestQgsNetworkAnalysis::testRouteFail()
468 {
469 std::unique_ptr< QgsVectorLayer > network = std::make_unique< QgsVectorLayer >( QStringLiteral( "LineString?crs=epsg:28355&field=cost:int" ), QStringLiteral( "x" ), QStringLiteral( "memory" ) );
470
471 const QStringList lines = QStringList() << QStringLiteral( "LineString (302081.71116495534079149 5753475.15082756895571947, 302140.54234686412382871 5753417.70564490929245949, 302143.24717211339157075 5753412.57312887348234653, 302143.17789465241366997 5753406.77192200440913439, 302140.35127420048229396 5753401.70546196680516005, 302078.46200818457873538 5753338.31098813004791737, 302038.17299743194598705 5753309.50200006738305092)" )
472 << QStringLiteral( "LineString (302081.70763194985920563 5753475.1403581602498889, 301978.24500802176771685 5753368.03299263771623373)" )
473 << QStringLiteral( "LineString (302181.69117977644782513 5753576.27856593858450651, 302081.71834095334634185 5753475.14562766999006271)" );
474 QgsFeatureList flist;
475 for ( const QString &line : lines )
476 {
477 QgsFeature ff( 0 );
478 const QgsGeometry refGeom = QgsGeometry::fromWkt( line );
479 ff.setGeometry( refGeom );
480 ff.setAttributes( QgsAttributes() << 1 );
481 flist << ff;
482 }
483 network->dataProvider()->addFeatures( flist );
484
485 // build graph
486 std::unique_ptr< QgsVectorLayerDirector > director = std::make_unique< QgsVectorLayerDirector > ( network.get(),
487 -1, QString(), QString(), QString(), QgsVectorLayerDirector::DirectionBoth );
488 std::unique_ptr< QgsNetworkStrategy > strategy = std::make_unique< TestNetworkStrategy >();
489 director->addStrategy( strategy.release() );
490 std::unique_ptr< QgsGraphBuilder > builder = std::make_unique< QgsGraphBuilder > ( network->sourceCrs(), true, 1 );
491
492 const QgsPointXY start( 302131.1053754404, 5753392.757948928 );
493 const QgsPointXY end( 302148.1636281528, 5753541.408436851 );
494
495 QVector<QgsPointXY > snapped;
496 director->makeGraph( builder.get(), QVector<QgsPointXY>() << start << end, snapped );
497 std::unique_ptr< QgsGraph > graph( builder->takeGraph() );
498
499 const QgsPointXY snappedStart = snapped.at( 0 );
500 QGSCOMPARENEAR( snappedStart.x(), 302131.3, 0.1 );
501 QGSCOMPARENEAR( snappedStart.y(), 5753392.5, 0.1 );
502 const int startVertexIdx = graph->findVertex( snappedStart );
503 QVERIFY( startVertexIdx != -1 );
504 const QgsPointXY snappedEnd = snapped.at( 1 );
505 QGSCOMPARENEAR( snappedEnd.x(), 302147.68, 0.1 );
506 QGSCOMPARENEAR( snappedEnd.y(), 5753541.88, 0.1 );
507 const int endVertexIdx = graph->findVertex( snappedEnd );
508 QVERIFY( endVertexIdx != -1 );
509
510 // both directions
511 QVector<int> resultTree;
512 QVector<double> resultCost;
513 QgsGraphAnalyzer::dijkstra( graph.get(), startVertexIdx, 0, &resultTree, &resultCost );
514
515 QCOMPARE( resultTree.at( startVertexIdx ), -1 );
516 QCOMPARE( resultCost.at( startVertexIdx ), 0.0 );
517 QVERIFY( resultTree.at( endVertexIdx ) != -1 );
518 QCOMPARE( resultCost.at( endVertexIdx ), 6.0 );
519 }
520
testRouteFail2()521 void TestQgsNetworkAnalysis::testRouteFail2()
522 {
523 std::unique_ptr< QgsVectorLayer > network = std::make_unique< QgsVectorLayer >( QStringLiteral( "LineString?crs=epsg:4326&field=cost:double" ), QStringLiteral( "x" ), QStringLiteral( "memory" ) );
524
525 const QStringList lines = QStringList() << QStringLiteral( "LineString (11.25044997999680874 48.42605439713970128, 11.25044693759680925 48.42603339773970106, 11.25044760759680962 48.42591690773969759, 11.25052289759680946 48.42589190773969676)" )
526 << QStringLiteral( "LineString (11.25052289759680946 48.42589190773969676, 11.25050350759680917 48.42586202773969717, 11.25047190759680937 48.42581754773969749, 11.2504146475968092 48.42573849773970096, 11.25038716759680923 48.42569834773969717, 11.2502920175968093 48.42557470773969897, 11.25019984759680902 48.42560406773969817, 11.25020393759680992 48.42571203773970012, 11.2502482875968095 48.42577478773969801, 11.25021922759680848 48.42578442773969982)" )
527 << QStringLiteral( "LineString (11.2504146475968092 48.42573849773970096, 11.25048389759681022 48.42572031773969599, 11.25051325759680942 48.42570672773970131)" )
528 << QStringLiteral( "LineString (11.25038716759680923 48.42569834773969717, 11.25055288759680927 48.42564748773969541, 11.25052296759680992 48.42560921773969795)" );
529 QgsFeatureList flist;
530 int i = 0;
531 for ( const QString &line : lines )
532 {
533 QgsFeature ff( 0 );
534 const QgsGeometry refGeom = QgsGeometry::fromWkt( line );
535 ff.setGeometry( refGeom );
536 ff.setAttributes( QgsAttributes() << 1 + 0.001 * i );
537 i++;
538 flist << ff;
539 }
540 network->dataProvider()->addFeatures( flist );
541
542 // build graph
543 std::unique_ptr< QgsVectorLayerDirector > director = std::make_unique< QgsVectorLayerDirector > ( network.get(),
544 -1, QString(), QString(), QString(), QgsVectorLayerDirector::DirectionBoth );
545 std::unique_ptr< QgsNetworkStrategy > strategy = std::make_unique< TestNetworkStrategy >();
546 director->addStrategy( strategy.release() );
547 std::unique_ptr< QgsGraphBuilder > builder = std::make_unique< QgsGraphBuilder > ( network->sourceCrs(), true, 0 );
548
549 const QgsPointXY start( 11.250443581846053, 48.42605665308498 );
550 const QgsPointXY end( 11.250525546822013, 48.42561343506683 );
551
552 QVector<QgsPointXY > snapped;
553 director->makeGraph( builder.get(), QVector<QgsPointXY>() << start << end, snapped );
554 std::unique_ptr< QgsGraph > graph( builder->takeGraph() );
555
556 const QgsPointXY snappedStart = snapped.at( 0 );
557 QGSCOMPARENEAR( snappedStart.x(), 11.250450, 0.000001 );
558 QGSCOMPARENEAR( snappedStart.y(), 48.426054, 0.000001 );
559 const int startVertexIdx = graph->findVertex( snappedStart );
560 QVERIFY( startVertexIdx != -1 );
561 const QgsPointXY snappedEnd = snapped.at( 1 );
562 QGSCOMPARENEAR( snappedEnd.x(), 11.250526, 0.000001 );
563 QGSCOMPARENEAR( snappedEnd.y(), 48.425613, 0.000001 );
564 const int endVertexIdx = graph->findVertex( snappedEnd );
565 QVERIFY( endVertexIdx != -1 );
566
567 // both directions
568 QVector<int> resultTree;
569 QVector<double> resultCost;
570 QgsGraphAnalyzer::dijkstra( graph.get(), startVertexIdx, 0, &resultTree, &resultCost );
571
572 QCOMPARE( resultTree.at( startVertexIdx ), -1 );
573 QCOMPARE( resultCost.at( startVertexIdx ), 0.0 );
574 QVERIFY( resultTree.at( endVertexIdx ) != -1 );
575 QCOMPARE( resultCost.at( endVertexIdx ), 9.01 );
576 }
577
578
579
580 QGSTEST_MAIN( TestQgsNetworkAnalysis )
581 #include "testqgsnetworkanalysis.moc"
582