1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtWidgets module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#ifndef QGRAPH_P_H
41#define QGRAPH_P_H
42
43//
44// W A R N I N G
45// -------------
46//
47// This file is not part of the Qt API. It exists purely as an
48// implementation detail. This header file may change from version to
49// version without notice, or even be removed.
50//
51// We mean it.
52//
53
54#include <QtWidgets/private/qtwidgetsglobal_p.h>
55#include <QtCore/QHash>
56#include <QtCore/QQueue>
57#include <QtCore/QString>
58#include <QtCore/QDebug>
59
60#include <functional> // for std::less
61
62#include <float.h>
63
64QT_REQUIRE_CONFIG(graphicsview);
65
66QT_BEGIN_NAMESPACE
67
68template <typename Vertex, typename EdgeData>
69class Graph
70{
71public:
72 Graph() {}
73
74 class const_iterator {
75 public:
76 const_iterator(const Graph *graph, bool begin) : g(graph){
77 if (begin) {
78 row = g->m_graph.constBegin();
79 //test if the graph is empty
80 if (row != g->m_graph.constEnd())
81 column = row->cbegin();
82 } else {
83 row = g->m_graph.constEnd();
84 }
85 }
86
87 inline Vertex *operator*() {
88 return column.key();
89 }
90
91 inline Vertex *from() const {
92 return row.key();
93 }
94
95 inline Vertex *to() const {
96 return column.key();
97 }
98
99 inline bool operator==(const const_iterator &o) const { return !(*this != o); }
100 inline bool operator!=(const const_iterator &o) const {
101 if (row == g->m_graph.end()) {
102 return row != o.row;
103 } else {
104 return row != o.row || column != o.column;
105 }
106 }
107
108 // prefix
109 const_iterator &operator++() {
110 if (row != g->m_graph.constEnd()) {
111 ++column;
112 if (column == row->cend()) {
113 ++row;
114 if (row != g->m_graph.constEnd()) {
115 column = row->cbegin();
116 }
117 }
118 }
119 return *this;
120 }
121
122 private:
123 const Graph *g;
124 typename QHash<Vertex *, QHash<Vertex *, EdgeData *> >::const_iterator row;
125 typename QHash<Vertex *, EdgeData *>::const_iterator column;
126 };
127
128 const_iterator constBegin() const {
129 return const_iterator(this,true);
130 }
131
132 const_iterator constEnd() const {
133 return const_iterator(this,false);
134 }
135
136 /*!
137 * \internal
138 *
139 * If there is an edge between \a first and \a second, it will return a structure
140 * containing the data associated with the edge, otherwise it will return 0.
141 *
142 */
143 EdgeData *edgeData(Vertex* first, Vertex* second) {
144 const auto it = m_graph.constFind(first);
145 if (it == m_graph.cend())
146 return nullptr;
147 const auto jt = it->constFind(second);
148 if (jt == it->cend())
149 return nullptr;
150 return *jt;
151 }
152
153 void createEdge(Vertex *first, Vertex *second, EdgeData *data)
154 {
155 // Creates a bidirectional edge
156#if defined(QT_DEBUG) && 0
157 qDebug("Graph::createEdge(): %s",
158 qPrintable(QString::fromLatin1("%1-%2")
159 .arg(first->toString()).arg(second->toString())));
160#endif
161 if (edgeData(first, second)) {
162#ifdef QT_DEBUG
163 qWarning("%s-%s already has an edge", qPrintable(first->toString()), qPrintable(second->toString()));
164#endif
165 }
166 createDirectedEdge(from: first, to: second, data);
167 createDirectedEdge(from: second, to: first, data);
168 }
169
170 void removeEdge(Vertex *first, Vertex *second)
171 {
172 // Removes a bidirectional edge
173#if defined(QT_DEBUG) && 0
174 qDebug("Graph::removeEdge(): %s",
175 qPrintable(QString::fromLatin1("%1-%2")
176 .arg(first->toString()).arg(second->toString())));
177#endif
178 EdgeData *data = edgeData(first, second);
179 removeDirectedEdge(from: first, to: second);
180 removeDirectedEdge(from: second, to: first);
181 if (data) delete data;
182 }
183
184 EdgeData *takeEdge(Vertex* first, Vertex* second)
185 {
186#if defined(QT_DEBUG) && 0
187 qDebug("Graph::takeEdge(): %s",
188 qPrintable(QString::fromLatin1("%1-%2")
189 .arg(first->toString()).arg(second->toString())));
190#endif
191 // Removes a bidirectional edge
192 EdgeData *data = edgeData(first, second);
193 if (data) {
194 removeDirectedEdge(from: first, to: second);
195 removeDirectedEdge(from: second, to: first);
196 }
197 return data;
198 }
199
200 QList<Vertex *> adjacentVertices(Vertex *vertex) const
201 {
202 const auto it = m_graph.constFind(vertex);
203 if (it == m_graph.cend())
204 return QList<Vertex *>();
205 else
206 return it->keys();
207 }
208
209 QSet<Vertex*> vertices() const {
210 QSet<Vertex *> setOfVertices;
211 for (const_iterator it = constBegin(); it != constEnd(); ++it) {
212 setOfVertices.insert(*it);
213 }
214 return setOfVertices;
215 }
216
217 QVector<QPair<Vertex*, Vertex*> > connections() const {
218 QVector<QPair<Vertex*, Vertex*> > conns;
219 for (const_iterator it = constBegin(); it != constEnd(); ++it) {
220 Vertex *from = it.from();
221 Vertex *to = it.to();
222 // do not return (from,to) *and* (to,from)
223 if (std::less<Vertex*>()(from, to))
224 conns.append(qMakePair(from, to));
225 }
226 return conns;
227 }
228
229#if defined(QT_DEBUG)
230 QString serializeToDot() { // traversal
231 QString strVertices;
232 QString edges;
233
234 QSet<Vertex *> setOfVertices = vertices();
235 for (typename QSet<Vertex*>::const_iterator it = setOfVertices.begin(); it != setOfVertices.end(); ++it) {
236 Vertex *v = *it;
237 const QList<Vertex*> adjacents = adjacentVertices(vertex: v);
238 for (auto *v1 : adjacents) {
239 EdgeData *data = edgeData(first: v, second: v1);
240 bool forward = data->from == v;
241 if (forward) {
242 edges += QString::fromLatin1(str: "\"%1\"->\"%2\" [label=\"[%3,%4,%5,%6,%7]\" color=\"#000000\"] \n")
243 .arg(v->toString())
244 .arg(v1->toString())
245 .arg(data->minSize)
246 .arg(data->minPrefSize)
247 .arg(data->prefSize)
248 .arg(data->maxPrefSize)
249 .arg(data->maxSize)
250 ;
251 }
252 }
253 strVertices += QString::fromLatin1(str: "\"%1\" [label=\"%2\"]\n").arg(v->toString()).arg(v->toString());
254 }
255 return QString::fromLatin1(str: "%1\n%2\n").arg(args&: strVertices, args&: edges);
256 }
257#endif
258
259protected:
260 void createDirectedEdge(Vertex *from, Vertex *to, EdgeData *data)
261 {
262 m_graph[from][to] = data;
263 }
264
265 void removeDirectedEdge(Vertex *from, Vertex *to)
266 {
267 const auto it = m_graph.find(from);
268 Q_ASSERT(it != m_graph.end());
269
270 it->remove(to);
271 if (it->isEmpty()) {
272 //nobody point to 'from' so we can remove it from the graph
273 m_graph.erase(it);
274 }
275 }
276
277private:
278 QHash<Vertex *, QHash<Vertex *, EdgeData *> > m_graph;
279};
280
281QT_END_NAMESPACE
282
283#endif
284

source code of qtbase/src/widgets/graphicsview/qgraph_p.h