summaryrefslogtreecommitdiffstats
path: root/Source/cmComputeComponentGraph.h
diff options
context:
space:
mode:
Diffstat (limited to 'Source/cmComputeComponentGraph.h')
-rw-r--r--Source/cmComputeComponentGraph.h87
1 files changed, 87 insertions, 0 deletions
diff --git a/Source/cmComputeComponentGraph.h b/Source/cmComputeComponentGraph.h
new file mode 100644
index 0000000..a75afcf
--- /dev/null
+++ b/Source/cmComputeComponentGraph.h
@@ -0,0 +1,87 @@
+/*=========================================================================
+
+ Program: CMake - Cross-Platform Makefile Generator
+ Module: $RCSfile$
+ Language: C++
+ Date: $Date$
+ Version: $Revision$
+
+ Copyright (c) 2002 Kitware, Inc., Insight Consortium. All rights reserved.
+ See Copyright.txt or http://www.cmake.org/HTML/Copyright.html for details.
+
+ This software is distributed WITHOUT ANY WARRANTY; without even
+ the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ PURPOSE. See the above copyright notices 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 cmGraphAdjacencyList Graph;
+
+ cmComputeComponentGraph(Graph const& input);
+ ~cmComputeComponentGraph();
+
+ /** Get the adjacency list of the component graph. */
+ Graph const& GetComponentGraph() const
+ { return this->ComponentGraph; }
+ NodeList 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