Quantum GIS API Documentation
1.8
|
00001 /*************************************************************************** 00002 qgsgraphanlyzer.cpp - QGIS Tools for graph analysis 00003 ------------------- 00004 begin : 14 april 2011 00005 copyright : (C) Sergey Yakushev 00006 email : [email protected] 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 }