Source/cmComputeComponentGraph.h

   1 /* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
   2    file Copyright.txt or https://cmake.org/licensing for details.  */
   3 #pragma once
   4
   5 #include "cmConfigure.h" // IWYU pragma: keep
   6
   7 #include <stack>
   8 #include <vector>
   9
  10 #include "cmGraphAdjacencyList.h"
  11
  12 /** \class cmComputeComponentGraph
  13  * \brief Analyze a graph to determine strongly connected components.
  14  *
  15  * Convert a directed graph into a directed acyclic graph whose nodes
  16  * correspond to strongly connected components of the original graph.
  17  *
  18  * We use Tarjan's algorithm to enumerate the components efficiently.
  19  * An advantage of this approach is that the components are identified
  20  * in a topologically sorted order.
  21  */
  22 class cmComputeComponentGraph
  23 {
  24 public:
  25   // Represent the graph with an adjacency list.
  26   using NodeList = cmGraphNodeList;
  27   using EdgeList = cmGraphEdgeList;
  28   using Graph = cmGraphAdjacencyList;
  29
  30   cmComputeComponentGraph(Graph const& input);
  31   ~cmComputeComponentGraph();
  32
  33   /** Run the computation.  */
  34   void Compute();
  35
  36   /** Get the adjacency list of the component graph.  */
  37   Graph const& GetComponentGraph() const { return this->ComponentGraph; }
  38   EdgeList const& GetComponentGraphEdges(int c) const
  39   {
  40     return this->ComponentGraph[c];
  41   }
  42
  43   /** Get map from component index to original node indices.  */
  44   std::vector<NodeList> const& GetComponents() const
  45   {
  46     return this->Components;
  47   }
  48   NodeList const& GetComponent(int c) const { return this->Components[c]; }
  49
  50   /** Get map from original node index to component index.  */
  51   std::vector<int> const& GetComponentMap() const
  52   {
  53     return this->TarjanComponents;
  54   }
  55
  56 private:
  57   void TransferEdges();
  58
  59   Graph const& InputGraph;
  60   Graph ComponentGraph;
  61
  62   // Tarjan's algorithm.
  63   struct TarjanEntry
  64   {
  65     int Root;
  66     int VisitIndex;
  67   };
  68   std::vector<int> TarjanVisited;
  69   std::vector<int> TarjanComponents;
  70   std::vector<TarjanEntry> TarjanEntries;
  71   std::vector<NodeList> Components;
  72   std::stack<int> TarjanStack;
  73   int TarjanWalkId;
  74   int TarjanIndex;
  75   void Tarjan();
  76   void TarjanVisit(int i);
  77
  78   // Connected components.
  79 };