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