QGIS API Documentation 3.28.0-Firenze (ed3ad0430f)
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
25void 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 const double curCost = it.key();
64 const int curVertex = it.value();
65 not_begin.erase( it );
66
67 // edge index list
68 const QgsGraphEdgeIds &outgoingEdges = source->vertex( curVertex ).outgoingEdges();
69 for ( const int edgeId : outgoingEdges )
70 {
71 const QgsGraphEdge &arc = source->edge( edgeId );
72 const 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
91QgsGraph *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}
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.
static QgsGraph * shortestTree(const QgsGraph *source, int startVertexIdx, int criterionNum)
Returns shortest path tree with root-node in startVertexIdx.
This class implements a graph edge.
Definition: qgsgraph.h:45
int fromVertex() const
Returns the index of the vertex at the start of this edge.
Definition: qgsgraph.cpp:179
QVector< QVariant > strategies() const
Returns array of available strategies.
Definition: qgsgraph.cpp:174
int toVertex() const
Returns the index of the vertex at the end of this edge.
Definition: qgsgraph.cpp:184
QVariant cost(int strategyIndex) const
Returns edge cost calculated using specified strategy.
Definition: qgsgraph.cpp:169
QgsGraphEdgeIds outgoingEdges() const
Returns outgoing edge ids, i.e.
Definition: qgsgraph.cpp:200
QgsPointXY point() const
Returns point associated with graph vertex.
Definition: qgsgraph.cpp:205
Mathematical graph representation.
Definition: qgsgraph.h:143
const QgsGraphVertex & vertex(int idx) const
Returns the vertex at the given index.
Definition: qgsgraph.cpp:47
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:30
const QgsGraphEdge & edge(int idx) const
Returns the edge at the given index.
Definition: qgsgraph.cpp:76
int addVertex(const QgsPointXY &pt)
Add a vertex to the graph.
Definition: qgsgraph.cpp:24
int vertexCount() const
Returns number of graph vertices.
Definition: qgsgraph.cpp:115
QList< int > QgsGraphEdgeIds
Definition: qgsgraph.h:87