1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#ifndef QGRAPH_P_H
5#define QGRAPH_P_H
6
7//
8// W A R N I N G
9// -------------
10//
11// This file is not part of the Qt API. It exists purely as an
12// implementation detail. This header file may change from version to
13// version without notice, or even be removed.
14//
15// We mean it.
16//
17
18#include <QtWidgets/private/qtwidgetsglobal_p.h>
19#include <QtCore/QHash>
20#include <QtCore/QQueue>
21#include <QtCore/QString>
22#include <QtCore/QSet>
23
24#include <functional> // for std::less
25
26#include <float.h>
27
28QT_REQUIRE_CONFIG(graphicsview);
29
30QT_BEGIN_NAMESPACE
31
32template <typename Vertex, typename EdgeData>
33class Graph
34{
35public:
36 Graph() {}
37
38 class const_iterator {
39 public:
40 const_iterator(const Graph *graph, bool begin) : g(graph){
41 if (begin) {
42 row = g->m_graph.constBegin();
43 //test if the graph is empty
44 if (row != g->m_graph.constEnd())
45 column = row->cbegin();
46 } else {
47 row = g->m_graph.constEnd();
48 }
49 }
50
51 inline Vertex *operator*() {
52 return column.key();
53 }
54
55 inline Vertex *from() const {
56 return row.key();
57 }
58
59 inline Vertex *to() const {
60 return column.key();
61 }
62
63 inline bool operator==(const const_iterator &o) const { return !(*this != o); }
64 inline bool operator!=(const const_iterator &o) const {
65 if (row == g->m_graph.end()) {
66 return row != o.row;
67 } else {
68 return row != o.row || column != o.column;
69 }
70 }
71
72 // prefix
73 const_iterator &operator++() {
74 if (row != g->m_graph.constEnd()) {
75 ++column;
76 if (column == row->cend()) {
77 ++row;
78 if (row != g->m_graph.constEnd()) {
79 column = row->cbegin();
80 }
81 }
82 }
83 return *this;
84 }
85
86 private:
87 const Graph *g;
88 typename QHash<Vertex *, QHash<Vertex *, EdgeData *> >::const_iterator row;
89 typename QHash<Vertex *, EdgeData *>::const_iterator column;
90 };
91
92 const_iterator constBegin() const {
93 return const_iterator(this,true);
94 }
95
96 const_iterator constEnd() const {
97 return const_iterator(this,false);
98 }
99
100 /*!
101 * \internal
102 *
103 * If there is an edge between \a first and \a second, it will return a structure
104 * containing the data associated with the edge, otherwise it will return 0.
105 *
106 */
107 EdgeData *edgeData(Vertex* first, Vertex* second) {
108 const auto it = m_graph.constFind(first);
109 if (it == m_graph.cend())
110 return nullptr;
111 const auto jt = it->constFind(second);
112 if (jt == it->cend())
113 return nullptr;
114 return *jt;
115 }
116
117 void createEdge(Vertex *first, Vertex *second, EdgeData *data)
118 {
119 // Creates a bidirectional edge
120#if defined(QT_DEBUG) && 0
121 qDebug("Graph::createEdge(): %s",
122 qPrintable(QString::fromLatin1("%1-%2")
123 .arg(first->toString()).arg(second->toString())));
124#endif
125 if (edgeData(first, second)) {
126#ifdef QT_DEBUG
127 qWarning("%s-%s already has an edge", qPrintable(first->toString()), qPrintable(second->toString()));
128#endif
129 }
130 createDirectedEdge(from: first, to: second, data);
131 createDirectedEdge(from: second, to: first, data);
132 }
133
134 void removeEdge(Vertex *first, Vertex *second)
135 {
136 // Removes a bidirectional edge
137#if defined(QT_DEBUG) && 0
138 qDebug("Graph::removeEdge(): %s",
139 qPrintable(QString::fromLatin1("%1-%2")
140 .arg(first->toString()).arg(second->toString())));
141#endif
142 EdgeData *data = edgeData(first, second);
143 removeDirectedEdge(from: first, to: second);
144 removeDirectedEdge(from: second, to: first);
145 if (data) delete data;
146 }
147
148 EdgeData *takeEdge(Vertex* first, Vertex* second)
149 {
150#if defined(QT_DEBUG) && 0
151 qDebug("Graph::takeEdge(): %s",
152 qPrintable(QString::fromLatin1("%1-%2")
153 .arg(first->toString()).arg(second->toString())));
154#endif
155 // Removes a bidirectional edge
156 EdgeData *data = edgeData(first, second);
157 if (data) {
158 removeDirectedEdge(from: first, to: second);
159 removeDirectedEdge(from: second, to: first);
160 }
161 return data;
162 }
163
164 QList<Vertex *> adjacentVertices(Vertex *vertex) const
165 {
166 const auto it = m_graph.constFind(vertex);
167 if (it == m_graph.cend())
168 return QList<Vertex *>();
169 else
170 return it->keys();
171 }
172
173 QSet<Vertex*> vertices() const {
174 QSet<Vertex *> setOfVertices;
175 for (const_iterator it = constBegin(); it != constEnd(); ++it) {
176 setOfVertices.insert(*it);
177 }
178 return setOfVertices;
179 }
180
181 QList<std::pair<Vertex *, Vertex *>> connections() const
182 {
183 QList<std::pair<Vertex *, Vertex *>> conns;
184 for (const_iterator it = constBegin(); it != constEnd(); ++it) {
185 Vertex *from = it.from();
186 Vertex *to = it.to();
187 // do not return (from,to) *and* (to,from)
188 if (std::less<Vertex*>()(from, to))
189 conns.emplace_back(from, to);
190 }
191 return conns;
192 }
193
194#if defined(QT_DEBUG)
195 QString serializeToDot() { // traversal
196 QString strVertices;
197 QString edges;
198
199 QSet<Vertex *> setOfVertices = vertices();
200 for (typename QSet<Vertex*>::const_iterator it = setOfVertices.begin(); it != setOfVertices.end(); ++it) {
201 Vertex *v = *it;
202 const QList<Vertex*> adjacents = adjacentVertices(vertex: v);
203 for (auto *v1 : adjacents) {
204 EdgeData *data = edgeData(first: v, second: v1);
205 bool forward = data->from == v;
206 if (forward) {
207 edges += QString::fromLatin1(ba: "\"%1\"->\"%2\" [label=\"[%3,%4,%5,%6,%7]\" color=\"#000000\"] \n")
208 .arg(v->toString())
209 .arg(v1->toString())
210 .arg(data->minSize)
211 .arg(data->minPrefSize)
212 .arg(data->prefSize)
213 .arg(data->maxPrefSize)
214 .arg(data->maxSize)
215 ;
216 }
217 }
218 strVertices += QString::fromLatin1(ba: "\"%1\" [label=\"%2\"]\n").arg(v->toString()).arg(v->toString());
219 }
220 return QString::fromLatin1(ba: "%1\n%2\n").arg(args&: strVertices, args&: edges);
221 }
222#endif
223
224protected:
225 void createDirectedEdge(Vertex *from, Vertex *to, EdgeData *data)
226 {
227 m_graph[from][to] = data;
228 }
229
230 void removeDirectedEdge(Vertex *from, Vertex *to)
231 {
232 const auto it = m_graph.find(from);
233 Q_ASSERT(it != m_graph.end());
234
235 it->remove(to);
236 if (it->isEmpty()) {
237 //nobody point to 'from' so we can remove it from the graph
238 m_graph.erase(it);
239 }
240 }
241
242private:
243 QHash<Vertex *, QHash<Vertex *, EdgeData *> > m_graph;
244};
245
246QT_END_NAMESPACE
247
248#endif
249

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