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