QGIS API Documentation  3.23.0-Master (eb871beae0)
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 
30 int QgsGraph::addEdge( int fromVertexIdx, int toVertexIdx, const QVector< QVariant > &strategies )
31 {
32  QgsGraphEdge e;
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 
47 const 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 
58 void 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 
76 const 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 
87 void 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 
125 int 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 
138 bool QgsGraph::hasVertex( int index ) const
139 {
140  auto it = mGraphVertices.constFind( index );
141  return it != mGraphVertices.constEnd();
142 }
143 
144 bool QgsGraph::hasEdge( int index ) const
145 {
146  auto it = mGraphEdges.constFind( index );
147  return it != mGraphEdges.constEnd();
148 }
149 
150 int 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 
169 QVariant QgsGraphEdge::cost( int i ) const
170 {
171  return mStrategies[ i ];
172 }
173 
174 QVector< 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