Source/cmComputeComponentGraph.h

   1 /*============================================================================
   2   CMake - Cross Platform Makefile Generator
   3   Copyright 2000-2009 Kitware, Inc., Insight Software Consortium
   4
   5   Distributed under the OSI-approved BSD License (the "License");
   6   see accompanying file Copyright.txt for details.
   7
   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
  14
  15 #include "cmStandardIncludes.h"
  16
  17 #include "cmGraphAdjacencyList.h"
  18
  19 #include <stack>
  20
  21 /** \class cmComputeComponentGraph
  22  * \brief Analyze a graph to determine strongly connected components.
  23  *
  24  * Convert a directed graph into a directed acyclic graph whose nodes
  25  * correspond to strongly connected components of the original graph.
  26  *
  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.
  30  */
  31 class cmComputeComponentGraph
  32 {
  33 public:
  34   // Represent the graph with an adjacency list.
  35   typedef cmGraphNodeList NodeList;
  36   typedef cmGraphEdgeList EdgeList;
  37   typedef cmGraphAdjacencyList Graph;
  38
  39   cmComputeComponentGraph(Graph const& input);
  40   ~cmComputeComponentGraph();
  41
  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]; }
  47
  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]; }
  53
  54   /** Get map from original node index to component index.  */
  55   std::vector<int> const& GetComponentMap() const
  56     { return this->TarjanComponents; }
  57
  58 private:
  59   void TransferEdges();
  60
  61   Graph const& InputGraph;
  62   Graph ComponentGraph;
  63
  64   // Tarjan's algorithm.
  65   struct TarjanEntry
  66   {
  67     int Root;
  68     int VisitIndex;
  69   };
  70   int TarjanWalkId;
  71   std::vector<int> TarjanVisited;
  72   std::vector<int> TarjanComponents;
  73   std::vector<TarjanEntry> TarjanEntries;
  74   std::stack<int> TarjanStack;
  75   int TarjanIndex;
  76   void Tarjan();
  77   void TarjanVisit(int i);
  78
  79   // Connected components.
  80   std::vector<NodeList> Components;
  81 };
  82
  83 #endif