Store graph vertices/edges in a hash, so that index gaps can

exist in the vertices/edges without issues
qgis · Nov 9, 2021 · d2c997c · d2c997c
1 parent 4181ad4
commit d2c997c
Show file tree

Hide file tree

Showing 2 changed files with 24 additions and 8 deletions.
diff --git a/src/analysis/network/qgsgraph.cpp b/src/analysis/network/qgsgraph.cpp
@@ -22,8 +22,8 @@
 
 int QgsGraph::addVertex( const QgsPointXY &pt )
 {
-  mGraphVertices.append( QgsGraphVertex( pt ) );
-  return mGraphVertices.size() - 1;
+  mGraphVertices[ mNextVertexId ] = QgsGraphVertex( pt );
+  return mNextVertexId++;
 }
 
 int QgsGraph::addEdge( int fromVertexIdx, int toVertexIdx, const QVector< QVariant > &strategies )
@@ -33,23 +33,30 @@ int QgsGraph::addEdge( int fromVertexIdx, int toVertexIdx, const QVector< QVaria
   e.mStrategies = strategies;
   e.mToIdx = toVertexIdx;
   e.mFromIdx  = fromVertexIdx;
-  mGraphEdges.push_back( e );
+
+  mGraphEdges[ mNextEdgeId ] = e;
   const int edgeIdx = mGraphEdges.size() - 1;
 
   mGraphVertices[ toVertexIdx ].mIncomingEdges.push_back( edgeIdx );
   mGraphVertices[ fromVertexIdx ].mOutgoingEdges.push_back( edgeIdx );
 
-  return mGraphEdges.size() - 1;
+  return mNextEdgeId++;
 }
 
 const QgsGraphVertex &QgsGraph::vertex( int idx ) const
 {
-  return mGraphVertices[ idx ];
+  auto it = mGraphVertices.constFind( idx );
+  if ( it != mGraphVertices.constEnd() )
+    return ( it ).value();
+  Q_ASSERT_X( false, "QgsGraph::vertex()", "Invalid vertex ID" );
 }
 
 const QgsGraphEdge &QgsGraph::edge( int idx ) const
 {
-  return mGraphEdges[ idx ];
+  auto it = mGraphEdges.constFind( idx );
+  if ( it != mGraphEdges.constEnd() )
+    return ( it ).value();
+  Q_ASSERT_X( false, "QgsGraph::edge()", "Invalid edge ID" );
 }
 
 int QgsGraph::vertexCount() const

diff --git a/src/analysis/network/qgsgraph.h b/src/analysis/network/qgsgraph.h
@@ -186,10 +186,19 @@ class ANALYSIS_EXPORT QgsGraph
      */
     int findVertex( const QgsPointXY &pt ) const;
 
+  protected:
+#ifndef SIP_RUN
+    //! Graph vertices
+    QHash<int, QgsGraphVertex> mGraphVertices;
+
+    //! Graph edges
+    QHash<int, QgsGraphEdge> mGraphEdges;
+#endif
+
   private:
-    QVector<QgsGraphVertex> mGraphVertices;
 
-    QVector<QgsGraphEdge> mGraphEdges;
+    int mNextVertexId = 0;
+    int mNextEdgeId = 0;
 };
 
 #endif // QGSGRAPH_H