1 /**************************************************************************** 2 ** 3 ** Copyright (C) 2016 The Qt Company Ltd. 4 ** Contact: https://www.qt.io/licensing/ 5 ** 6 ** This file is part of Qt for Python. 7 ** 8 ** $QT_BEGIN_LICENSE:GPL-EXCEPT$ 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 General Public License Usage 18 ** Alternatively, this file may be used under the terms of the GNU 19 ** General Public License version 3 as published by the Free Software 20 ** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT 21 ** included in the packaging of this file. Please review the following 22 ** information to ensure the GNU General Public License requirements will 23 ** be met: https://www.gnu.org/licenses/gpl-3.0.html. 24 ** 25 ** $QT_END_LICENSE$ 26 ** 27 ****************************************************************************/ 28 29 #ifndef GRAPH_H 30 #define GRAPH_H 31 32 #include <QVector> 33 #include <QHash> 34 #include <QString> 35 36 /// A graph that can have their nodes topologically sorted. 37 class Graph 38 { 39 public: 40 Q_DISABLE_COPY(Graph) 41 42 using Indexes = QVector<int>; 43 44 /// Create a new graph with \p numNodes nodes. 45 Graph(int numNodes); 46 ~Graph(); 47 48 /// Returns the numbed of nodes in this graph. 49 int nodeCount() const; 50 /// Returns true if the graph contains the edge from -> to 51 bool containsEdge(int from, int to); 52 /// Adds an edge to this graph. 53 void addEdge(int from, int to); 54 /// Removes an edge out of this graph. 55 void removeEdge(int from, int to); 56 /// Print this graph to stdout. 57 void dump() const; 58 /** 59 * Dumps a dot graph to a file named \p filename. 60 * \param nodeNames map used to translate node ids to human readable text. 61 * \param fileName file name where the output should be written. 62 */ 63 void dumpDot(const QHash<int, QString>& nodeNames, const QString& fileName) const; 64 65 /** 66 * Topologically sort this graph. 67 * \return A collection with all nodes topologically sorted or an empty collection if a cyclic 68 * dependency was found. 69 */ 70 Indexes topologicalSort() const; 71 private: 72 73 struct GraphPrivate; 74 GraphPrivate* m_d; 75 }; 76 77 #endif 78