QGIS API Documentation  2.14.0-Essen
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 : [email protected]
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 = nullptr;
32  if ( resultCost )
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 )
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;
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();
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 )
77  {
78  ( *resultTree )[ arc.inVertex()] = *arcIt;
79  }
80  not_begin.insert( cost, arc.inVertex() );
81  }
82  }
83  }
84  if ( !resultCost )
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 }
const QgsGraphArc & arc(int idx) const
return edge at index
Definition: qgsgraph.cpp:50
int inVertex() const
return index of incoming vertex
Definition: qgsgraph.cpp:96
iterator erase(iterator pos)
bool empty() const
QVariant property(int propertyIndex) const
return property value
Definition: qgsgraph.cpp:86
iterator begin()
QgsGraphArcIdList outArc() const
return outgoing edges
Definition: qgsgraph.cpp:112
void insert(int i, const T &value)
QgsPoint point() const
return vertex point
Definition: qgsgraph.cpp:122
int outVertex() const
return index of outgoing vertex
Definition: qgsgraph.cpp:101
QVector< QVariant > properties() const
get array of properties
Definition: qgsgraph.cpp:91
void clear()
This class implement a graph edge.
Definition: qgsgraph.h:44
int addArc(int outVertexIdx, int inVertexIdx, const QVector< QVariant > &properties)
add edge to a graph
Definition: qgsgraph.cpp:29
int addVertex(const QgsPoint &pt)
add vertex to a grap
Definition: qgsgraph.cpp:23
QMap< Key, T >::iterator insert(const Key &key, const T &value)
static QgsGraph * shortestTree(const QgsGraph *source, int startVertexIdx, int criterionNum)
return shortest path tree with root-node in startVertexIdx
T & value() const
iterator begin()
Mathematics graph representation.
Definition: qgsgraph.h:131
iterator end()
const Key & key() const
double toDouble(bool *ok) const
const QgsGraphVertex & vertex(int idx) const
return vertex at index
Definition: qgsgraph.cpp:45
int vertexCount() const
return vertex count
Definition: qgsgraph.cpp:56
int size() const
iterator begin()
static void dijkstra(const QgsGraph *source, int startVertexIdx, int criterionNum, QVector< int > *resultTree=nullptr, QVector< double > *resultCost=nullptr)
solve shortest path problem using dijkstra algorithm