summaryrefslogtreecommitdiff
path: root/Source/cmComputeComponentGraph.h
diff options
context:
space:
mode:
Diffstat (limited to 'Source/cmComputeComponentGraph.h')
-rw-r--r--Source/cmComputeComponentGraph.h83
1 files changed, 83 insertions, 0 deletions
diff --git a/Source/cmComputeComponentGraph.h b/Source/cmComputeComponentGraph.h
new file mode 100644
index 000000000..a2ce946c1
--- /dev/null
+++ b/Source/cmComputeComponentGraph.h
@@ -0,0 +1,83 @@
+/*============================================================================
+ CMake - Cross Platform Makefile Generator
+ Copyright 2000-2009 Kitware, Inc., Insight Software Consortium
+
+ Distributed under the OSI-approved BSD License (the "License");
+ see accompanying file Copyright.txt for details.
+
+ This software is distributed WITHOUT ANY WARRANTY; without even the
+ implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ See the License for more information.
+============================================================================*/
+#ifndef cmComputeComponentGraph_h
+#define cmComputeComponentGraph_h
+
+#include "cmStandardIncludes.h"
+
+#include "cmGraphAdjacencyList.h"
+
+#include <stack>
+
+/** \class cmComputeComponentGraph
+ * \brief Analyze a graph to determine strongly connected components.
+ *
+ * Convert a directed graph into a directed acyclic graph whose nodes
+ * correspond to strongly connected components of the original graph.
+ *
+ * We use Tarjan's algorithm to enumerate the components efficiently.
+ * An advantage of this approach is that the components are identified
+ * in a topologically sorted order.
+ */
+class cmComputeComponentGraph
+{
+public:
+ // Represent the graph with an adjacency list.
+ typedef cmGraphNodeList NodeList;
+ typedef cmGraphEdgeList EdgeList;
+ typedef cmGraphAdjacencyList Graph;
+
+ cmComputeComponentGraph(Graph const& input);
+ ~cmComputeComponentGraph();
+
+ /** Get the adjacency list of the component graph. */
+ Graph const& GetComponentGraph() const
+ { return this->ComponentGraph; }
+ EdgeList const& GetComponentGraphEdges(int c) const
+ { return this->ComponentGraph[c]; }
+
+ /** Get map from component index to original node indices. */
+ std::vector<NodeList> const& GetComponents() const
+ { return this->Components; }
+ NodeList const& GetComponent(int c) const
+ { return this->Components[c]; }
+
+ /** Get map from original node index to component index. */
+ std::vector<int> const& GetComponentMap() const
+ { return this->TarjanComponents; }
+
+private:
+ void TransferEdges();
+
+ Graph const& InputGraph;
+ Graph ComponentGraph;
+
+ // Tarjan's algorithm.
+ struct TarjanEntry
+ {
+ int Root;
+ int VisitIndex;
+ };
+ int TarjanWalkId;
+ std::vector<int> TarjanVisited;
+ std::vector<int> TarjanComponents;
+ std::vector<TarjanEntry> TarjanEntries;
+ std::stack<int> TarjanStack;
+ int TarjanIndex;
+ void Tarjan();
+ void TarjanVisit(int i);
+
+ // Connected components.
+ std::vector<NodeList> Components;
+};
+
+#endif