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

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