diff options
author | Hugo Lima <hugo.lima@openbossa.org> | 2010-03-03 11:15:53 -0300 |
---|---|---|
committer | Hugo Lima <hugo.lima@openbossa.org> | 2010-03-03 17:34:39 -0300 |
commit | 84b8b4a5b7581c4076bfbf1a19a324cb0561baae (patch) | |
tree | 5d698234fe4b9b99a0dfb1da75b6dae90650e0f0 /graph.h | |
parent | 62dfdd85bbcac527be99183cfc8e8f7b92902f11 (diff) |
Remove Boost::graph dependence from ApiExtractor by using our own code
for graph topological sort.
Diffstat (limited to 'graph.h')
-rw-r--r-- | graph.h | 68 |
1 files changed, 68 insertions, 0 deletions
diff --git a/graph.h b/graph.h new file mode 100644 index 000000000..2cc0a8f43 --- /dev/null +++ b/graph.h @@ -0,0 +1,68 @@ +/* +* This file is part of the API Extractor project. +* +* Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies). +* +* Contact: PySide team <contact@pyside.org> +* +* This program is free software; you can redistribute it and/or +* modify it under the terms of the GNU General Public License +* version 2 as published by the Free Software Foundation. +* +* This program 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 +* General Public License for more details. +* +* You should have received a copy of the GNU General Public License +* along with this program; if not, write to the Free Software +* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA +* 02110-1301 USA +* +*/ + +#ifndef GRAPH_H +#define GRAPH_H + +#include <QLinkedList> +#include <QHash> +#include <QString> +#include "apiextractormacros.h" + +/// A graph that can have their nodes topologically sorted. +class APIEXTRACTOR_API Graph +{ +public: + /// Create a new graph with \p numNodes nodes. + Graph(int numNodes); + ~Graph(); + + /// Returns the numbed of nodes in this graph. + int nodeCount() const; + /// Returns true if the graph contains the edge from -> to + bool containsEdge(int from, int to); + /// Adds an edge to this graph. + void addEdge(int from, int to); + /// Removes an edge out of this graph. + void removeEdge(int from, int to); + /// Print this graph to stdout. + void dump() const; + /** + * Dumps a dot graph to a file named \p filename. + * \param nodeNames map used to translate node ids to human readable text. + * \param fileName file name where the output should be written. + */ + void dumpDot(const QHash<int, QString> nodeNames, const QString& fileName) const; + + /** + * Topologically sort this graph. + * \return A collection with all nodes topologically sorted or an empty collection if a ciclic dependency was found. + */ + QLinkedList<int> topologicalSort() const; +private: + + struct GraphPrivate; + GraphPrivate* m_d; +}; + +#endif |