1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkBoostExtractLargestComponent.cxx
5
6 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7 All rights reserved.
8 See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
9
10 This software is distributed WITHOUT ANY WARRANTY; without even
11 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12 PURPOSE. See the above copyright notice for more information.
13
14 =========================================================================*/
15 #include "vtkBoostExtractLargestComponent.h"
16
17 #include "vtkBoostConnectedComponents.h"
18 #include "vtkDataSetAttributes.h"
19 #include "vtkDirectedGraph.h"
20 #include "vtkExecutive.h"
21 #include "vtkExtractSelectedGraph.h"
22 #include "vtkGraph.h"
23 #include "vtkIdTypeArray.h"
24 #include "vtkInformation.h"
25 #include "vtkInformationVector.h"
26 #include "vtkIntArray.h"
27 #include "vtkObjectFactory.h"
28 #include "vtkSelection.h"
29 #include "vtkSelectionNode.h"
30 #include "vtkSmartPointer.h"
31 #include "vtkUndirectedGraph.h"
32
33 #include <algorithm>
34
35 vtkStandardNewMacro(vtkBoostExtractLargestComponent);
36
vtkBoostExtractLargestComponent()37 vtkBoostExtractLargestComponent::vtkBoostExtractLargestComponent()
38 {
39 this->InvertSelection = false;
40 }
41
RequestData(vtkInformation * vtkNotUsed (request),vtkInformationVector ** inputVector,vtkInformationVector * outputVector)42 int vtkBoostExtractLargestComponent::RequestData(vtkInformation* vtkNotUsed(request),
43 vtkInformationVector** inputVector, vtkInformationVector* outputVector)
44 {
45 // Get the info objects
46 vtkInformation* inInfo = inputVector[0]->GetInformationObject(0);
47 vtkInformation* outInfo = outputVector->GetInformationObject(0);
48
49 // Get the input and output
50 vtkGraph* input = vtkGraph::SafeDownCast(inInfo->Get(vtkDataObject::DATA_OBJECT()));
51
52 vtkGraph* output = vtkGraph::SafeDownCast(outInfo->Get(vtkDataObject::DATA_OBJECT()));
53
54 vtkSmartPointer<vtkGraph> inputCopy;
55 if (vtkDirectedGraph::SafeDownCast(input))
56 {
57 inputCopy = vtkSmartPointer<vtkDirectedGraph>::New();
58 }
59 else
60 {
61 inputCopy = vtkSmartPointer<vtkUndirectedGraph>::New();
62 }
63 inputCopy->ShallowCopy(input);
64
65 // Find all of the connected components
66 vtkSmartPointer<vtkBoostConnectedComponents> connectedComponents =
67 vtkSmartPointer<vtkBoostConnectedComponents>::New();
68 connectedComponents->SetInputData(inputCopy);
69 connectedComponents->Update();
70
71 vtkIntArray* components = vtkArrayDownCast<vtkIntArray>(
72 connectedComponents->GetOutput()->GetVertexData()->GetArray("component"));
73
74 // Create an array to store the count of the number of vertices
75 // in every component
76 int componentRange[2];
77 components->GetValueRange(componentRange);
78 std::vector<int> componentCount(componentRange[1] + 1);
79
80 for (vtkIdType i = 0; i < components->GetNumberOfTuples(); i++)
81 {
82 componentCount[components->GetValue(i)]++;
83 }
84
85 // Save the original counts
86 std::vector<int> originalComponentCount(componentCount.size());
87 std::copy(componentCount.begin(), componentCount.end(), originalComponentCount.begin());
88
89 // Sort in descending order
90 std::sort(componentCount.rbegin(), componentCount.rend());
91
92 // Find the original component ID of the component with the highest count
93 std::vector<int>::iterator it =
94 find(originalComponentCount.begin(), originalComponentCount.end(), componentCount[0]);
95
96 if (it == originalComponentCount.end())
97 {
98 vtkErrorMacro("Should never get to the end of the components!");
99 return 0;
100 }
101
102 int largestComponent = it - originalComponentCount.begin();
103
104 vtkDebugMacro("The largest component is " << largestComponent << " and it has "
105 << componentCount[0] << " vertices.");
106
107 // Put either the index of the vertices belonging to the largest connected component
108 // or the index of the vertices NOT the largest connected component (depending on the
109 // InververtSelection flag) into an array to be used to extract this part of the graph.
110 vtkSmartPointer<vtkIdTypeArray> ids = vtkSmartPointer<vtkIdTypeArray>::New();
111 for (vtkIdType i = 0; i < components->GetNumberOfTuples(); i++)
112 {
113 if (!this->InvertSelection)
114 {
115 if (components->GetValue(i) == largestComponent)
116 {
117 ids->InsertNextValue(i);
118 }
119 }
120 else
121 {
122 if (components->GetValue(i) != largestComponent)
123 {
124 ids->InsertNextValue(i);
125 }
126 }
127 }
128
129 vtkDebugMacro(<< ids->GetNumberOfTuples() << " values selected.");
130
131 // Mark all of the things in the graph that should be extracted
132 vtkSmartPointer<vtkSelection> selection = vtkSmartPointer<vtkSelection>::New();
133
134 vtkSmartPointer<vtkSelectionNode> node = vtkSmartPointer<vtkSelectionNode>::New();
135 selection->AddNode(node);
136 node->SetSelectionList(ids);
137 node->SetContentType(vtkSelectionNode::INDICES);
138 node->SetFieldType(vtkSelectionNode::VERTEX);
139
140 // Extract them
141 vtkSmartPointer<vtkExtractSelectedGraph> extractSelectedGraph =
142 vtkSmartPointer<vtkExtractSelectedGraph>::New();
143 extractSelectedGraph->SetInputData(0, inputCopy);
144 extractSelectedGraph->SetInputData(1, selection);
145 extractSelectedGraph->Update();
146
147 output->ShallowCopy(extractSelectedGraph->GetOutput());
148
149 return 1;
150 }
151
PrintSelf(ostream & os,vtkIndent indent)152 void vtkBoostExtractLargestComponent::PrintSelf(ostream& os, vtkIndent indent)
153 {
154 this->Superclass::PrintSelf(os, indent);
155
156 os << indent << "InvertSelection: " << this->InvertSelection << "\n";
157 }
158