PARP Research Group

Universidad de Murcia

---

src/qvmath/qvdirectedgraph.h Go to the documentation of this file. /* * Copyright (C) 2011, 2012. PARP Research Group. * <http://perception.inf.um.es> * University of Murcia, Spain. * * This file is part of the QVision library. * * QVision is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation, version 3 of the License. * * QVision is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with QVision. If not, see <http://www.gnu.org/licenses/>. */ #ifndef QVDIRECTEDGRAPH_H #define QVDIRECTEDGRAPH_H #include <QPoint> #include <QHash> #include <QMap> #include <QVVector> #include <qvmath.h> typedef QPoint QVGraphLink; bool operator<(const QVGraphLink &link1, const QVGraphLink &link2); template <typename Element> class QVDirectedGraph: public QMap<QVGraphLink, Element> { private: int maxNodeIndex; public: QVVector getNodesConnectivity() const { QVVector result(maxNodesIndex()+1, 0.0); foreach(QVGraphLink link, this->keys()) { result[link.x()]++; result[link.y()]++; } return result; } int getMinConnectivity() const { return int(getNodesConnectivity().min()); } int getMaxConnectivity() const { return int(getNodesConnectivity().max()); } double getMeanConnectivity() const { return getNodesConnectivity().mean(); } /* enum ArrowHeadType { normal, inv, dot, invdot, odot, invodot, none, tee, empty, invempty, diamond, odiamond, ediamond, crow, box, obox, open, halfopen, vee }; typedef QFlags<ArrowHeadType> ArrowHeadTypes; */ QVDirectedGraph():QMap<QVGraphLink, Element>(), maxNodeIndex(0) { } void insert(const int source, const int destination, const Element element) { Q_ASSERT(source >= 0); Q_ASSERT(destination >= 0); maxNodeIndex = MAX(maxNodeIndex, MAX(source, destination)); QMap<QVGraphLink, Element>::insert(QVGraphLink(source, destination), element); } void insert(const QVGraphLink &link, const Element element) { Q_ASSERT(link.x() >= 0); Q_ASSERT(link.y() >= 0); maxNodeIndex = MAX(maxNodeIndex, MAX(link.x(), link.y())); QMap<QVGraphLink, Element>::insert(link, element); } Element operator [](const QVGraphLink &link) const { Q_ASSERT(link.x() >= 0); Q_ASSERT(link.y() >= 0); Q_ASSERT(link.x() <= maxNodeIndex); Q_ASSERT(link.y() <= maxNodeIndex); return QMap<QVGraphLink, Element>::operator[](link); } Element & operator [](const QVGraphLink &link) { Q_ASSERT(link.x() >= 0); Q_ASSERT(link.y() >= 0); maxNodeIndex = MAX(maxNodeIndex, MAX(link.x(), link.y())); return QMap<QVGraphLink, Element>::operator[](link); } inline const Element value(const int source, const int destination) const { Q_ASSERT(source >= 0); Q_ASSERT(destination >= 0); Q_ASSERT(source <= maxNodeIndex); Q_ASSERT(destination <= maxNodeIndex); return QMap<QVGraphLink, Element>::value(QVGraphLink(source, destination)); } inline bool contains(const int source, const int destination) const { return QMap<QVGraphLink, Element>::contains(QVGraphLink(source, destination)); } inline bool contains(const QVGraphLink &link) const { return QMap<QVGraphLink, Element>::contains(link); } QList<QVGraphLink> getLinks() const { return this->keys(); } void deleteInsufficientlyConnectedNodes(const int minConnections) { QMap<int, int> counts = numLinksPerNode(); while(true) { foreach( QVGraphLink p, this->keys() ) if ( (counts[p.x()] < minConnections) or (counts[p.y()] < minConnections) ) this->remove(p); QMap<int, int> newCounts = numLinksPerNode(); if (counts == newCounts) break; counts = newCounts; } } int numNodes() const { return numLinksPerNode().count(); } int maxNodesIndex() const { std::cout << "WARNING: 'QVDirectedGraph::maxNodesIndex' deprecated. Use 'QVDirectedGraph::getMaxNodeIndex' instead." << std::endl; int result = 0; foreach(QVGraphLink link, this->keys()) result = MAX(result, MAX(link.x(), link.y())); return result; } int getMaxNodeIndex() const { #ifdef DEBUG int temp = 0; foreach(QVGraphLink key, this->keys()) temp = MAX(temp, MAX(key.x(), key.y())); Q_ASSERT(maxNodeIndex == temp); Q_ASSERT(maxNodeIndex == maxNodesIndex()); #endif // DEBUG return maxNodeIndex; } QMap<int, int> numLinksForNode() const { std::cout << "WARNING: 'QVDirectedGraph::numLinksForNode' deprecated. Use 'QVDirectedGraph::numLinksPerNode' instead." << std::endl; return numLinksPerNode(); } QMap<int, int> numLinksPerNode() const { QMap<int, int> result; foreach(QVGraphLink link, this->keys()) { result[link.x()] ++; result[link.y()] ++; } return result; } }; #include <QStringList> bool writeGraphToDotFile(const QString &fileName, const QVDirectedGraph<QString> &graph, const QStringList &nodeLabels = QStringList()); #endif

---

QVision framework. PARP research group. Copyright © 2007, 2008, 2009, 2010, 2011.