/************************************************************************** ** ** Copyright (C) 2016 The Qt Company Ltd. ** Contact: http://www.qt.io/licensing/ ** ** This file is part of the Qt Installer Framework. ** ** $QT_BEGIN_LICENSE:LGPL21$ ** Commercial License Usage ** Licensees holding valid commercial Qt licenses may use this file in ** accordance with the commercial license agreement provided with the ** Software or, alternatively, in accordance with the terms contained in ** a written agreement between you and The Qt Company. For licensing terms ** and conditions see http://www.qt.io/terms-conditions. For further ** information use the contact form at http://www.qt.io/contact-us. ** ** GNU Lesser General Public License Usage ** Alternatively, this file may be used under the terms of the GNU Lesser ** General Public License version 2.1 or version 3 as published by the Free ** Software Foundation and appearing in the file LICENSE.LGPLv21 and ** LICENSE.LGPLv3 included in the packaging of this file. Please review the ** following information to ensure the GNU Lesser General Public License ** requirements will be met: https://www.gnu.org/licenses/lgpl.html and ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. ** ** As a special exception, The Qt Company gives you certain additional ** rights. These rights are described in The Qt Company LGPL Exception ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. ** ** $QT_END_LICENSE$ ** **************************************************************************/ #ifndef GRAPH_H #define GRAPH_H #include #include #include #include namespace QInstaller { template class Graph { public: inline Graph() {} explicit Graph(const QList &nodes) { addNodes(nodes); } const QList nodes() const { return m_graph.keys(); } void addNode(const T &node) { m_graph.insert(node, QSet()); } void addNodes(const QList &nodes) { foreach (const T &node, nodes) addNode(node); } QList edges(const T &node) const { return m_graph.value(node).toList(); } void addEdge(const T &node, const T &edge) { m_graph[node].insert(edge); } void addEdges(const T &node, const QList &edges) { foreach (const T &edge, edges) addEdge(node, edge); } bool hasCycle() const { return m_hasCycle; } QPair cycle() const { return m_cycle; } QList sort() const { QSet visitedNodes; QList resolvedNodes; m_hasCycle = false; m_cycle = qMakePair(T(), T()); foreach (const T &node, nodes()) visit(node, &resolvedNodes, &visitedNodes); return resolvedNodes; } QList sortReverse() const { QList result = sort(); std::reverse(result.begin(), result.end()); return result; } private: void visit(const T &node, QList *const resolvedNodes, QSet *const visitedNodes) const { if (m_hasCycle) return; // if we visited this node already if (visitedNodes->contains(node)) { // and if the node is already in the ordered list if (resolvedNodes->contains(node)) return; m_hasCycle = true; m_cycle.second = node; return; // if not yet in the ordered list, we detected a cycle } // mark this node as visited visitedNodes->insert(node); m_cycle.first = node; // recursively visit all adjacency foreach (const T &adjacency, edges(node)) visit(adjacency, resolvedNodes, visitedNodes); // append this node to the ordered list resolvedNodes->append(node); } private: mutable bool m_hasCycle; QHash > m_graph; mutable QPair m_cycle; }; } #endif // GRAPH_H