QGIS API Documentation  2.99.0-Master (37c43df)
qgsgraphanalyzer.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  qgsgraphanalyzer.cpp
3  --------------------------------------
4  Date : 2011-04-14
5  Copyright : (C) 2010 by Yakushev Sergey
6  Email : YakushevS <at> list.ru
7 ****************************************************************************
8 * *
9 * This program is free software; you can redistribute it and/or modify *
10 * it under the terms of the GNU General Public License as published by *
11 * the Free Software Foundation; either version 2 of the License, or *
12 * (at your option) any later version. *
13 * *
14 ***************************************************************************/
15 
16 #include <limits>
17 
18 #include <QMap>
19 #include <QVector>
20 #include <QPair>
21 
22 #include "qgsgraph.h"
23 #include "qgsgraphanalyzer.h"
24 
25 void QgsGraphAnalyzer::dijkstra( const QgsGraph* source, int startPointIdx, int criterionNum, QVector<int>* resultTree, QVector<double>* resultCost )
26 {
27  QVector< double > * result = nullptr;
28  if ( resultCost )
29  {
30  result = resultCost;
31  }
32  else
33  {
34  result = new QVector<double>();
35  }
36 
37  result->clear();
38  result->insert( result->begin(), source->vertexCount(), std::numeric_limits<double>::infinity() );
39  ( *result )[ startPointIdx ] = 0.0;
40 
41  if ( resultTree )
42  {
43  resultTree->clear();
44  resultTree->insert( resultTree->begin(), source->vertexCount(), -1 );
45  }
46 
47  // QMultiMap< cost, vertexIdx > not_begin
48  // I use it and don't create any struct or class
49  QMultiMap< double, int > not_begin;
50  QMultiMap< double, int >::iterator it;
51 
52  not_begin.insert( 0.0, startPointIdx );
53 
54  while ( !not_begin.empty() )
55  {
56  it = not_begin.begin();
57  double curCost = it.key();
58  int curVertex = it.value();
59  not_begin.erase( it );
60 
61  // edge index list
62  QgsGraphEdgeIds l = source->vertex( curVertex ).outEdges();
63  QgsGraphEdgeIds::iterator arcIt;
64  for ( arcIt = l.begin(); arcIt != l.end(); ++arcIt )
65  {
66  const QgsGraphEdge arc = source->edge( *arcIt );
67  double cost = arc.cost( criterionNum ).toDouble() + curCost;
68 
69  if ( cost < ( *result )[ arc.inVertex()] )
70  {
71  ( *result )[ arc.inVertex()] = cost;
72  if ( resultTree )
73  {
74  ( *resultTree )[ arc.inVertex()] = *arcIt;
75  }
76  not_begin.insert( cost, arc.inVertex() );
77  }
78  }
79  }
80  if ( !resultCost )
81  {
82  delete result;
83  }
84 }
85 
86 QgsGraph* QgsGraphAnalyzer::shortestTree( const QgsGraph* source, int startVertexIdx, int criterionNum )
87 {
88  QgsGraph *treeResult = new QgsGraph();
89  QVector<int> tree;
90 
91  QgsGraphAnalyzer::dijkstra( source, startVertexIdx, criterionNum, &tree );
92 
93  // sourceVertexIdx2resultVertexIdx
94  QVector<int> source2result( tree.size(), -1 );
95 
96  // Add reachable vertices to the result
97  source2result[ startVertexIdx ] = treeResult->addVertex( source->vertex( startVertexIdx ).point() );
98  int i = 0;
99  for ( i = 0; i < source->vertexCount(); ++i )
100  {
101  if ( tree[ i ] != -1 )
102  {
103  source2result[ i ] = treeResult->addVertex( source->vertex( i ).point() );
104  }
105  }
106 
107  // Add arcs to the result
108  for ( i = 0; i < source->vertexCount(); ++i )
109  {
110  if ( tree[ i ] != -1 )
111  {
112  const QgsGraphEdge& arc = source->edge( tree[i] );
113 
114  treeResult->addEdge( source2result[ arc.outVertex()], source2result[ arc.inVertex()],
115  arc.strategies() );
116  }
117  }
118 
119  return treeResult;
120 }
const QgsGraphEdge & edge(int idx) const
Returns edge at given index.
Definition: qgsgraph.cpp:54
int vertexCount() const
Returns number of graph vertices.
Definition: qgsgraph.cpp:59
int outVertex() const
Returns index of the outgoing vertex.
Definition: qgsgraph.cpp:104
QgsGraphEdgeIds outEdges() const
Returns outgoing edges ids.
Definition: qgsgraph.cpp:115
QVector< QVariant > strategies() const
Returns array of available strategies.
Definition: qgsgraph.cpp:94
QgsPoint point() const
Returns point associated with graph vertex.
Definition: qgsgraph.cpp:125
int addVertex(const QgsPoint &pt)
Add a vertex to the graph.
Definition: qgsgraph.cpp:27
static QgsGraph * shortestTree(const QgsGraph *source, int startVertexIdx, int criterionNum)
Returns shortest path tree with root-node in startVertexIdx.
QVariant cost(int strategyIndex) const
Returns edge cost calculated using specified strategy.
Definition: qgsgraph.cpp:89
Mathematical graph representation.
Definition: qgsgraph.h:130
int inVertex() const
Returns index of the incoming vertex.
Definition: qgsgraph.cpp:99
int addEdge(int outVertexIdx, int inVertexIdx, const QVector< QVariant > &strategies)
Add an edge to the graph.
Definition: qgsgraph.cpp:33
const QgsGraphVertex & vertex(int idx) const
Returns vertex at given index.
Definition: qgsgraph.cpp:49
QList< int > QgsGraphEdgeIds
Definition: qgsgraph.h:79
This class implements a graph edge.
Definition: qgsgraph.h:42
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.