vtkBoostExtractLargestComponent.cxx 5.29 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
/*=========================================================================

  Program:   Visualization Toolkit
  Module:    vtkBoostExtractLargestComponent.cxx

  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.

     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
     PURPOSE.  See the above copyright notice for more information.

=========================================================================*/
#include "vtkBoostExtractLargestComponent.h"

#include "vtkBoostConnectedComponents.h"
#include "vtkDataSetAttributes.h"
#include "vtkDirectedGraph.h"
#include "vtkExecutive.h"
#include "vtkExtractSelectedGraph.h"
#include "vtkGraph.h"
#include "vtkIdTypeArray.h"
#include "vtkInformation.h"
#include "vtkInformationVector.h"
#include "vtkIntArray.h"
#include "vtkObjectFactory.h"
#include "vtkSmartPointer.h"
#include "vtkSelection.h"
#include "vtkSelectionNode.h"
#include "vtkUndirectedGraph.h"

#include <algorithm>

vtkStandardNewMacro(vtkBoostExtractLargestComponent);

vtkBoostExtractLargestComponent::vtkBoostExtractLargestComponent()
{
  this->InvertSelection = false;
}

int vtkBoostExtractLargestComponent::RequestData(vtkInformation *vtkNotUsed(request),
                                         vtkInformationVector **inputVector,
                                         vtkInformationVector *outputVector)
{
  // Get the info objects
  vtkInformation *inInfo = inputVector[0]->GetInformationObject(0);
  vtkInformation *outInfo = outputVector->GetInformationObject(0);

luz.paz's avatar
luz.paz committed
50
  // Get the input and output
51 52 53 54 55 56 57 58
  vtkGraph* input = vtkGraph::SafeDownCast(
      inInfo->Get(vtkDataObject::DATA_OBJECT()));

  vtkGraph* output = vtkGraph::SafeDownCast(
      outInfo->Get(vtkDataObject::DATA_OBJECT()));

  vtkSmartPointer<vtkGraph> inputCopy;
  if (vtkDirectedGraph::SafeDownCast(input))
59
  {
60
    inputCopy = vtkSmartPointer<vtkDirectedGraph>::New();
61
  }
62
  else
63
  {
64
    inputCopy = vtkSmartPointer<vtkUndirectedGraph>::New();
65
  }
66 67 68 69 70
  inputCopy->ShallowCopy(input);

  // Find all of the connected components
  vtkSmartPointer<vtkBoostConnectedComponents> connectedComponents =
    vtkSmartPointer<vtkBoostConnectedComponents>::New();
71
  connectedComponents->SetInputData(inputCopy);
72 73
  connectedComponents->Update();

74
  vtkIntArray* components = vtkArrayDownCast<vtkIntArray>(
75 76 77 78
    connectedComponents->GetOutput()->GetVertexData()->GetArray("component"));

  // Create an array to store the count of the number of vertices
  // in every component
79 80
  int componentRange[2];
  components->GetValueRange(componentRange);
David Doria's avatar
David Doria committed
81
  std::vector<int> componentCount(componentRange[1] + 1);
82 83

  for(vtkIdType i = 0; i < components->GetNumberOfTuples(); i++)
84
  {
85
    componentCount[components->GetValue(i)]++;
86
  }
87 88 89 90 91 92 93 94 95 96 97 98 99

  // Save the original counts
  std::vector<int> originalComponentCount(componentCount.size());
  std::copy(componentCount.begin(), componentCount.end(), originalComponentCount.begin());

  // Sort in descending order
  std::sort(componentCount.rbegin(), componentCount.rend());

  // Find the original component ID of the component with the highest count
  std::vector<int>::iterator it = find(originalComponentCount.begin(),
    originalComponentCount.end(), componentCount[0]);

  if(it == originalComponentCount.end())
100
  {
101 102
    vtkErrorMacro("Should never get to the end of the components!");
    return 0;
103
  }
104 105 106 107 108 109 110 111 112 113 114 115

  int largestComponent = it - originalComponentCount.begin();

  vtkDebugMacro("The largest component is " << largestComponent
      << " and it has " << componentCount[0] << " vertices.");

  // Put either the index of the vertices belonging to the largest connected component
  // or the index of the vertices NOT the largest connected component (depending on the
  // InververtSelection flag) into an array to be used to extract this part of the graph.
  vtkSmartPointer<vtkIdTypeArray> ids =
    vtkSmartPointer<vtkIdTypeArray>::New();
  for(vtkIdType i = 0; i < components->GetNumberOfTuples(); i++)
116
  {
117
    if(!this->InvertSelection)
118
    {
119
      if(components->GetValue(i) == largestComponent)
120
      {
121 122
        ids->InsertNextValue(i);
      }
123
    }
124
    else
125
    {
126
      if(components->GetValue(i) != largestComponent)
127
      {
128 129 130
        ids->InsertNextValue(i);
      }
    }
131
  }
132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148

  vtkDebugMacro(<< ids->GetNumberOfTuples() << " values selected.");

  // Mark all of the things in the graph that should be extracted
  vtkSmartPointer<vtkSelection> selection =
      vtkSmartPointer<vtkSelection>::New();

  vtkSmartPointer<vtkSelectionNode> node =
    vtkSmartPointer<vtkSelectionNode>::New();
  selection->AddNode(node);
  node->SetSelectionList(ids);
  node->SetContentType(vtkSelectionNode::INDICES);
  node->SetFieldType(vtkSelectionNode::VERTEX);

  // Extract them
  vtkSmartPointer<vtkExtractSelectedGraph> extractSelectedGraph =
    vtkSmartPointer<vtkExtractSelectedGraph>::New();
149 150
  extractSelectedGraph->SetInputData(0, inputCopy);
  extractSelectedGraph->SetInputData(1, selection);
151 152 153 154 155 156 157 158 159 160 161 162 163
  extractSelectedGraph->Update();

  output->ShallowCopy(extractSelectedGraph->GetOutput());

  return 1;
}

void vtkBoostExtractLargestComponent::PrintSelf(ostream& os, vtkIndent indent)
{
  this->Superclass::PrintSelf(os,indent);

  os << indent << "InvertSelection: " << this->InvertSelection << "\n";
}