Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
Add method to find opposite edge in a QgsGraph
  • Loading branch information
nyalldawson committed Nov 9, 2021
1 parent c0b253a commit 37b3eaa
Show file tree
Hide file tree
Showing 4 changed files with 117 additions and 2 deletions.
30 changes: 29 additions & 1 deletion python/analysis/auto_generated/network/qgsgraph.sip.in
Expand Up @@ -236,16 +236,44 @@ no longer have any incoming or outgoing edges as a result will be removed from t
}
%End


int findVertex( const QgsPointXY &pt ) const;
%Docstring
Find vertex by associated point

:return: vertex index
%End


int findOppositeEdge( int index ) const;
%Docstring
Finds the first edge which is the opposite of the edge with the specified index.

This represents the edge which has the same vertices as the specified edge, but
the opposite direction in the graph.(I.e. the edge which starts at the "from" vertex
of the specified edge and ends at the "to" vertex.)

Returns -1 if no opposite edge exists.

:raises IndexError: if the edge with the specified ``index`` is not found.

.. versionadded:: 3.24
%End
%MethodCode
auto it = sipCpp->mGraphEdges.constFind( a0 );
if ( it != sipCpp->mGraphEdges.constEnd() )
{
sipRes = sipCpp->findOppositeEdge( a0 );
}
else
{
PyErr_SetString( PyExc_IndexError, QByteArray::number( a0 ) );
sipIsErr = 1;
}
%End

protected:


};

/************************************************************************
Expand Down
19 changes: 19 additions & 0 deletions src/analysis/network/qgsgraph.cpp
Expand Up @@ -129,6 +129,25 @@ int QgsGraph::findVertex( const QgsPointXY &pt ) const
return -1;
}

int QgsGraph::findOppositeEdge( int index ) const
{
auto it = mGraphEdges.constFind( index );
if ( it != mGraphEdges.constEnd() )
{
const int fromVertex = it->fromVertex();
const int toVertex = it->toVertex();

// look for edges which start at toVertex
const QgsGraphEdgeIds candidates = mGraphVertices.value( toVertex ).outgoingEdges();
for ( int candidate : candidates )
{
if ( mGraphEdges.value( candidate ).toVertex() == fromVertex )
return candidate;
}
}
return -1;
}

QVariant QgsGraphEdge::cost( int i ) const
{
return mStrategies[ i ];
Expand Down
46 changes: 45 additions & 1 deletion src/analysis/network/qgsgraph.h
Expand Up @@ -299,14 +299,58 @@ class ANALYSIS_EXPORT QgsGraph
% End
#endif


/**
* Find vertex by associated point
* \returns vertex index
*/
int findVertex( const QgsPointXY &pt ) const;

#ifndef SIP_RUN

/**
* Finds the first edge which is the opposite of the edge with the specified index.
*
* This represents the edge which has the same vertices as the specified edge, but
* the opposite direction in the graph.(I.e. the edge which starts at the "from" vertex
* of the specified edge and ends at the "to" vertex.)
*
* Returns -1 if no opposite edge exists.
*
* \since QGIS 3.24
*/
int findOppositeEdge( int index ) const;
#else

/**
* Finds the first edge which is the opposite of the edge with the specified index.
*
* This represents the edge which has the same vertices as the specified edge, but
* the opposite direction in the graph.(I.e. the edge which starts at the "from" vertex
* of the specified edge and ends at the "to" vertex.)
*
* Returns -1 if no opposite edge exists.
*
* \throws IndexError if the edge with the specified \a index is not found.
*
* \since QGIS 3.24
*/
int findOppositeEdge( int index ) const;
% MethodCode
auto it = sipCpp->mGraphEdges.constFind( a0 );
if ( it != sipCpp->mGraphEdges.constEnd() )
{
sipRes = sipCpp->findOppositeEdge( a0 );
}
else
{
PyErr_SetString( PyExc_IndexError, QByteArray::number( a0 ) );
sipIsErr = 1;
}
% End
#endif

protected:

#ifndef SIP_RUN
//! Graph vertices
QHash<int, QgsGraphVertex> mGraphVertices;
Expand Down
24 changes: 24 additions & 0 deletions tests/src/python/test_qgsgraph.py
Expand Up @@ -306,6 +306,30 @@ def test_remove_edge(self):
with self.assertRaises(IndexError):
graph.removeEdge(edge_5)

def test_find_opposite_edge(self):
graph = QgsGraph()

with self.assertRaises(IndexError):
graph.findOppositeEdge(0)
with self.assertRaises(IndexError):
graph.findOppositeEdge(-1)

v1 = graph.addVertex(QgsPointXY(1, 1))
v2 = graph.addVertex(QgsPointXY(2, 2))
v3 = graph.addVertex(QgsPointXY(3, 3))
v4 = graph.addVertex(QgsPointXY(4, 4))
edge_1 = graph.addEdge(v1, v2, [1])
edge_2 = graph.addEdge(v2, v1, [1])
edge_3 = graph.addEdge(v2, v3, [1])
edge_4 = graph.addEdge(v2, v4, [1])
edge_5 = graph.addEdge(v3, v4, [1])

self.assertEqual(graph.findOppositeEdge(edge_1), edge_2)
self.assertEqual(graph.findOppositeEdge(edge_2), edge_1)
self.assertEqual(graph.findOppositeEdge(edge_3), -1)
self.assertEqual(graph.findOppositeEdge(edge_4), -1)
self.assertEqual(graph.findOppositeEdge(edge_5), -1)


if __name__ == '__main__':
unittest.main()

0 comments on commit 37b3eaa

Please sign in to comment.