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 64 QT_REQUIRE_CONFIG(graphicsview); 65 66 QT_BEGIN_NAMESPACE 67 68 template <typename Vertex, typename EdgeData> 69 class Graph 70 { 71 public: Graph()72 Graph() {} 73 74 class const_iterator { 75 public: const_iterator(const Graph * graph,bool begin)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 from()91 inline Vertex *from() const { 92 return row.key(); 93 } 94 to()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 constBegin()128 const_iterator constBegin() const { 129 return const_iterator(this,true); 130 } 131 constEnd()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 */ edgeData(Vertex * first,Vertex * second)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 createEdge(Vertex * first,Vertex * second,EdgeData * data)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 removeEdge(Vertex * first,Vertex * second)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 takeEdge(Vertex * first,Vertex * second)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 adjacentVertices(Vertex * vertex)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 vertices()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 connections()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) serializeToDot()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(v); 238 for (auto *v1 : adjacents) { 239 EdgeData *data = edgeData(v, v1); 240 bool forward = data->from == v; 241 if (forward) { 242 edges += QString::fromLatin1("\"%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("\"%1\" [label=\"%2\"]\n").arg(v->toString()).arg(v->toString()); 254 } 255 return QString::fromLatin1("%1\n%2\n").arg(strVertices, edges); 256 } 257 #endif 258 259 protected: createDirectedEdge(Vertex * from,Vertex * to,EdgeData * data)260 void createDirectedEdge(Vertex *from, Vertex *to, EdgeData *data) 261 { 262 m_graph[from][to] = data; 263 } 264 removeDirectedEdge(Vertex * from,Vertex * to)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 277 private: 278 QHash<Vertex *, QHash<Vertex *, EdgeData *> > m_graph; 279 }; 280 281 QT_END_NAMESPACE 282 283 #endif 284