Source/cmComputeComponentGraph.cxx

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