Fix QgsGraphAnalyzer::dijkstra traverses through edges backwards

This means that it flips the direction of the graph edge, breaking route restrictions. Refs #17325
qgis · Oct 31, 2017 · 8d32bf7 · 8d32bf7
1 parent 57edec6
commit 8d32bf7
Show file tree

Hide file tree

Showing 7 changed files with 286 additions and 86 deletions.
diff --git a/python/plugins/processing/algs/qgis/ShortestPathLayerToPoint.py b/python/plugins/processing/algs/qgis/ShortestPathLayerToPoint.py
@@ -250,7 +250,7 @@ def processAlgorithm(self, parameters, context, feedback):
 
             idxStart = graph.findVertex(snappedPoints[i])
 
-            tree, cost = QgsGraphAnalyzer.dijkstra(graph, idxStart, 0)
+            tree, costs = QgsGraphAnalyzer.dijkstra(graph, idxStart, 0)
 
             if tree[idxEnd] == -1:
                 msg = self.tr('There is no route from start point ({}) to end point ({}).'.format(points[i].toString(), endPoint.toString()))
@@ -266,9 +266,9 @@ def processAlgorithm(self, parameters, context, feedback):
             cost = 0.0
             current = idxEnd
             while current != idxStart:
-                cost += graph.edge(tree[current]).cost(0)
-                route.append(graph.vertex(graph.edge(tree[current]).fromVertex()).point())
-                current = graph.edge(tree[current]).toVertex()
+                cost += costs[current]
+                current = graph.edge(tree[current]).fromVertex()
+                route.append(graph.vertex(current).point())
 
             route.append(snappedPoints[i])
             route.reverse()

diff --git a/python/plugins/processing/algs/qgis/ShortestPathPointToLayer.py b/python/plugins/processing/algs/qgis/ShortestPathPointToLayer.py
@@ -241,8 +241,7 @@ def processAlgorithm(self, parameters, context, feedback):
         graph = builder.graph()
 
         idxStart = graph.findVertex(snappedPoints[0])
-        tree, cost = QgsGraphAnalyzer.dijkstra(graph, idxStart, 0)
-        route = []
+        tree, costs = QgsGraphAnalyzer.dijkstra(graph, idxStart, 0)
 
         nPoints = len(snappedPoints)
         total = 100.0 / nPoints if nPoints else 1
@@ -266,9 +265,9 @@ def processAlgorithm(self, parameters, context, feedback):
             cost = 0.0
             current = idxEnd
             while current != idxStart:
-                cost += graph.edge(tree[current]).cost(0)
-                route.append(graph.vertex(graph.edge(tree[current]).fromVertex()).point())
-                current = graph.edge(tree[current]).toVertex()
+                cost += costs[current]
+                current = graph.edge(tree[current]).fromVertex()
+                route.append(graph.vertex(current).point())
 
             route.append(snappedPoints[0])
             route.reverse()

diff --git a/python/plugins/processing/algs/qgis/ShortestPathPointToPoint.py b/python/plugins/processing/algs/qgis/ShortestPathPointToPoint.py
@@ -217,7 +217,7 @@ def processAlgorithm(self, parameters, context, feedback):
         idxStart = graph.findVertex(snappedPoints[0])
         idxEnd = graph.findVertex(snappedPoints[1])
 
-        tree, cost = QgsGraphAnalyzer.dijkstra(graph, idxStart, 0)
+        tree, costs = QgsGraphAnalyzer.dijkstra(graph, idxStart, 0)
         if tree[idxEnd] == -1:
             raise QgsProcessingException(
                 self.tr('There is no route from start point to end point.'))
@@ -226,9 +226,9 @@ def processAlgorithm(self, parameters, context, feedback):
         cost = 0.0
         current = idxEnd
         while current != idxStart:
-            cost += graph.edge(tree[current]).cost(0)
-            route.append(graph.vertex(graph.edge(tree[current]).fromVertex()).point())
-            current = graph.edge(tree[current]).toVertex()
+            cost += costs[current]
+            current = graph.edge(tree[current]).fromVertex()
+            route.append(graph.vertex(current).point())
 
         route.append(snappedPoints[0])
         route.reverse()

