QGIS API Documentation  2.5.0-Master
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
qgsgraphanalyzer.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  qgsgraphanlyzer.cpp - QGIS Tools for graph analysis
3  -------------------
4  begin : 14 april 2011
5  copyright : (C) Sergey Yakushev
6  email : Yakushevs@list.ru
7  ***************************************************************************/
8 
9 /***************************************************************************
10  * *
11  * This program is free software; you can redistribute it and/or modify *
12  * it under the terms of the GNU General Public License as published by *
13  * the Free Software Foundation; either version 2 of the License, or *
14  * (at your option) any later version. *
15  * *
16  ***************************************************************************/
17 // C++ standard includes
18 #include <limits>
19 
20 // QT includes
21 #include <QMap>
22 #include <QVector>
23 #include <QPair>
24 
25 //QGIS-uncludes
26 #include "qgsgraph.h"
27 #include "qgsgraphanalyzer.h"
28 
29 void QgsGraphAnalyzer::dijkstra( const QgsGraph* source, int startPointIdx, int criterionNum, QVector<int>* resultTree, QVector<double>* resultCost )
30 {
31  QVector< double > * result = NULL;
32  if ( resultCost != NULL )
33  {
34  result = resultCost;
35  }
36  else
37  {
38  result = new QVector<double>();
39  }
40 
41  result->clear();
42  result->insert( result->begin(), source->vertexCount(), std::numeric_limits<double>::infinity() );
43  ( *result )[ startPointIdx ] = 0.0;
44 
45  if ( resultTree != NULL )
46  {
47  resultTree->clear();
48  resultTree->insert( resultTree->begin(), source->vertexCount(), -1 );
49  }
50 
51  // QMultiMap< cost, vertexIdx > not_begin
52  // I use it and not create any struct or class.
53  QMultiMap< double, int > not_begin;
54  QMultiMap< double, int >::iterator it;
55 
56  not_begin.insert( 0.0, startPointIdx );
57 
58  while ( !not_begin.empty() )
59  {
60  it = not_begin.begin();
61  double curCost = it.key();
62  int curVertex = it.value();
63  not_begin.erase( it );
64 
65  // edge index list
66  QgsGraphArcIdList l = source->vertex( curVertex ).outArc();
67  QgsGraphArcIdList::iterator arcIt;
68  for ( arcIt = l.begin(); arcIt != l.end(); ++arcIt )
69  {
70  const QgsGraphArc arc = source->arc( *arcIt );
71  double cost = arc.property( criterionNum ).toDouble() + curCost;
72 
73  if ( cost < ( *result )[ arc.inVertex()] )
74  {
75  ( *result )[ arc.inVertex()] = cost;
76  if ( resultTree != NULL )
77  {
78  ( *resultTree )[ arc.inVertex()] = *arcIt;
79  }
80  not_begin.insert( cost, arc.inVertex() );
81  }
82  }
83  }
84  if ( resultCost == NULL )
85  {
86  delete result;
87  }
88 }
89 
90 QgsGraph* QgsGraphAnalyzer::shortestTree( const QgsGraph* source, int startVertexIdx, int criterionNum )
91 {
92  QgsGraph *treeResult = new QgsGraph();
93  QVector<int> tree;
94 
95  QgsGraphAnalyzer::dijkstra( source, startVertexIdx, criterionNum, &tree );
96 
97  // sourceVertexIdx2resultVertexIdx
98  QVector<int> source2result( tree.size(), -1 );
99 
100  // Add reachable vertices to the result
101  source2result[ startVertexIdx ] = treeResult->addVertex( source->vertex( startVertexIdx ).point() );
102  int i = 0;
103  for ( i = 0; i < source->vertexCount(); ++i )
104  {
105  if ( tree[ i ] != -1 )
106  {
107  source2result[ i ] = treeResult->addVertex( source->vertex( i ).point() );
108  }
109  }
110 
111  // Add arcs to result
112  for ( i = 0; i < source->vertexCount(); ++i )
113  {
114  if ( tree[ i ] != -1 )
115  {
116  const QgsGraphArc& arc = source->arc( tree[i] );
117 
118  treeResult->addArc( source2result[ arc.outVertex()], source2result[ arc.inVertex()],
119  arc.properties() );
120  }
121  }
122 
123  return treeResult;
124 }