Source/cmComputeComponentGraph.h

   1 /*=========================================================================
   2
   3   Program:   CMake - Cross-Platform Makefile Generator
   4   Module:    $RCSfile: cmComputeComponentGraph.h,v $
   5   Language:  C++
   6   Date:      $Date: 2008-02-07 21:14:05 $
   7   Version:   $Revision: 1.1 $
   8
   9   Copyright (c) 2002 Kitware, Inc., Insight Consortium.  All rights reserved.
  10   See Copyright.txt or http://www.cmake.org/HTML/Copyright.html for details.
  11
  12      This software is distributed WITHOUT ANY WARRANTY; without even
  13      the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  14      PURPOSE.  See the above copyright notices for more information.
  15
  16 =========================================================================*/
  17 #ifndef cmComputeComponentGraph_h
  18 #define cmComputeComponentGraph_h
  19
  20 #include "cmStandardIncludes.h"
  21
  22 #include "cmGraphAdjacencyList.h"
  23
  24 #include <stack>
  25
  26 /** \class cmComputeComponentGraph
  27  * \brief Analyze a graph to determine strongly connected components.
  28  *
  29  * Convert a directed graph into a directed acyclic graph whose nodes
  30  * correspond to strongly connected components of the original graph.
  31  *
  32  * We use Tarjan's algorithm to enumerate the components efficiently.
  33  * An advantage of this approach is that the components are identified
  34  * in a topologically sorted order.
  35  */
  36 class cmComputeComponentGraph
  37 {
  38 public:
  39   // Represent the graph with an adjacency list.
  40   typedef cmGraphNodeList NodeList;
  41   typedef cmGraphAdjacencyList Graph;
  42
  43   cmComputeComponentGraph(Graph const& input);
  44   ~cmComputeComponentGraph();
  45
  46   /** Get the adjacency list of the component graph.  */
  47   Graph const& GetComponentGraph() const
  48     { return this->ComponentGraph; }
  49   NodeList const& GetComponentGraphEdges(int c) const
  50     { return this->ComponentGraph[c]; }
  51
  52   /** Get map from component index to original node indices.  */
  53   std::vector<NodeList> const& GetComponents() const
  54     { return this->Components; }
  55   NodeList const& GetComponent(int c) const
  56     { return this->Components[c]; }
  57
  58   /** Get map from original node index to component index.  */
  59   std::vector<int> const& GetComponentMap() const
  60     { return this->TarjanComponents; }
  61
  62 private:
  63   void TransferEdges();
  64
  65   Graph const& InputGraph;
  66   Graph ComponentGraph;
  67
  68   // Tarjan's algorithm.
  69   struct TarjanEntry
  70   {
  71     int Root;
  72     int VisitIndex;
  73   };
  74   int TarjanWalkId;
  75   std::vector<int> TarjanVisited;
  76   std::vector<int> TarjanComponents;
  77   std::vector<TarjanEntry> TarjanEntries;
  78   std::stack<int> TarjanStack;
  79   int TarjanIndex;
  80   void Tarjan();
  81   void TarjanVisit(int i);
  82
  83   // Connected components.
  84   std::vector<NodeList> Components;
  85 };
  86
  87 #endif