QGIS API Documentation  2.99.0-Master (19b062c)
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  const QgsGraphEdgeIds &outgoingEdges = source->vertex( curVertex ).outgoingEdges();
63  for ( int edgeId : outgoingEdges )
64  {
65  const QgsGraphEdge &arc = source->edge( edgeId );
66  double cost = arc.cost( criterionNum ).toDouble() + curCost;
67 
68  if ( cost < ( *result )[ arc.toVertex()] )
69  {
70  ( *result )[ arc.toVertex()] = cost;
71  if ( resultTree )
72  {
73  ( *resultTree )[ arc.toVertex()] = edgeId;
74  }
75  not_begin.insert( cost, arc.toVertex() );
76  }
77  }
78  }
79  if ( !resultCost )
80  {
81  delete result;
82  }
83 }
84 
85 QgsGraph *QgsGraphAnalyzer::shortestTree( const QgsGraph *source, int startVertexIdx, int criterionNum )
86 {
87  QgsGraph *treeResult = new QgsGraph();
88  QVector<int> tree;
89 
90  QgsGraphAnalyzer::dijkstra( source, startVertexIdx, criterionNum, &tree );
91 
92  // sourceVertexIdx2resultVertexIdx
93  QVector<int> source2result( tree.size(), -1 );
94 
95  // Add reachable vertices to the result
96  source2result[ startVertexIdx ] = treeResult->addVertex( source->vertex( startVertexIdx ).point() );
97  int i = 0;
98  for ( i = 0; i < source->vertexCount(); ++i )
99  {
100  if ( tree[ i ] != -1 )
101  {
102  source2result[ i ] = treeResult->addVertex( source->vertex( i ).point() );
103  }
104  }
105 
106  // Add arcs to the result
107  for ( i = 0; i < source->vertexCount(); ++i )
108  {
109  if ( tree[ i ] != -1 )
110  {
111  const QgsGraphEdge &arc = source->edge( tree[i] );
112 
113  treeResult->addEdge( source2result[ arc.fromVertex()], source2result[ arc.toVertex()],
114  arc.strategies() );
115  }
116  }
117 
118  return treeResult;
119 }
const QgsGraphEdge & edge(int idx) const
Returns edge at given index.
Definition: qgsgraph.cpp:50
int vertexCount() const
Returns number of graph vertices.
Definition: qgsgraph.cpp:55
QgsPointXY point() const
Returns point associated with graph vertex.
Definition: qgsgraph.cpp:114
QVector< QVariant > strategies() const
Returns array of available strategies.
Definition: qgsgraph.cpp:83
int fromVertex() const
Returns the index of the vertex at the start of this edge.
Definition: qgsgraph.cpp:88
QgsGraphEdgeIds outgoingEdges() const
Returns outgoing edge ids, i.e.
Definition: qgsgraph.cpp:109
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:78
Mathematical graph representation.
Definition: qgsgraph.h:141
int addEdge(int fromVertexIdx, int toVertexIdx, const QVector< QVariant > &strategies)
Add an edge to the graph, going from the fromVertexIdx to toVertexIdx.
Definition: qgsgraph.cpp:29
int toVertex() const
Returns the index of the vertex at the end of this edge.
Definition: qgsgraph.cpp:93
const QgsGraphVertex & vertex(int idx) const
Returns vertex at given index.
Definition: qgsgraph.cpp:45
int addVertex(const QgsPointXY &pt)
Add a vertex to the graph.
Definition: qgsgraph.cpp:23
QList< int > QgsGraphEdgeIds
Definition: qgsgraph.h:86
This class implements a graph edge.
Definition: qgsgraph.h:43
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.