Source/cmComputeComponentGraph.cxx

/*============================================================================
  CMake - Cross Platform Makefile Generator
  Copyright 2000-2009 Kitware, Inc., Insight Software Consortium

  Distributed under the OSI-approved BSD License (the "License");
  see accompanying file Copyright.txt for details.

  This software is distributed WITHOUT ANY WARRANTY; without even the
  implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  See the License for more information.
============================================================================*/
#include "cmComputeComponentGraph.h"

#include <algorithm>

#include <assert.h>

//----------------------------------------------------------------------------
cmComputeComponentGraph::cmComputeComponentGraph(Graph const& input):
  InputGraph(input)
{
  // Identify components.
  this->Tarjan();

  // Compute the component graph.
  this->ComponentGraph.resize(0);
  this->ComponentGraph.resize(this->Components.size());
  this->TransferEdges();
}

//----------------------------------------------------------------------------
cmComputeComponentGraph::~cmComputeComponentGraph()
{
}

//----------------------------------------------------------------------------
void cmComputeComponentGraph::Tarjan()
{
  int n = static_cast<int>(this->InputGraph.size());
  TarjanEntry entry = {0,0};
  this->TarjanEntries.resize(0);
  this->TarjanEntries.resize(n, entry);
  this->TarjanComponents.resize(0);
  this->TarjanComponents.resize(n, -1);
  this->TarjanWalkId = 0;
  this->TarjanVisited.resize(0);
  this->TarjanVisited.resize(n, 0);
  for(int i = 0; i < n; ++i)
    {
    // Start a new DFS from this node if it has never been visited.
    if(!this->TarjanVisited[i])
      {
      assert(this->TarjanStack.empty());
      ++this->TarjanWalkId;
      this->TarjanIndex = 0;
      this->TarjanVisit(i);
      }
    }
}

//----------------------------------------------------------------------------
void cmComputeComponentGraph::TarjanVisit(int i)
{
  // We are now visiting this node.
  this->TarjanVisited[i] = this->TarjanWalkId;

  // Initialize the entry.
  this->TarjanEntries[i].Root = i;
  this->TarjanComponents[i] = -1;
  this->TarjanEntries[i].VisitIndex = ++this->TarjanIndex;
  this->TarjanStack.push(i);

  // Follow outgoing edges.
  EdgeList const& nl = this->InputGraph[i];
  for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
    {
    int j = *ni;

    // Ignore edges to nodes that have been reached by a previous DFS
    // walk.  Since we did not reach the current node from that walk
    // it must not belong to the same component and it has already
    // been assigned to a component.
    if(this->TarjanVisited[j] > 0 &&
       this->TarjanVisited[j] < this->TarjanWalkId)
      {
      continue;
      }

    // Visit the destination if it has not yet been visited.
    if(!this->TarjanVisited[j])
      {
      this->TarjanVisit(j);
      }

    // If the destination has not yet been assigned to a component,
    // check if it has a better root for the current object.
    if(this->TarjanComponents[j] < 0)
      {
      if(this->TarjanEntries[this->TarjanEntries[j].Root].VisitIndex <
         this->TarjanEntries[this->TarjanEntries[i].Root].VisitIndex)
        {
        this->TarjanEntries[i].Root = this->TarjanEntries[j].Root;
        }
      }
    }

  // Check if we have found a component.
  if(this->TarjanEntries[i].Root == i)
    {
    // Yes.  Create it.
    int c = static_cast<int>(this->Components.size());
    this->Components.push_back(NodeList());
    NodeList& component = this->Components[c];

    // Populate the component list.
    int j;
    do
      {
      // Get the next member of the component.
      j = this->TarjanStack.top();
      this->TarjanStack.pop();

      // Assign the member to the component.
      this->TarjanComponents[j] = c;
      this->TarjanEntries[j].Root = i;

      // Store the node in its component.
      component.push_back(j);
      } while(j != i);

    // Sort the component members for clarity.
    std::sort(component.begin(), component.end());
    }
}

//----------------------------------------------------------------------------
void cmComputeComponentGraph::TransferEdges()
{
  // Map inter-component edges in the original graph to edges in the
  // component graph.
  int n = static_cast<int>(this->InputGraph.size());
  for(int i=0; i < n; ++i)
    {
    int i_component = this->TarjanComponents[i];
    EdgeList const& nl = this->InputGraph[i];
    for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
      {
      int j = *ni;
      int j_component = this->TarjanComponents[j];
      if(i_component != j_component)
        {
        // We do not attempt to combine duplicate edges, but instead
        // store the inter-component edges with suitable multiplicity.
        this->ComponentGraph[i_component].push_back(
          cmGraphEdge(j_component, ni->IsStrong()));
        }
      }
    }
}