Source/cmComputeComponentGraph.cxx

   1 /* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
   2    file Copyright.txt or https://cmake.org/licensing for details.  */
   3 #include "cmComputeComponentGraph.h"
   4
   5 #include <algorithm>
   6 #include <cassert>
   7 #include <cstddef>
   8 #include <limits>
   9
  10 const size_t cmComputeComponentGraph::INVALID_COMPONENT =
  11   std::numeric_limits<size_t>::max();
  12
  13 cmComputeComponentGraph::cmComputeComponentGraph(Graph const& input)
  14   : InputGraph(input)
  15 {
  16 }
  17
  18 cmComputeComponentGraph::~cmComputeComponentGraph() = default;
  19
  20 void cmComputeComponentGraph::Compute()
  21 {
  22   // Identify components.
  23   this->Tarjan();
  24
  25   // Compute the component graph.
  26   this->ComponentGraph.resize(0);
  27   this->ComponentGraph.resize(this->Components.size());
  28   this->TransferEdges();
  29 }
  30
  31 void cmComputeComponentGraph::Tarjan()
  32 {
  33   size_t n = this->InputGraph.size();
  34   TarjanEntry entry = { 0, 0 };
  35   this->TarjanEntries.resize(0);
  36   this->TarjanEntries.resize(n, entry);
  37   this->TarjanComponents.resize(0);
  38   this->TarjanComponents.resize(n, INVALID_COMPONENT);
  39   this->TarjanWalkId = 0;
  40   this->TarjanVisited.resize(0);
  41   this->TarjanVisited.resize(n, 0);
  42   for (size_t i = 0; i < n; ++i) {
  43     // Start a new DFS from this node if it has never been visited.
  44     if (!this->TarjanVisited[i]) {
  45       assert(this->TarjanStack.empty());
  46       ++this->TarjanWalkId;
  47       this->TarjanIndex = 0;
  48       this->TarjanVisit(i);
  49     }
  50   }
  51 }
  52
  53 void cmComputeComponentGraph::TarjanVisit(size_t i)
  54 {
  55   // We are now visiting this node.
  56   this->TarjanVisited[i] = this->TarjanWalkId;
  57
  58   // Initialize the entry.
  59   this->TarjanEntries[i].Root = i;
  60   this->TarjanComponents[i] = INVALID_COMPONENT;
  61   this->TarjanEntries[i].VisitIndex = ++this->TarjanIndex;
  62   this->TarjanStack.push(i);
  63
  64   // Follow outgoing edges.
  65   EdgeList const& nl = this->InputGraph[i];
  66   for (cmGraphEdge const& ni : nl) {
  67     size_t j = ni;
  68
  69     // Ignore edges to nodes that have been reached by a previous DFS
  70     // walk.  Since we did not reach the current node from that walk
  71     // it must not belong to the same component and it has already
  72     // been assigned to a component.
  73     if (this->TarjanVisited[j] > 0 &&
  74         this->TarjanVisited[j] < this->TarjanWalkId) {
  75       continue;
  76     }
  77
  78     // Visit the destination if it has not yet been visited.
  79     if (!this->TarjanVisited[j]) {
  80       this->TarjanVisit(j);
  81     }
  82
  83     // If the destination has not yet been assigned to a component,
  84     // check if it has a better root for the current object.
  85     if (this->TarjanComponents[j] == INVALID_COMPONENT) {
  86       if (this->TarjanEntries[this->TarjanEntries[j].Root].VisitIndex <
  87           this->TarjanEntries[this->TarjanEntries[i].Root].VisitIndex) {
  88         this->TarjanEntries[i].Root = this->TarjanEntries[j].Root;
  89       }
  90     }
  91   }
  92
  93   // Check if we have found a component.
  94   if (this->TarjanEntries[i].Root == i) {
  95     // Yes.  Create it.
  96     size_t c = this->Components.size();
  97     this->Components.emplace_back();
  98     NodeList& component = this->Components[c];
  99
 100     // Populate the component list.
 101     size_t j;
 102     do {
 103       // Get the next member of the component.
 104       j = this->TarjanStack.top();
 105       this->TarjanStack.pop();
 106
 107       // Assign the member to the component.
 108       this->TarjanComponents[j] = c;
 109       this->TarjanEntries[j].Root = i;
 110
 111       // Store the node in its component.
 112       component.push_back(j);
 113     } while (j != i);
 114
 115     // Sort the component members for clarity.
 116     std::sort(component.begin(), component.end());
 117   }
 118 }
 119
 120 void cmComputeComponentGraph::TransferEdges()
 121 {
 122   // Map inter-component edges in the original graph to edges in the
 123   // component graph.
 124   size_t n = this->InputGraph.size();
 125   for (size_t i = 0; i < n; ++i) {
 126     size_t i_component = this->TarjanComponents[i];
 127     EdgeList const& nl = this->InputGraph[i];
 128     for (cmGraphEdge const& ni : nl) {
 129       size_t j = ni;
 130       size_t j_component = this->TarjanComponents[j];
 131       if (i_component != j_component) {
 132         // We do not attempt to combine duplicate edges, but instead
 133         // store the inter-component edges with suitable multiplicity.
 134         this->ComponentGraph[i_component].emplace_back(
 135           j_component, ni.IsStrong(), ni.IsCross(), ni.GetBacktrace());
 136       }
 137     }
 138   }
 139 }