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