RoadGraph: add dijkstra method to Network analysis library, remove un…

…used shortestpath, update python bindings
qgis · Jan 17, 2012 · 35cd0b9 · 35cd0b9
1 parent 86ce859
commit 35cd0b9
Show file tree

Hide file tree

Showing 5 changed files with 126 additions and 87 deletions.
diff --git a/python/analysis/network/qgsgraphanalyzer.sip b/python/analysis/network/qgsgraphanalyzer.sip
@@ -3,18 +3,45 @@ class QgsGraphAnalyzer
 %TypeHeaderCode
 #include <qgsgraphanalyzer.h>
 %End
-
+  
   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
+     * @param criterionNum index of arc property as optimization criterion
+     * @param treeResult array represents the shortest path tree. resultTree[ vertexIndex ] == inboundingArcIndex if vertex reacheble and resultTree[ vertexIndex ] == -1 others.
+     * @param resultCost array of cost paths
      */
-//    static void shortestpath( const QgsGraph* source, int startVertexIdx, int criterionNum, const QVector<int>& destPointCost, QVector<double>& cost, QgsGraph* treeResult );
+    static SIP_PYLIST dijkstra( const QgsGraph* source, int startVertexIdx, int criterionNum );
+%MethodCode
+      QVector< int > treeResult;
+      QVector< double > costResult;
+      QgsGraphAnalyzer::dijkstra( a0, a1, a2, &treeResult, &costResult );      
+
+      PyObject *l1 = PyList_New( treeResult.size() );
+      if ( l1 == NULL )
+      {
+        return NULL;
+      }
+      PyObject *l2 = PyList_New( costResult.size() );
+      if ( l2 == NULL )
+      {
+        return NULL;
+      }
+      int i;
+      for ( i = 0; i < costResult.size(); ++i )
+      { 
+        PyObject *Int = PyInt_FromLong( treeResult[i] );
+        PyList_SET_ITEM( l1, i, Int );
+        PyObject *Float = PyFloat_FromDouble( costResult[i] );
+        PyList_SET_ITEM( l2, i, Float ); 
+      }
+
+      sipRes = PyTuple_New( 2 );
+      PyTuple_SET_ITEM( sipRes, 0, l1 );
+      PyTuple_SET_ITEM( sipRes, 1, l2 );
+%End
 
     /**
      * return shortest path tree with root-node in startVertexIdx
@@ -25,3 +52,4 @@ class QgsGraphAnalyzer
     static QgsGraph* shortestTree( const QgsGraph* source, int startVertexIdx, int criterionNum );
 };
 
+
diff --git a/src/analysis/network/qgsgraphanalyzer.cpp b/src/analysis/network/qgsgraphanalyzer.cpp
@@ -26,28 +26,35 @@
 #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 )
+void QgsGraphAnalyzer::dijkstra( const QgsGraph* source, int startPointIdx, int criterionNum, QVector<int>* resultTree, QVector<double>* resultCost )
 {
+  QVector< double > * result = NULL;
+  if ( resultCost != NULL )
+  {
+    result = resultCost;
+  }
+  else
+  {
+    result = new QVector<double>();
+  }
+
+  result->clear();
+  result->insert( result->begin(), source->vertexCount(), std::numeric_limits<double>::infinity() );
+  ( *result )[ startPointIdx ] = 0.0;
+
+  if ( resultTree != NULL )
+  {
+    resultTree->clear();
+    resultTree->insert( resultTree->begin(), source->vertexCount(), -1 );
+  }
 
   // QMultiMap< cost, vertexIdx > not_begin
   // I use it and not create any struct or class.
   QMultiMap< double, int > not_begin;
   QMultiMap< double, int >::iterator it;
 
-  // QVector< QPair< cost, arc 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[ startPointIdx ] = QPair<double, int> ( 0.0, -1 );
-
   not_begin.insert( 0.0, startPointIdx );
 
-  // begin Dijkstra algorithm
   while ( !not_begin.empty() )
   {
     it = not_begin.begin();
@@ -60,55 +67,58 @@ void QgsGraphAnalyzer::shortestpath( const QgsGraph* source, int startPointIdx,
     QgsGraphArcIdList::iterator arcIt;
     for ( arcIt = l.begin(); arcIt != l.end(); ++arcIt )
     {
-      const QgsGraphArc& arc = source->arc( *arcIt );
+      const QgsGraphArc arc = source->arc( *arcIt );
       double cost = arc.property( criterionNum ).toDouble() + curCost;
 
-      if ( cost < result[ arc.inVertex()].first )
+      if ( cost < ( *result )[ arc.inVertex()] )
       {
-        result[ arc.inVertex()] = QPair< double, int >( cost, *arcIt );
+        ( *result )[ arc.inVertex()] = cost;
+        if ( resultTree != NULL )
+        {
+          ( *resultTree )[ arc.inVertex()] = *arcIt;
+        }
         not_begin.insert( cost, arc.inVertex() );
       }
     }
   }
-
-  // fill shortestpath tree
-  if ( treeResult != NULL )
+  if ( resultCost == NULL )
   {
-    // sourceVertexIdx2resultVertexIdx
-    QVector<int> source2result( result.size(), -1 );
+    delete result;
+  }
+}
 
-    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 QgsGraphArc& arc = source->arc( result[i].second );
+QgsGraph* QgsGraphAnalyzer::shortestTree( const QgsGraph* source, int startVertexIdx, int criterionNum )
+{
+  QgsGraph *treeResult = new QgsGraph();
+  QVector<int> tree;
 
-        treeResult->addArc( source2result[ arc.outVertex()], source2result[ i ],
-                            arc.properties() );
-      }
+  QgsGraphAnalyzer::dijkstra( source, startVertexIdx, criterionNum, &tree );
+
+  // sourceVertexIdx2resultVertexIdx
+  QVector<int> source2result( tree.size(), -1 );
+
+  // Add reachable vertices to the result
+  source2result[ startVertexIdx ] = treeResult->addVertex( source->vertex( startVertexIdx ).point() );
+  int i = 0;
+  for ( i = 0; i < source->vertexCount(); ++i )
+  {
+    if ( tree[ i ] != -1 )
+    {
+      source2result[ i ] = treeResult->addVertex( source->vertex( i ).point() );
     }
   }
 
-  // fill shortestpath's costs
-  for ( i = 0; i < destPointCost.size(); ++i )
+  // Add arcs to result
+  for ( i = 0; i < source->vertexCount(); ++i )
   {
-    cost[i] = result[ destPointCost[i] ].first;
-  }
-}
+    if ( tree[ i ] != -1 )
+    {
+      const QgsGraphArc& arc = source->arc( tree[i] );
 
-QgsGraph* QgsGraphAnalyzer::shortestTree( const QgsGraph* source, int startVertexIdx, int criterionNum )
-{
-  QgsGraph *g = new QgsGraph;
-  QVector<int> v;
-  QVector<double> vv;
-  QgsGraphAnalyzer::shortestpath( source, startVertexIdx, criterionNum, v, vv, g );
+      treeResult->addArc( source2result[ arc.outVertex()], source2result[ arc.inVertex()],
+                          arc.properties() );
+    }
+  }
 
-  return g;
+  return treeResult;
 }
diff --git a/src/analysis/network/qgsgraphanalyzer.h b/src/analysis/network/qgsgraphanalyzer.h
@@ -35,12 +35,11 @@ class ANALYSIS_EXPORT QgsGraphAnalyzer
      * 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
+     * @param criterionNum index of arc property as optimization criterion
+     * @param treeResult array represents the shortest path tree. resultTree[ vertexIndex ] == inboundingArcIndex if vertex reacheble and resultTree[ vertexIndex ] == -1 others.
+     * @param resultCost array of cost paths
      */
