Quantum GIS API Documentation  1.8
src/analysis/network/qgsgraphanalyzer.cpp
Go to the documentation of this file.
00001 /***************************************************************************
00002     qgsgraphanlyzer.cpp - QGIS Tools for graph analysis
00003                              -------------------
00004     begin                : 14 april 2011
00005     copyright            : (C) Sergey Yakushev
00006     email                : Yakushevs@list.ru
00007  ***************************************************************************/
00008 
00009 /***************************************************************************
00010  *                                                                         *
00011  *   This program is free software; you can redistribute it and/or modify  *
00012  *   it under the terms of the GNU General Public License as published by  *
00013  *   the Free Software Foundation; either version 2 of the License, or     *
00014  *   (at your option) any later version.                                   *
00015  *                                                                         *
00016  ***************************************************************************/
00017 // C++ standard includes
00018 #include <limits>
00019 
00020 // QT includes
00021 #include <QMap>
00022 #include <QVector>
00023 #include <QPair>
00024 
00025 //QGIS-uncludes
00026 #include "qgsgraph.h"
00027 #include "qgsgraphanalyzer.h"
00028 
00029 void QgsGraphAnalyzer::dijkstra( const QgsGraph* source, int startPointIdx, int criterionNum, QVector<int>* resultTree, QVector<double>* resultCost )
00030 {
00031   QVector< double > * result = NULL;
00032   if ( resultCost != NULL )
00033   {
00034     result = resultCost;
00035   }
00036   else
00037   {
00038     result = new QVector<double>();
00039   }
00040 
00041   result->clear();
00042   result->insert( result->begin(), source->vertexCount(), std::numeric_limits<double>::infinity() );
00043   ( *result )[ startPointIdx ] = 0.0;
00044 
00045   if ( resultTree != NULL )
00046   {
00047     resultTree->clear();
00048     resultTree->insert( resultTree->begin(), source->vertexCount(), -1 );
00049   }
00050 
00051   // QMultiMap< cost, vertexIdx > not_begin
00052   // I use it and not create any struct or class.
00053   QMultiMap< double, int > not_begin;
00054   QMultiMap< double, int >::iterator it;
00055 
00056   not_begin.insert( 0.0, startPointIdx );
00057 
00058   while ( !not_begin.empty() )
00059   {
00060     it = not_begin.begin();
00061     double curCost = it.key();
00062     int curVertex = it.value();
00063     not_begin.erase( it );
00064 
00065     // edge index list
00066     QgsGraphArcIdList l = source->vertex( curVertex ).outArc();
00067     QgsGraphArcIdList::iterator arcIt;
00068     for ( arcIt = l.begin(); arcIt != l.end(); ++arcIt )
00069     {
00070       const QgsGraphArc arc = source->arc( *arcIt );
00071       double cost = arc.property( criterionNum ).toDouble() + curCost;
00072 
00073       if ( cost < ( *result )[ arc.inVertex()] )
00074       {
00075         ( *result )[ arc.inVertex()] = cost;
00076         if ( resultTree != NULL )
00077         {
00078           ( *resultTree )[ arc.inVertex()] = *arcIt;
00079         }
00080         not_begin.insert( cost, arc.inVertex() );
00081       }
00082     }
00083   }
00084   if ( resultCost == NULL )
00085   {
00086     delete result;
00087   }
00088 }
00089 
00090 QgsGraph* QgsGraphAnalyzer::shortestTree( const QgsGraph* source, int startVertexIdx, int criterionNum )
00091 {
00092   QgsGraph *treeResult = new QgsGraph();
00093   QVector<int> tree;
00094 
00095   QgsGraphAnalyzer::dijkstra( source, startVertexIdx, criterionNum, &tree );
00096 
00097   // sourceVertexIdx2resultVertexIdx
00098   QVector<int> source2result( tree.size(), -1 );
00099 
00100   // Add reachable vertices to the result
00101   source2result[ startVertexIdx ] = treeResult->addVertex( source->vertex( startVertexIdx ).point() );
00102   int i = 0;
00103   for ( i = 0; i < source->vertexCount(); ++i )
00104   {
00105     if ( tree[ i ] != -1 )
00106     {
00107       source2result[ i ] = treeResult->addVertex( source->vertex( i ).point() );
00108     }
00109   }
00110 
00111   // Add arcs to result
00112   for ( i = 0; i < source->vertexCount(); ++i )
00113   {
00114     if ( tree[ i ] != -1 )
00115     {
00116       const QgsGraphArc& arc = source->arc( tree[i] );
00117 
00118       treeResult->addArc( source2result[ arc.outVertex()], source2result[ arc.inVertex()],
00119                           arc.properties() );
00120     }
00121   }
00122 
00123   return treeResult;
00124 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines