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(first, second, data);
167 createDirectedEdge(second, 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(first, second);
180 removeDirectedEdge(second, 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(first, second);
195 removeDirectedEdge(second, 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 QList<QPair<Vertex *, Vertex *>> connections() const
218 {
219 QList<QPair<Vertex *, Vertex *>> conns;
220 for (const_iterator it = constBegin(); it != constEnd(); ++it) {
221 Vertex *from = it.from();
222 Vertex *to = it.to();
223 // do not return (from,to) *and* (to,from)
224 if (std::less<Vertex*>()(from, to))
225 conns.append(qMakePair(from, to));
226 }
227 return conns;
228 }
229
230#if defined(QT_DEBUG)
231 QString serializeToDot() { // traversal
232 QString strVertices;
233 QString edges;
234
235 QSet<Vertex *> setOfVertices = vertices();
236 for (typename QSet<Vertex*>::const_iterator it = setOfVertices.begin(); it != setOfVertices.end(); ++it) {
237 Vertex *v = *it;
238 const QList<Vertex*> adjacents = adjacentVertices(v);
239 for (auto *v1 : adjacents) {
240 EdgeData *data = edgeData(v, v1);
241 bool forward = data->from == v;
242 if (forward) {
243 edges += QString::fromLatin1("\"%1\"->\"%2\" [label=\"[%3,%4,%5,%6,%7]\" color=\"#000000\"] \n")
244 .arg(v->toString())
245 .arg(v1->toString())
246 .arg(data->minSize)
247 .arg(data->minPrefSize)
248 .arg(data->prefSize)
249 .arg(data->maxPrefSize)
250 .arg(data->maxSize)
251 ;
252 }
253 }
254 strVertices += QString::fromLatin1("\"%1\" [label=\"%2\"]\n").arg(v->toString()).arg(v->toString());
255 }
256 return QString::fromLatin1("%1\n%2\n").arg(strVertices, edges);
257 }
258#endif
259
260protected:
261 void createDirectedEdge(Vertex *from, Vertex *to, EdgeData *data)
262 {
263 m_graph[from][to] = data;
264 }
265
266 void removeDirectedEdge(Vertex *from, Vertex *to)
267 {
268 const auto it = m_graph.find(from);
269 Q_ASSERT(it != m_graph.end());
270
271 it->remove(to);
272 if (it->isEmpty()) {
273 //nobody point to 'from' so we can remove it from the graph
274 m_graph.erase(it);
275 }
276 }
277
278private:
279 QHash<Vertex *, QHash<Vertex *, EdgeData *> > m_graph;
280};
281
282QT_END_NAMESPACE
283
284#endif
285