Revision control
Copy as Markdown
// Copyright (C) 2016 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
// Qt-Security score:significant reason:default
#ifndef QGRAPH_P_H
#define QGRAPH_P_H
//
// W A R N I N G
// -------------
//
// This file is not part of the Qt API. It exists purely as an
// implementation detail. This header file may change from version to
// version without notice, or even be removed.
//
// We mean it.
//
#include <QtWidgets/private/qtwidgetsglobal_p.h>
#include <QtCore/QHash>
#include <QtCore/QQueue>
#include <QtCore/QString>
#include <QtCore/QSet>
#include <functional> // for std::less
#include <float.h>
QT_REQUIRE_CONFIG(graphicsview);
QT_BEGIN_NAMESPACE
template <typename Vertex, typename EdgeData>
class Graph
{
public:
Graph() {}
class const_iterator {
public:
const_iterator(const Graph *graph, bool begin) : g(graph){
if (begin) {
row = g->m_graph.constBegin();
//test if the graph is empty
if (row != g->m_graph.constEnd())
column = row->cbegin();
} else {
row = g->m_graph.constEnd();
}
}
inline Vertex *operator*() {
return column.key();
}
inline Vertex *from() const {
return row.key();
}
inline Vertex *to() const {
return column.key();
}
inline bool operator==(const const_iterator &o) const { return !(*this != o); }
inline bool operator!=(const const_iterator &o) const {
if (row == g->m_graph.end()) {
return row != o.row;
} else {
return row != o.row || column != o.column;
}
}
// prefix
const_iterator &operator++() {
if (row != g->m_graph.constEnd()) {
++column;
if (column == row->cend()) {
++row;
if (row != g->m_graph.constEnd()) {
column = row->cbegin();
}
}
}
return *this;
}
private:
const Graph *g;
typename QHash<Vertex *, QHash<Vertex *, EdgeData *> >::const_iterator row;
typename QHash<Vertex *, EdgeData *>::const_iterator column;
};
const_iterator constBegin() const {
return const_iterator(this,true);
}
const_iterator constEnd() const {
return const_iterator(this,false);
}
/*!
* \internal
*
* If there is an edge between \a first and \a second, it will return a structure
* containing the data associated with the edge, otherwise it will return 0.
*
*/
EdgeData *edgeData(Vertex* first, Vertex* second) {
const auto it = m_graph.constFind(first);
if (it == m_graph.cend())
return nullptr;
const auto jt = it->constFind(second);
if (jt == it->cend())
return nullptr;
return *jt;
}
void createEdge(Vertex *first, Vertex *second, EdgeData *data)
{
// Creates a bidirectional edge
#if defined(QT_DEBUG) && 0
qDebug("Graph::createEdge(): %s",
qPrintable(QString::fromLatin1("%1-%2")
.arg(first->toString()).arg(second->toString())));
#endif
if (edgeData(first, second)) {
#ifdef QT_DEBUG
qWarning("%s-%s already has an edge", qPrintable(first->toString()), qPrintable(second->toString()));
#endif
}
createDirectedEdge(first, second, data);
createDirectedEdge(second, first, data);
}
void removeEdge(Vertex *first, Vertex *second)
{
// Removes a bidirectional edge
#if defined(QT_DEBUG) && 0
qDebug("Graph::removeEdge(): %s",
qPrintable(QString::fromLatin1("%1-%2")
.arg(first->toString()).arg(second->toString())));
#endif
EdgeData *data = edgeData(first, second);
removeDirectedEdge(first, second);
removeDirectedEdge(second, first);
if (data) delete data;
}
EdgeData *takeEdge(Vertex* first, Vertex* second)
{
#if defined(QT_DEBUG) && 0
qDebug("Graph::takeEdge(): %s",
qPrintable(QString::fromLatin1("%1-%2")
.arg(first->toString()).arg(second->toString())));
#endif
// Removes a bidirectional edge
EdgeData *data = edgeData(first, second);
if (data) {
removeDirectedEdge(first, second);
removeDirectedEdge(second, first);
}
return data;
}
QList<Vertex *> adjacentVertices(Vertex *vertex) const
{
const auto it = m_graph.constFind(vertex);
if (it == m_graph.cend())
return QList<Vertex *>();
else
return it->keys();
}
QSet<Vertex*> vertices() const {
QSet<Vertex *> setOfVertices;
for (const_iterator it = constBegin(); it != constEnd(); ++it) {
setOfVertices.insert(*it);
}
return setOfVertices;
}
QList<std::pair<Vertex *, Vertex *>> connections() const
{
QList<std::pair<Vertex *, Vertex *>> conns;
for (const_iterator it = constBegin(); it != constEnd(); ++it) {
Vertex *from = it.from();
Vertex *to = it.to();
// do not return (from,to) *and* (to,from)
if (std::less<Vertex*>()(from, to))
conns.emplace_back(from, to);
}
return conns;
}
#if defined(QT_DEBUG)
QString serializeToDot() { // traversal
QString strVertices;
QString edges;
QSet<Vertex *> setOfVertices = vertices();
for (typename QSet<Vertex*>::const_iterator it = setOfVertices.begin(); it != setOfVertices.end(); ++it) {
Vertex *v = *it;
const QList<Vertex*> adjacents = adjacentVertices(v);
for (auto *v1 : adjacents) {
EdgeData *data = edgeData(v, v1);
bool forward = data->from == v;
if (forward) {
edges += QString::fromLatin1("\"%1\"->\"%2\" [label=\"[%3,%4,%5,%6,%7]\" color=\"#000000\"] \n")
.arg(v->toString())
.arg(v1->toString())
.arg(data->minSize)
.arg(data->minPrefSize)
.arg(data->prefSize)
.arg(data->maxPrefSize)
.arg(data->maxSize)
;
}
}
strVertices += QString::fromLatin1("\"%1\" [label=\"%2\"]\n").arg(v->toString()).arg(v->toString());
}
return QString::fromLatin1("%1\n%2\n").arg(strVertices, edges);
}
#endif
protected:
void createDirectedEdge(Vertex *from, Vertex *to, EdgeData *data)
{
m_graph[from][to] = data;
}
void removeDirectedEdge(Vertex *from, Vertex *to)
{
const auto it = m_graph.find(from);
Q_ASSERT(it != m_graph.end());
it->remove(to);
if (it->isEmpty()) {
//nobody point to 'from' so we can remove it from the graph
m_graph.erase(it);
}
}
private:
QHash<Vertex *, QHash<Vertex *, EdgeData *> > m_graph;
};
QT_END_NAMESPACE
#endif