qgraph_p.h

Go to the documentation of this file.

// 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
 
#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/QDebug>
#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);
    }
 
    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<QPair<Vertex *, Vertex *>> connections() const
    {
        QList<QPair<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.append(qMakePair(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