1 /*============================================================================
2 CMake - Cross Platform Makefile Generator
3 Copyright 2000-2009 Kitware, Inc., Insight Software Consortium
5 Distributed under the OSI-approved BSD License (the "License");
6 see accompanying file Copyright.txt for details.
8 This software is distributed WITHOUT ANY WARRANTY; without even the
9 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
10 See the License for more information.
11 ============================================================================*/
12 #ifndef cmComputeComponentGraph_h
13 #define cmComputeComponentGraph_h
15 #include "cmStandardIncludes.h"
17 #include "cmGraphAdjacencyList.h"
21 /** \class cmComputeComponentGraph
22 * \brief Analyze a graph to determine strongly connected components.
24 * Convert a directed graph into a directed acyclic graph whose nodes
25 * correspond to strongly connected components of the original graph.
27 * We use Tarjan's algorithm to enumerate the components efficiently.
28 * An advantage of this approach is that the components are identified
29 * in a topologically sorted order.
31 class cmComputeComponentGraph
34 // Represent the graph with an adjacency list.
35 typedef cmGraphNodeList NodeList;
36 typedef cmGraphEdgeList EdgeList;
37 typedef cmGraphAdjacencyList Graph;
39 cmComputeComponentGraph(Graph const& input);
40 ~cmComputeComponentGraph();
42 /** Get the adjacency list of the component graph. */
43 Graph const& GetComponentGraph() const
44 { return this->ComponentGraph; }
45 EdgeList const& GetComponentGraphEdges(int c) const
46 { return this->ComponentGraph[c]; }
48 /** Get map from component index to original node indices. */
49 std::vector<NodeList> const& GetComponents() const
50 { return this->Components; }
51 NodeList const& GetComponent(int c) const
52 { return this->Components[c]; }
54 /** Get map from original node index to component index. */
55 std::vector<int> const& GetComponentMap() const
56 { return this->TarjanComponents; }
61 Graph const& InputGraph;
64 // Tarjan's algorithm.
71 std::vector<int> TarjanVisited;
72 std::vector<int> TarjanComponents;
73 std::vector<TarjanEntry> TarjanEntries;
74 std::stack<int> TarjanStack;
77 void TarjanVisit(int i);
79 // Connected components.
80 std::vector<NodeList> Components;