QGIS API Documentation  3.14.0-Pi (9f7028fd23)
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  if ( startPointIdx < 0 || startPointIdx >= source->vertexCount() )
28  {
29  // invalid start point
30  return;
31  }
32 
33  QVector< double > *result = nullptr;
34  if ( resultCost )
35  {
36  result = resultCost;
37  }
38  else
39  {
40  result = new QVector<double>();
41  }
42 
43  result->clear();
44  result->insert( result->begin(), source->vertexCount(), std::numeric_limits<double>::infinity() );
45  ( *result )[ startPointIdx ] = 0.0;
46 
47  if ( resultTree )
48  {
49  resultTree->clear();
50  resultTree->insert( resultTree->begin(), source->vertexCount(), -1 );
51  }
52 
53  // QMultiMap< cost, vertexIdx > not_begin
54  // I use it and don't create any struct or class
55  QMultiMap< double, int > not_begin;
56  QMultiMap< double, int >::iterator it;
57 
58  not_begin.insert( 0.0, startPointIdx );
59 
60  while ( !not_begin.empty() )
61  {
62  it = not_begin.begin();
63  double curCost = it.key();
64  int curVertex = it.value();
65  not_begin.erase( it );
66 
67  // edge index list
68  const QgsGraphEdgeIds &outgoingEdges = source->vertex( curVertex ).outgoingEdges();
69  for ( int edgeId : outgoingEdges )
70  {
71  const QgsGraphEdge &arc = source->edge( edgeId );
72  double cost = arc.cost( criterionNum ).toDouble() + curCost;
73 
74  if ( cost < ( *result )[ arc.toVertex()] )
75  {
76  ( *result )[ arc.toVertex()] = cost;
77  if ( resultTree )
78  {
79  ( *resultTree )[ arc.toVertex()] = edgeId;
80  }
81  not_begin.insert( cost, arc.toVertex() );
82  }
83  }
84  }
85  if ( !resultCost )
86  {
87  delete result;
88  }
89 }
90 
91 QgsGraph *QgsGraphAnalyzer::shortestTree( const QgsGraph *source, int startVertexIdx, int criterionNum )
92 {
93  QgsGraph *treeResult = new QgsGraph();
94  QVector<int> tree;
95 
96  QgsGraphAnalyzer::dijkstra( source, startVertexIdx, criterionNum, &tree );
97 
98  // sourceVertexIdx2resultVertexIdx
99  QVector<int> source2result( tree.size(), -1 );
100 
101  // Add reachable vertices to the result
102  source2result[ startVertexIdx ] = treeResult->addVertex( source->vertex( startVertexIdx ).point() );
103  int i = 0;
104  for ( i = 0; i < source->vertexCount(); ++i )
105  {
106  if ( tree[ i ] != -1 )
107  {
108  source2result[ i ] = treeResult->addVertex( source->vertex( i ).point() );
109  }
110  }
111 
112  // Add arcs to the result
113  for ( i = 0; i < source->vertexCount(); ++i )
114  {
115  if ( tree[ i ] != -1 )
116  {
117  const QgsGraphEdge &arc = source->edge( tree[i] );
118 
119  treeResult->addEdge( source2result[ arc.fromVertex()], source2result[ arc.toVertex()],
120  arc.strategies() );
121  }
122  }
123 
124  return treeResult;
125 }
qgsgraph.h
QgsGraph
Mathematical graph representation.
Definition: qgsgraph.h:141
QgsGraphVertex::outgoingEdges
QgsGraphEdgeIds outgoingEdges() const
Returns outgoing edge ids, i.e.
Definition: qgsgraph.cpp:109
QgsGraphVertex::point
QgsPointXY point() const
Returns point associated with graph vertex.
Definition: qgsgraph.cpp:114
QgsGraphEdge
This class implements a graph edge.
Definition: qgsgraph.h:43
QgsGraph::addVertex
int addVertex(const QgsPointXY &pt)
Add a vertex to the graph.
Definition: qgsgraph.cpp:23
QgsGraphEdge::strategies
QVector< QVariant > strategies() const
Returns array of available strategies.
Definition: qgsgraph.cpp:83
QgsGraphEdge::fromVertex
int fromVertex() const
Returns the index of the vertex at the start of this edge.
Definition: qgsgraph.cpp:88
QgsGraph::vertex
const QgsGraphVertex & vertex(int idx) const
Returns vertex at given index.
Definition: qgsgraph.cpp:45
QgsGraphEdgeIds
QList< int > QgsGraphEdgeIds
Definition: qgsgraph.h:86
QgsGraph::edge
const QgsGraphEdge & edge(int idx) const
Returns edge at given index.
Definition: qgsgraph.cpp:50
QgsGraphEdge::cost
QVariant cost(int strategyIndex) const
Returns edge cost calculated using specified strategy.
Definition: qgsgraph.cpp:78
QgsGraphEdge::toVertex
int toVertex() const
Returns the index of the vertex at the end of this edge.
Definition: qgsgraph.cpp:93
QgsGraph::vertexCount
int vertexCount() const
Returns number of graph vertices.
Definition: qgsgraph.cpp:55
QgsGraphAnalyzer::shortestTree
static QgsGraph * shortestTree(const QgsGraph *source, int startVertexIdx, int criterionNum)
Returns shortest path tree with root-node in startVertexIdx.
Definition: qgsgraphanalyzer.cpp:91
qgsgraphanalyzer.h
QgsGraph::addEdge
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
QgsGraphAnalyzer::dijkstra
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.
Definition: qgsgraphanalyzer.cpp:25