Source/cmComputeComponentGraph.cxx

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