1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtGui module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #ifndef QGRAPH_P_H

    43 #define QGRAPH_P_H

    44 

    45 //

    46 //  W A R N I N G

    47 //  -------------

    48 //

    49 // This file is not part of the Qt API.  It exists purely as an

    50 // implementation detail.  This header file may change from version to

    51 // version without notice, or even be removed.

    52 //

    53 // We mean it.

    54 //

    55 

    56 #include <QtCore/QHash>

    57 #include <QtCore/QQueue>

    58 #include <QtCore/QString>

    59 #include <QtCore/QDebug>

    60 

    61 #include <float.h>

    62 

    63 QT_BEGIN_NAMESPACE

    64 

    65 template <typename Vertex, typename EdgeData>

    66 class Graph

    67 {

    68 public:

    69     Graph() {}

    70 

    71     class const_iterator {

    72     public:

    73         const_iterator(const Graph *graph, bool begin) : g(graph){

    74             if (begin) {

    75                 row = g->m_graph.constBegin();

    76                 //test if the graph is empty

    77                 if (row != g->m_graph.constEnd())

    78                 {

    79                     column = (*row)->constBegin();

    80                 }

    81             } else {

    82                 row = g->m_graph.constEnd();

    83             }

    84         }

    85 

    86         inline Vertex *operator*() {

    87             return column.key();

    88         }

    89 

    90         inline Vertex *from() const {

    91             return row.key();

    92         }

    93 

    94         inline Vertex *to() const {

    95             return column.key();

    96         }

    97 

    98         inline bool operator==(const const_iterator &o) const { return !(*this != o); }

    99         inline bool operator!=(const const_iterator &o) const {

   100            if (row ==  g->m_graph.end()) {

   101                 return row != o.row;

   102            } else {

   103                 return row != o.row || column != o.column;

   104            }

   105         }

   106         inline const_iterator& operator=(const const_iterator &o) const { row = o.row; column = o.column; return *this;}

   107 

   108         // prefix

   109         const_iterator &operator++() {

   110             if (row != g->m_graph.constEnd()) {

   111                 ++column;

   112                 if (column == (*row)->constEnd()) {

   113                     ++row;

   114                     if (row != g->m_graph.constEnd()) {

   115                         column = (*row)->constBegin();

   116                     }

   117                 }

   118             }

   119             return *this;

   120         }

   121 

   122     private:

   123         const Graph *g;

   124         Q_TYPENAME QHash<Vertex *, QHash<Vertex *, EdgeData *> * >::const_iterator row;

   125         Q_TYPENAME QHash<Vertex *, EdgeData *>::const_iterator column;

   126     };

   127 

   128     const_iterator constBegin() const {

   129         return const_iterator(this,true);

   130     }

   131 

   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      */

   143     EdgeData *edgeData(Vertex* first, Vertex* second) {

   144         QHash<Vertex *, EdgeData *> *row = m_graph.value(first);

   145         return row ? row->value(second) : 0;

   146     }

   147 

   148     void createEdge(Vertex *first, Vertex *second, EdgeData *data)

   149     {

   150         // Creates a bidirectional edge

   151 #if defined(QT_DEBUG) && 0

   152         qDebug("Graph::createEdge(): %s",

   153                qPrintable(QString::fromAscii("%1-%2")

   154                           .arg(first->toString()).arg(second->toString())));

   155 #endif

   156         if (edgeData(first, second)) {

   157 #ifdef QT_DEBUG

   158             qWarning("%s-%s already has an edge", qPrintable(first->toString()), qPrintable(second->toString()));

   159 #endif

   160         }

   161         createDirectedEdge(first, second, data);

   162         createDirectedEdge(second, first, data);

   163     }

   164 

   165     void removeEdge(Vertex *first, Vertex *second)

   166     {

   167         // Removes a bidirectional edge

   168 #if defined(QT_DEBUG) && 0

   169         qDebug("Graph::removeEdge(): %s",

   170                qPrintable(QString::fromAscii("%1-%2")

   171                           .arg(first->toString()).arg(second->toString())));

   172 #endif

   173         EdgeData *data = edgeData(first, second);

   174         removeDirectedEdge(first, second);

   175         removeDirectedEdge(second, first);

   176         if (data) delete data;

   177     }

   178 

   179     EdgeData *takeEdge(Vertex* first, Vertex* second)

   180     {

   181 #if defined(QT_DEBUG) && 0

   182         qDebug("Graph::takeEdge(): %s",

   183                qPrintable(QString::fromAscii("%1-%2")

   184                           .arg(first->toString()).arg(second->toString())));

   185 #endif

   186         // Removes a bidirectional edge

   187         EdgeData *data = edgeData(first, second);

   188         if (data) {

   189             removeDirectedEdge(first, second);

   190             removeDirectedEdge(second, first);

   191         }

   192         return data;

   193     }

   194 

   195     QList<Vertex *> adjacentVertices(Vertex *vertex) const

   196     {

   197         QHash<Vertex *, EdgeData *> *row = m_graph.value(vertex);

   198         QList<Vertex *> l;

   199         if (row)

   200             l = row->keys();

   201         return l;

   202     }

   203 

   204     void setRootVertex(Vertex *vertex)

   205     {

   206         userVertex = vertex;

   207     }

   208 

   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 

   217     QList<QPair<Vertex*, Vertex*> > connections() const {

   218         QList<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 (from < to) {

   224                 conns.append(qMakePair(from, to));

   225             }

   226         }

   227         return conns;

   228     }

   229 

   230 #if defined(QT_DEBUG)

   231     QString serializeToDot() {   // traversal

   232         QString strVertices;

   233         QString edges;

   234 

   235         QSet<Vertex *> setOfVertices = vertices();

   236         for (Q_TYPENAME QSet<Vertex*>::const_iterator it = setOfVertices.begin(); it != setOfVertices.end(); ++it) {

   237             Vertex *v = *it;

   238             QList<Vertex*> adjacents = adjacentVertices(v);

   239             for (int i = 0; i < adjacents.count(); ++i) {

   240                 Vertex *v1 = adjacents.at(i);

   241                 EdgeData *data = edgeData(v, v1);

   242                 bool forward = data->from == v;

   243                 if (forward) {

   244                     edges += QString::fromAscii("%1->%2 [label=\"[%3,%4,%5]\" dir=both color=\"#000000:#a0a0a0\"] \n")

   245                         .arg(v->toString())

   246                         .arg(v1->toString())

   247                         .arg(data->minSize)

   248                         .arg(data->prefSize)

   249                         .arg(data->maxSize)

   250                         ;

   251                 }

   252             }

   253             strVertices += QString::fromAscii("%1 [label=\"%2\"]\n").arg(v->toString()).arg(v->toString());

   254         }

   255         return QString::fromAscii("%1\n%2\n").arg(strVertices).arg(edges);

   256     }

   257 #endif

   258 

   259     Vertex *rootVertex() const

   260     {

   261         return userVertex;

   262     }

   263 

   264 protected:

   265     void createDirectedEdge(Vertex *from, Vertex *to, EdgeData *data)

   266     {

   267         QHash<Vertex *, EdgeData *> *adjacentToFirst = m_graph.value(from);

   268         if (!adjacentToFirst) {

   269             adjacentToFirst = new QHash<Vertex *, EdgeData *>();

   270             m_graph.insert(from, adjacentToFirst);

   271         }

   272         adjacentToFirst->insert(to, data);

   273     }

   274 

   275     void removeDirectedEdge(Vertex *from, Vertex *to)

   276     {

   277         QHash<Vertex *, EdgeData *> *adjacentToFirst = m_graph.value(from);

   278         Q_ASSERT(adjacentToFirst);

   279 

   280         adjacentToFirst->remove(to);

   281         if (adjacentToFirst->isEmpty()) {

   282             //nobody point to 'from' so we can remove it from the graph

   283             m_graph.remove(from);

   284             delete adjacentToFirst;

   285         }

   286     }

   287 

   288 private:

   289     Vertex *userVertex;

   290 

   291     QHash<Vertex *, QHash<Vertex *, EdgeData *> *> m_graph;

   292 };

   293 

   294 QT_END_NAMESPACE

   295 

   296 #endif