diff --git a/src/analysis/network/qgsgraphanalyzer.cpp b/src/analysis/network/qgsgraphanalyzer.cpp
@@ -59,21 +59,20 @@ void QgsGraphAnalyzer::dijkstra( const QgsGraph *source, int startPointIdx, int
     not_begin.erase( it );
 
     // edge index list
-    QgsGraphEdgeIds l = source->vertex( curVertex ).incomingEdges();
-    QgsGraphEdgeIds::iterator arcIt;
-    for ( arcIt = l.begin(); arcIt != l.end(); ++arcIt )
+    const QgsGraphEdgeIds &outgoingEdges = source->vertex( curVertex ).outgoingEdges();
+    for ( int edgeId : outgoingEdges )
     {
-      const QgsGraphEdge arc = source->edge( *arcIt );
+      const QgsGraphEdge &arc = source->edge( edgeId );
       double cost = arc.cost( criterionNum ).toDouble() + curCost;
 
-      if ( cost < ( *result )[ arc.fromVertex()] )
+      if ( cost < ( *result )[ arc.toVertex()] )
       {
-        ( *result )[ arc.fromVertex()] = cost;
+        ( *result )[ arc.toVertex()] = cost;
         if ( resultTree )
         {
-          ( *resultTree )[ arc.fromVertex()] = *arcIt;
+          ( *resultTree )[ arc.toVertex()] = edgeId;
         }
-        not_begin.insert( cost, arc.fromVertex() );
+        not_begin.insert( cost, arc.toVertex() );
       }
     }
   }

diff --git a/src/analysis/network/qgsgraphbuilder.cpp b/src/analysis/network/qgsgraphbuilder.cpp
@@ -42,7 +42,7 @@ void QgsGraphBuilder::addVertex( int, const QgsPointXY &pt )
 
 void QgsGraphBuilder::addEdge( int pt1id, const QgsPointXY &, int pt2id, const QgsPointXY &, const QVector< QVariant > &prop )
 {
-  mGraph->addEdge( pt2id, pt1id, prop );
+  mGraph->addEdge( pt1id, pt2id, prop );
 }
 
 QgsGraph *QgsGraphBuilder::graph()

diff --git a/src/analysis/network/qgsvectorlayerdirector.cpp b/src/analysis/network/qgsvectorlayerdirector.cpp
@@ -39,12 +39,14 @@ using namespace SpatialIndex;
 struct TiePointInfo
 {
   TiePointInfo() = default;
-  TiePointInfo( QgsFeatureId featureId, const QgsPointXY &start, const QgsPointXY &end )
-    : mNetworkFeatureId( featureId )
+  TiePointInfo( int additionalPointId, QgsFeatureId featureId, const QgsPointXY &start, const QgsPointXY &end )
+    : additionalPointId( additionalPointId )
+    , mNetworkFeatureId( featureId )
     , mFirstPoint( start )
     , mLastPoint( end )
   {}
 
+  int additionalPointId = -1;
   QgsPointXY mTiedPoint;
   double mLength = DBL_MAX;
   QgsFeatureId mNetworkFeatureId = -1;
@@ -255,7 +257,7 @@ void QgsVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, const
             if ( thisSegmentClosestDist < additionalTiePoints[ i ].mLength )
             {
               // found a closer segment for this additional point
-              TiePointInfo info( feature.id(), pt1, pt2 );
+              TiePointInfo info( i, feature.id(), pt1, pt2 );
               info.mLength = thisSegmentClosestDist;
               info.mTiedPoint = snappedPoint;
 
@@ -300,8 +302,11 @@ void QgsVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, const
       snappedPoints[ i ] = graphVertices.at( ptIdx );
     }
   }
-
   // also need to update tie points - they need to be matched for snapped points
+  for ( int i = 0; i < additionalTiePoints.count(); ++i )
+  {
+    additionalTiePoints[ i ].mTiedPoint = snappedPoints.at( additionalTiePoints.at( i ).additionalPointId );
+  }
 
 
   // begin graph construction
@@ -361,9 +366,9 @@ void QgsVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, const
           int pt1idx = -1;
           int pt2idx = -1;
           bool isFirstPoint = true;
-          for ( const QgsPointXY &arcPoint : qgis::as_const( pointsOnArc ) )
+          for ( auto arcPointIt = pointsOnArc.constBegin(); arcPointIt != pointsOnArc.constEnd(); ++arcPointIt )
           {
-            pt2 = arcPoint;
+            pt2 = arcPointIt.value();
 
             pt2idx = findPointWithinTolerance( pt2 );
             Q_ASSERT_X( pt2idx >= 0, "QgsVectorLayerDirectory::makeGraph", "encountered a vertex which was not present in graph" );
@@ -372,10 +377,9 @@ void QgsVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, const
             {
               double distance = builder->distanceArea()->measureLine( pt1, pt2 );
               QVector< QVariant > prop;
-              QList< QgsNetworkStrategy * >::const_iterator it;
-              for ( it = mStrategies.begin(); it != mStrategies.end(); ++it )
+              for ( QgsNetworkStrategy *strategy : mStrategies )
               {
-                prop.push_back( ( *it )->cost( distance, feature ) );
+                prop.push_back( strategy->cost( distance, feature ) );
               }
 
               if ( direction == Direction::DirectionForward ||