-    static void shortestpath( const QgsGraph* source, int startVertexIdx, int criterionNum, const QVector<int>& destPointCost, QVector<double>& cost, QgsGraph* treeResult );
+    static void dijkstra( const QgsGraph* source, int startVertexIdx, int criterionNum, QVector<int>* resultTree = NULL, QVector<double>* resultCost = NULL );
 
     /**
      * return shortest path tree with root-node in startVertexIdx

diff --git a/src/plugins/roadgraph/shortestpathwidget.cpp b/src/plugins/roadgraph/shortestpathwidget.cpp
@@ -230,12 +230,12 @@ void RgShortestPathWidget::setBackPoint( const QgsPoint& pt )
   mrbBackPoint->show();
 }
 
-bool RgShortestPathWidget::getPath( QgsGraph* shortestTree, QgsPoint& p1, QgsPoint& p2 )
+QgsGraph* RgShortestPathWidget::getPath( QgsPoint& p1, QgsPoint& p2 )
 {
   if ( mFrontPointLineEdit->text().isNull() || mBackPointLineEdit->text().isNull() )
   {
     QMessageBox::critical( this, tr( "Point not selected" ), tr( "First, select start and stop points." ) );
-    return false;
+    return NULL;
   }
 
   QgsGraphBuilder builder(
@@ -247,7 +247,7 @@ bool RgShortestPathWidget::getPath( QgsGraph* shortestTree, QgsPoint& p1, QgsPoi
     if ( director == NULL )
     {
       QMessageBox::critical( this, tr( "Plugin isn't configured" ), tr( "Plugin isn't configured!" ) );
-      return false;
+      return NULL;
     }
     connect( director, SIGNAL( buildProgress( int, int ) ), mPlugin->iface()->mainWindow(), SLOT( showProgress( int, int ) ) );
     connect( director, SIGNAL( buildMessage( QString ) ), mPlugin->iface()->mainWindow(), SLOT( showStatusMessage( QString ) ) );
@@ -268,12 +268,12 @@ bool RgShortestPathWidget::getPath( QgsGraph* shortestTree, QgsPoint& p1, QgsPoi
   if ( p1 == QgsPoint( 0.0, 0.0 ) )
   {
     QMessageBox::critical( this, tr( "Tie point failed" ), tr( "Start point doesn't tie to the road!" ) );
-    return false;
+    return NULL;
   }
   if ( p2 == QgsPoint( 0.0, 0.0 ) )
   {
     QMessageBox::critical( this, tr( "Tie point failed" ), tr( "Stop point doesn't tie to the road!" ) );
-    return false;
+    return NULL;
   }
 
   QgsGraph *graph = builder.graph();
@@ -287,44 +287,43 @@ bool RgShortestPathWidget::getPath( QgsGraph* shortestTree, QgsPoint& p1, QgsPoi
   if ( mCriterionName->currentIndex() > 0 )
     criterionNum = 1;
 
-  QgsGraphAnalyzer::shortestpath( graph, startVertexIdx, criterionNum, pointIdx, pointCost, shortestTree );
+  QgsGraph* shortestpathTree = QgsGraphAnalyzer::shortestTree( graph, startVertexIdx, criterionNum );
 
   delete graph;
 
-  if ( shortestTree->findVertex( p2 ) == -1 )
+  if ( shortestpathTree->findVertex( p2 ) == -1 )
   {
     QMessageBox::critical( this, tr( "Path not found" ), tr( "Path not found" ) );
-    return false;
+    return NULL;
   }
-  return true;
+  return shortestpathTree;
 }
 
 void RgShortestPathWidget::findingPath()
 {
   QgsPoint p1, p2;
-  QgsGraph path;
-
-  if ( !getPath( &path, p1, p2 ) )
+  QgsGraph *path = getPath( p1, p2 );
+  if ( path == NULL )
     return;
 
   mrbPath->reset( false );
   double time = 0.0;
   double cost = 0.0;
 
-  int startVertexIdx = path.findVertex( p1 );
-  int stopVertexIdx  = path.findVertex( p2 );
+  int startVertexIdx = path->findVertex( p1 );
+  int stopVertexIdx  = path->findVertex( p2 );
   QList< QgsPoint > p;
   while ( startVertexIdx != stopVertexIdx )
   {
-    QgsGraphArcIdList l = path.vertex( stopVertexIdx ).inArc();
+    QgsGraphArcIdList l = path->vertex( stopVertexIdx ).inArc();
     if ( l.empty() )
       break;
-    const QgsGraphArc& e = path.arc( l.front() );
+    const QgsGraphArc& e = path->arc( l.front() );
 
     cost += e.property( 0 ).toDouble();
     time += e.property( 1 ).toDouble();
 
-    p.push_front( path.vertex( e.inVertex() ).point() );
+    p.push_front( path->vertex( e.inVertex() ).point() );
 
     stopVertexIdx = e.outVertex();
   }
@@ -342,6 +341,8 @@ void RgShortestPathWidget::findingPath()
   mPathTimeLineEdit->setText( QString().setNum( time / timeUnit.multipler() ) + timeUnit.name() );
 
   mrbPath->setColor( Qt::red );
+
+  delete path;
 }
 
 void RgShortestPathWidget::clear()
@@ -361,29 +362,29 @@ void RgShortestPathWidget::exportPath()
   if ( !dlg.exec() )
     return;
 
-  QgsPoint p1, p2;
-  QgsGraph path;
-  if ( !getPath( &path, p1, p2 ) )
-    return;
-
   QgsVectorLayer *vl = dlg.mapLayer();
   if ( vl == NULL )
     return;
 
+  QgsPoint p1, p2;
+  QgsGraph *path = getPath( p1, p2 );
+  if ( path == NULL )
+    return;
+
   QgsCoordinateTransform ct( mPlugin->iface()->mapCanvas()->mapRenderer()->destinationCrs(),
                              vl->crs() );
 
-  int startVertexIdx = path.findVertex( p1 );
-  int stopVertexIdx  = path.findVertex( p2 );
+  int startVertexIdx = path->findVertex( p1 );
+  int stopVertexIdx  = path->findVertex( p2 );
 
   QgsPolyline p;
   while ( startVertexIdx != stopVertexIdx )
   {
-    QgsGraphArcIdList l = path.vertex( stopVertexIdx ).inArc();
+    QgsGraphArcIdList l = path->vertex( stopVertexIdx ).inArc();
     if ( l.empty() )
       break;
-    const QgsGraphArc& e = path.arc( l.front() );
-    p.push_front( ct.transform( path.vertex( e.inVertex() ).point() ) );
+    const QgsGraphArc& e = path->arc( l.front() );
+    p.push_front( ct.transform( path->vertex( e.inVertex() ).point() ) );
     stopVertexIdx = e.outVertex();
   }
   p.push_front( ct.transform( p1 ) );
@@ -395,6 +396,7 @@ void RgShortestPathWidget::exportPath()
   vl->updateExtents();
 
   mPlugin->iface()->mapCanvas()->update();
+  delete path;
 }
 
 void RgShortestPathWidget::helpRequested()

diff --git a/src/plugins/roadgraph/shortestpathwidget.h b/src/plugins/roadgraph/shortestpathwidget.h
@@ -105,7 +105,7 @@ class RgShortestPathWidget : public QDockWidget
     /**
      * retrun path as a graph
      */
-    bool getPath( QgsGraph *, QgsPoint& p1, QgsPoint& p2 );
+    QgsGraph* getPath( QgsPoint& p1, QgsPoint& p2 );
 
     /**
      * This line edit show front points coordinates