From 84b8b4a5b7581c4076bfbf1a19a324cb0561baae Mon Sep 17 00:00:00 2001 From: Hugo Lima Date: Wed, 3 Mar 2010 11:15:53 -0300 Subject: Remove Boost::graph dependence from ApiExtractor by using our own code for graph topological sort. --- graph.h | 68 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 68 insertions(+) create mode 100644 graph.h (limited to 'graph.h') 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 +* +* 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 +#include +#include +#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 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 topologicalSort() const; +private: + + struct GraphPrivate; + GraphPrivate* m_d; +}; + +#endif -- cgit v1.2.3