QGIS API Documentation 3.27.0-Master (75dc696944)
qgsgraph.cpp
Go to the documentation of this file.
1/***************************************************************************
2 qgsgraph.cpp
3 --------------------------------------
4 Date : 2011-04-01
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
21#include "qgsgraph.h"
22#include <QSet>
23
25{
26 mGraphVertices[ mNextVertexId ] = QgsGraphVertex( pt );
27 return mNextVertexId++;
28}
29
30int QgsGraph::addEdge( int fromVertexIdx, int toVertexIdx, const QVector< QVariant > &strategies )
31{
33
34 e.mStrategies = strategies;
35 e.mToIdx = toVertexIdx;
36 e.mFromIdx = fromVertexIdx;
37
38 mGraphEdges[ mNextEdgeId ] = e;
39 const int edgeIdx = mGraphEdges.size() - 1;
40
41 mGraphVertices[ toVertexIdx ].mIncomingEdges.push_back( edgeIdx );
42 mGraphVertices[ fromVertexIdx ].mOutgoingEdges.push_back( edgeIdx );
43
44 return mNextEdgeId++;
45}
46
47const QgsGraphVertex &QgsGraph::vertex( int idx ) const
48{
49 auto it = mGraphVertices.constFind( idx );
50 if ( it != mGraphVertices.constEnd() )
51 return ( it ).value();
52 Q_ASSERT_X( false, "QgsGraph::vertex()", "Invalid vertex ID" );
53
54 // unreachable...
55 return ( *const_cast< QHash<int, QgsGraphVertex>* >( &mGraphVertices ) )[ idx ];
56}
57
58void QgsGraph::removeVertex( int index )
59{
60 auto it = mGraphVertices.constFind( index );
61 if ( it != mGraphVertices.constEnd() )
62 {
63 QSet< int > affectedEdges = qgis::listToSet( it->incomingEdges() );
64 affectedEdges.unite( qgis::listToSet( it->outgoingEdges() ) );
65
66 mGraphVertices.erase( it );
67
68 // remove affected edges
69 for ( int edgeId : std::as_const( affectedEdges ) )
70 {
71 mGraphEdges.remove( edgeId );
72 }
73 }
74}
75
76const QgsGraphEdge &QgsGraph::edge( int idx ) const
77{
78 auto it = mGraphEdges.constFind( idx );
79 if ( it != mGraphEdges.constEnd() )
80 return ( it ).value();
81 Q_ASSERT_X( false, "QgsGraph::edge()", "Invalid edge ID" );
82
83 // unreachable...
84 return ( *const_cast< QHash<int, QgsGraphEdge>* >( &mGraphEdges ) )[ idx ];
85}
86
87void QgsGraph::removeEdge( int index )
88{
89 auto it = mGraphEdges.constFind( index );
90 if ( it != mGraphEdges.constEnd() )
91 {
92 const int fromVertex = it->fromVertex();
93 const int toVertex = it->toVertex();
94 mGraphEdges.erase( it );
95
96 // clean up affected vertices
97 auto vertexIt = mGraphVertices.find( fromVertex );
98 if ( vertexIt != mGraphVertices.end() )
99 {
100 vertexIt->mOutgoingEdges.removeAll( index );
101 if ( vertexIt->mOutgoingEdges.empty() && vertexIt->mIncomingEdges.empty() )
102 mGraphVertices.erase( vertexIt );
103 }
104
105 vertexIt = mGraphVertices.find( toVertex );
106 if ( vertexIt != mGraphVertices.end() )
107 {
108 vertexIt->mIncomingEdges.removeAll( index );
109 if ( vertexIt->mOutgoingEdges.empty() && vertexIt->mIncomingEdges.empty() )
110 mGraphVertices.erase( vertexIt );
111 }
112 }
113}
114
116{
117 return mGraphVertices.size();
118}
119
121{
122 return mGraphEdges.size();
123}
124
125int QgsGraph::findVertex( const QgsPointXY &pt ) const
126{
127 int i = 0;
128 for ( i = 0; i < mGraphVertices.size(); ++i )
129 {
130 if ( mGraphVertices[ i ].point() == pt )
131 {
132 return i;
133 }
134 }
135 return -1;
136}
137
138bool QgsGraph::hasVertex( int index ) const
139{
140 auto it = mGraphVertices.constFind( index );
141 return it != mGraphVertices.constEnd();
142}
143
144bool QgsGraph::hasEdge( int index ) const
145{
146 auto it = mGraphEdges.constFind( index );
147 return it != mGraphEdges.constEnd();
148}
149
150int QgsGraph::findOppositeEdge( int index ) const
151{
152 auto it = mGraphEdges.constFind( index );
153 if ( it != mGraphEdges.constEnd() )
154 {
155 const int fromVertex = it->fromVertex();
156 const int toVertex = it->toVertex();
157
158 // look for edges which start at toVertex
159 const QgsGraphEdgeIds candidates = mGraphVertices.value( toVertex ).outgoingEdges();
160 for ( int candidate : candidates )
161 {
162 if ( mGraphEdges.value( candidate ).toVertex() == fromVertex )
163 return candidate;
164 }
165 }
166 return -1;
167}
168
169QVariant QgsGraphEdge::cost( int i ) const
170{
171 return mStrategies[ i ];
172}
173
174QVector< QVariant > QgsGraphEdge::strategies() const
175{
176 return mStrategies;
177}
178
180{
181 return mFromIdx;
182}
183
185{
186 return mToIdx;
187}
188
190 : mCoordinate( point )
191{
192
193}
194
196{
197 return mIncomingEdges;
198}
199
201{
202 return mOutgoingEdges;
203}
204
206{
207 return mCoordinate;
208}
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
This class implements a graph vertex.
Definition: qgsgraph.h:96
QgsGraphEdgeIds outgoingEdges() const
Returns outgoing edge ids, i.e.
Definition: qgsgraph.cpp:200
QgsGraphEdgeIds incomingEdges() const
Returns the incoming edge ids, i.e.
Definition: qgsgraph.cpp:195
QgsPointXY point() const
Returns point associated with graph vertex.
Definition: qgsgraph.cpp:205
QgsGraphVertex()=default
Default constructor.
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
int findOppositeEdge(int index) const
Finds the first edge which is the opposite of the edge with the specified index.
Definition: qgsgraph.cpp:150
int findVertex(const QgsPointXY &pt) const
Find vertex by associated point.
Definition: qgsgraph.cpp:125
bool hasVertex(int index) const
Returns whether the vertex of the given index exists.
Definition: qgsgraph.cpp:138
bool hasEdge(int index) const
Returns whether the edge of the given index exists.
Definition: qgsgraph.cpp:144
QHash< int, QgsGraphVertex > mGraphVertices
Graph vertices.
Definition: qgsgraph.h:366
int edgeCount() const
Returns number of graph edges.
Definition: qgsgraph.cpp:120
const QgsGraphEdge & edge(int idx) const
Returns the edge at the given index.
Definition: qgsgraph.cpp:76
void removeEdge(int index)
Removes the edge at specified index.
Definition: qgsgraph.cpp:87
int addVertex(const QgsPointXY &pt)
Add a vertex to the graph.
Definition: qgsgraph.cpp:24
QHash< int, QgsGraphEdge > mGraphEdges
Graph edges.
Definition: qgsgraph.h:369
void removeVertex(int index)
Removes the vertex at specified index.
Definition: qgsgraph.cpp:58
int vertexCount() const
Returns number of graph vertices.
Definition: qgsgraph.cpp:115
A class to represent a 2D point.
Definition: qgspointxy.h:59
QList< int > QgsGraphEdgeIds
Definition: qgsgraph.h:87