1 /***************************************************************************
2   qgsgraph.h
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 
16 /*
17  * This file describes the built-in QGIS classes for modeling a mathematical graph.
18  * Vertices are identified by their geographic coordinates and have no additional
19  * properties. Number of strategies for calculating edge cost is not limited.
20  * Graph may have incidence edges.
21  *
22  * \file qgsgraph.h
23  */
24 
25 #ifndef QGSGRAPH_H
26 #define QGSGRAPH_H
27 
28 #include <QList>
29 #include <QVector>
30 #include <QVariant>
31 
32 #include "qgspointxy.h"
33 #include "qgis_analysis.h"
34 
35 class QgsGraphVertex;
36 
37 /**
38  * \ingroup analysis
39  * \class QgsGraphEdge
40  * \brief This class implements a graph edge
41  * \since QGIS 3.0
42  */
43 class ANALYSIS_EXPORT QgsGraphEdge
44 {
45   public:
46 
47     /**
48      * Constructor for QgsGraphEdge.
49      */
50     QgsGraphEdge() = default;
51 
52     /**
53      * Returns edge cost calculated using specified strategy
54      * \param strategyIndex strategy index
55      */
56     QVariant cost( int strategyIndex ) const;
57 
58     /**
59      * Returns array of available strategies
60      */
61     QVector< QVariant > strategies() const;
62 
63     /**
64      * Returns the index of the vertex at the end of this edge.
65      * \see fromVertex()
66      */
67     int toVertex() const;
68 
69     /**
70      * Returns the index of the vertex at the start of this edge.
71      * \see toVertex()
72      */
73     int fromVertex() const;
74 
75   private:
76 
77     QVector< QVariant > mStrategies;
78 
79     int mToIdx = 0;
80     int mFromIdx = 0;
81 
82     friend class QgsGraph;
83 };
84 
85 
86 typedef QList< int > QgsGraphEdgeIds;
87 
88 /**
89  * \ingroup analysis
90  * \class QgsGraphVertex
91  * \brief This class implements a graph vertex
92  * \since QGIS 3.0
93  */
94 class ANALYSIS_EXPORT QgsGraphVertex
95 {
96   public:
97 
98     /**
99      * Default constructor. It is needed for Qt's container, e.g. QVector
100      */
101     QgsGraphVertex() = default;
102 
103     /**
104      * This constructor initializes QgsGraphVertex object and associates a vertex with a point
105      */
106 
107     QgsGraphVertex( const QgsPointXY &point );
108 
109     /**
110      * Returns the incoming edge ids, i.e. edges which end at this node.
111      * \see outgoingEdges()
112      */
113     QgsGraphEdgeIds incomingEdges() const;
114 
115     /**
116      * Returns outgoing edge ids, i.e. edges which start at this node.
117      * \see incomingEdges()
118      */
119     QgsGraphEdgeIds outgoingEdges() const;
120 
121     /**
122      * Returns point associated with graph vertex.
123      */
124     QgsPointXY point() const;
125 
126   private:
127     QgsPointXY mCoordinate;
128     QgsGraphEdgeIds mIncomingEdges;
129     QgsGraphEdgeIds mOutgoingEdges;
130 
131     friend class QgsGraph;
132 };
133 
134 /**
135  * \ingroup analysis
136  * \class QgsGraph
137  * \brief Mathematical graph representation
138  * \since QGIS 3.0
139  */
140 
141 class ANALYSIS_EXPORT QgsGraph
142 {
143   public:
144 
145     /**
146      * Constructor for QgsGraph.
147      */
148     QgsGraph() = default;
149 
150     // Graph constructing methods
151 
152     /**
153      * Add a vertex to the graph
154      */
155     int addVertex( const QgsPointXY &pt );
156 
157     /**
158      * Add an edge to the graph, going from the \a fromVertexIdx
159      * to \a toVertexIdx.
160      */
161     int addEdge( int fromVertexIdx, int toVertexIdx, const QVector< QVariant > &strategies );
162 
163     /**
164      * Returns number of graph vertices
165      */
166     int vertexCount() const;
167 
168     /**
169      * Returns vertex at given index
170      */
171     const QgsGraphVertex &vertex( int idx ) const;
172 
173     /**
174       * Returns number of graph edges
175       */
176     int edgeCount() const;
177 
178     /**
179      * Returns edge at given index
180      */
181     const QgsGraphEdge &edge( int idx ) const;
182 
183     /**
184      * Find vertex by associated point
185      * \returns vertex index
186      */
187     int findVertex( const QgsPointXY &pt ) const;
188 
189   private:
190     QVector<QgsGraphVertex> mGraphVertices;
191 
192     QVector<QgsGraphEdge> mGraphEdges;
193 };
194 
195 #endif // QGSGRAPH_H
196