add qgsgraphanalyzer.*

qgis · May 25, 2011 · 8560e4d · 8560e4d
1 parent b7946b4
commit 8560e4d
Show file tree

Hide file tree

Showing 3 changed files with 153 additions and 1 deletion.
diff --git a/src/analysis/network/CMakeLists.txt b/src/analysis/network/CMakeLists.txt
@@ -8,11 +8,13 @@ SET(QGIS_NETWORK_ANALYSIS_SRCS
   qgsgraphbuilder.cpp
   qgsdistanceedgeproperter.cpp
   qgslinevectorlayerdirector.cpp
+  qgsgraphanalyzer.cpp
 )
 
 INCLUDE_DIRECTORIES(BEFORE raster)
 
 SET(QGIS_ANALYSIS_MOC_HDRS
+  qgslinevectorlayerdirector.cpp
 )
 
 QT4_WRAP_CPP(QGIS_NETWORK_ANALYSIS_MOC_SRCS ${QGIS_ANALYSIS_MOC_HDRS})
@@ -58,7 +60,8 @@ SET(QGIS_NETWORK_ANALYSIS_HDRS
   qgsedgeproperter.h 
   qgsdistanceedgeproperter.h 
   qgsgraphdirector.h 
-  qgslinevectorlayerdirector.h )
+  qgslinevectorlayerdirector.h 
+  qgsgraphanalyzer.h )
 
 INSTALL(CODE "MESSAGE(\"Installing NETWORK ANALYSIS headers...\")")
 INSTALL(FILES ${QGIS_NETWORK_ANALYSIS_HDRS} ${QGIS_NETWORK_ANALYSIS_MOC_HDRS} DESTINATION ${QGIS_INCLUDE_DIR}) 
diff --git a/src/analysis/network/qgsgraphanalyzer.cpp b/src/analysis/network/qgsgraphanalyzer.cpp
@@ -0,0 +1,103 @@
+/***************************************************************************
+    qgsgraphanlyzer.cpp - QGIS Tools for graph analysis
+                             -------------------
+    begin                : 14 april 2011
+    copyright            : (C) Sergey Yakushev
+    email                : Yakushevs@list.ru
+ ***************************************************************************/
+
+/***************************************************************************
+ *                                                                         *
+ *   This program is free software; you can redistribute it and/or modify  *
+ *   it under the terms of the GNU General Public License as published by  *
+ *   the Free Software Foundation; either version 2 of the License, or     *
+ *   (at your option) any later version.                                   *
+ *                                                                         *
+ ***************************************************************************/
+// C++ standart includes
+#include <limits>
+
+// QT includes
+#include <QMap>
+#include <QVector>
+#include <QPair>
+
+//QGIS-uncludes
+#include "qgsgraph.h"
+#include "qgsgraphanalyzer.h"
+
+void QgsGraphAnalyzer::shortestpath( const QgsGraph* source, int startPointIdx, int criterionNum, const QVector<int>& destPointCost, QVector<double>& cost, QgsGraph* treeResult )
+{
+
+  // QMap< cost, vertexIdx > not_begin
+  // I use it and not create any struct or class.
+  QMap< double, int > not_begin;  
+  QMap< double, int >::iterator it;
+
+  // QVector< QPair< cost, edge id > result
+  QVector< QPair< double, int > > result;
+
+  result.reserve( source->vertexCount() );
+  int i;
+  for ( i=0; i < source->vertexCount(); ++i )
+  {
+    result.push_back( QPair<double, int> ( std::numeric_limits<double>::infinity() , i ) );
+  }
+  result.push_back ( QPair<double, int>( 0.0, -1 ) );
+
+  not_begin.insert( 0.0, startPointIdx );
+
+  // begin Dijkstra algorithm
+  while ( !not_begin.empty() )
+  {
+    it = not_begin.begin();
+    double curCost = it.key();
+    int curVertex = it.value();
+    not_begin.erase( it );
+
+    QgsGraphEdgeList l = source->vertex( curVertex ).outEdges();
+    QgsGraphEdgeList::iterator edgeIt;
+    for (edgeIt = l.begin(); edgeIt != l.end(); ++edgeIt)
+    {
+      const QgsGraphEdge& edge = source->edge( *edgeIt );
+      double cost = edge.property( criterionNum ).toDouble() + curCost;
+
+      if ( cost < result[ edge.in() ].first )
+      {
+        result[ edge.in() ] = QPair< double, int >( cost, *edgeIt );
+        not_begin.insert( cost, edge.in() );
+      }
+    }
+  }
+
+  // fill shortestpath tree
+  if ( treeResult != NULL )
+  {
+    // sourceVertexIdx2resultVertexIdx
+    QVector<int> source2result( result.size(), -1 );
+
+    for ( i=0; i < source->vertexCount(); ++i )
+    {
+      if ( result[ i ].first < std::numeric_limits<double>::infinity() )
+      {
+        source2result[ i ] = treeResult->addVertex( source->vertex(i).point() );
+      }
+    }
+    for ( i=0; i < source->vertexCount(); ++i )
+    {
+      if ( result[ i ].first < std::numeric_limits<double>::infinity() && result[i].second != -1)
+      {  
+        const QgsGraphEdge& edge = source->edge( result[i].second );
+
+        treeResult->addEdge( source2result[ edge.out() ], source2result[ i ], 
+            edge.properties() );
+      }
+    }
+  }
+
+  // fill shortestpath's costs
+  for ( i=0; i < destPointCost.size(); ++i )
+  {
+    cost[i] = result[ destPointCost[i] ].first;
+  }
+}
diff --git a/src/analysis/network/qgsgraphanalyzer.h b/src/analysis/network/qgsgraphanalyzer.h
@@ -0,0 +1,46 @@
+/***************************************************************************
+    qgsgraphalyzer.h - QGIS Tools for vector geometry analysis
+                             -------------------
+    begin                : 14 april 2010
+    copyright            : (C) Sergey Yakushev
+    email                : yakushevs@list.ru
+ ***************************************************************************/
+
+/***************************************************************************
+ *                                                                         *
+ *   This program is free software; you can redistribute it and/or modify  *
+ *   it under the terms of the GNU General Public License as published by  *
+ *   the Free Software Foundation; either version 2 of the License, or     *
+ *   (at your option) any later version.                                   *
+ *                                                                         *
+ ***************************************************************************/
+
+#ifndef QGSGRAPHANALYZERH
+#define QGSGRAPHANALYZERH
+
+//QT-includes
+#include <QVector>
+
+// forward-declaration
+class QgsGraph;
+
+/** \ingroup analysis
+ * The QGis class provides graph analysis functions
+ */
+
+class QgsGraphAnalyzer
+{
+  public:
+    /**
+     * solve shortest path problem using dijkstra algorithm
+     * @param source The source graph
+     * @param startVertexIdx index of start vertex
+     * @param criterionNum index of edge property as optimization criterion
+     * @param destPointCost array of vertex indexes. Function calculating shortest path costs for vertices with these indexes
+     * @param cost array of cost paths
+     * @param treeResult return shortest path tree
+     */
+    static void shortestpath( const QgsGraph* source, int startVertexIdx, int criterionNum, const QVector<int>& destPointCost, QVector<double>& cost, QgsGraph* treeResult );
+
+};
+#endif //QGSGRAPHANALYZERH