1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkBoostBiconnectedComponents.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 /*-------------------------------------------------------------------------
16 Copyright 2008 Sandia Corporation.
17 Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
18 the U.S. Government retains certain rights in this software.
19 -------------------------------------------------------------------------*/
20 #include "vtkBoostBiconnectedComponents.h"
21
22 #include "vtkCellData.h"
23 #include "vtkIdTypeArray.h"
24 #include "vtkInformation.h"
25 #include "vtkInformationVector.h"
26 #include "vtkObjectFactory.h"
27 #include "vtkOutEdgeIterator.h"
28 #include "vtkPointData.h"
29 #include "vtkSmartPointer.h"
30 #include "vtkVertexListIterator.h"
31
32 #include "vtkBoostGraphAdapter.h"
33 #include "vtkGraph.h"
34 #include <boost/graph/biconnected_components.hpp>
35 #include <boost/version.hpp>
36 #include <utility>
37 #include <vector>
38
39 using namespace boost;
40
41 vtkStandardNewMacro(vtkBoostBiconnectedComponents);
42
vtkBoostBiconnectedComponents()43 vtkBoostBiconnectedComponents::vtkBoostBiconnectedComponents()
44 {
45 this->OutputArrayName = nullptr;
46 }
47
~vtkBoostBiconnectedComponents()48 vtkBoostBiconnectedComponents::~vtkBoostBiconnectedComponents()
49 {
50 // release mem
51 this->SetOutputArrayName(nullptr);
52 }
53
RequestData(vtkInformation * vtkNotUsed (request),vtkInformationVector ** inputVector,vtkInformationVector * outputVector)54 int vtkBoostBiconnectedComponents::RequestData(vtkInformation* vtkNotUsed(request),
55 vtkInformationVector** inputVector, vtkInformationVector* outputVector)
56 {
57 // get the info objects
58 vtkInformation* inInfo = inputVector[0]->GetInformationObject(0);
59 vtkInformation* outInfo = outputVector->GetInformationObject(0);
60
61 // get the input and output
62 vtkUndirectedGraph* input =
63 vtkUndirectedGraph::SafeDownCast(inInfo->Get(vtkDataObject::DATA_OBJECT()));
64 vtkUndirectedGraph* output =
65 vtkUndirectedGraph::SafeDownCast(outInfo->Get(vtkDataObject::DATA_OBJECT()));
66
67 // Send the data to output.
68 output->ShallowCopy(input);
69
70 // Create edge biconnected component array.
71 // This will be populated directly by the boost algorithm.
72 vtkSmartPointer<vtkIntArray> edgeCompArr = vtkSmartPointer<vtkIntArray>::New();
73 edgeCompArr->SetNumberOfTuples(input->GetNumberOfEdges());
74 for (vtkIdType i = 0; i < input->GetNumberOfEdges(); ++i)
75 {
76 edgeCompArr->SetValue(i, -1);
77 }
78 if (this->OutputArrayName)
79 {
80 edgeCompArr->SetName(this->OutputArrayName);
81 }
82 else
83 {
84 edgeCompArr->SetName("biconnected component");
85 }
86 vtkGraphEdgePropertyMapHelper<vtkIntArray*> helper(edgeCompArr);
87
88 // Create vector of articulation points and set it up for insertion
89 // by the algorithm.
90 std::vector<vtkIdType> artPoints;
91 std::pair<size_t, std::back_insert_iterator<std::vector<vtkIdType>>> res(
92 0, std::back_inserter(artPoints));
93
94 // Call BGL biconnected_components.
95 // It appears that the signature for this
96 // algorithm has changed in 1.32, 1.33, and 1.34 ;p
97 #if BOOST_VERSION < 103300 // Boost 1.32.x
98 // TODO I have no idea what the 1.32 signature is suppose to be
99 // res = biconnected_components(
100 // output, helper, std::back_inserter(artPoints), vtkGraphIndexMap());
101 #elif BOOST_VERSION < 103400 // Boost 1.33.x
102 res = biconnected_components(output, helper, std::back_inserter(artPoints), vtkGraphIndexMap());
103 #else // Anything after Boost 1.34.x
104 res = biconnected_components(
105 output, helper, std::back_inserter(artPoints), vertex_index_map(vtkGraphIndexMap()));
106 #endif
107
108 size_t numComp = res.first;
109
110 // Assign component values to vertices based on the first edge.
111 // If isolated, assign a new value.
112 vtkSmartPointer<vtkIntArray> vertCompArr = vtkSmartPointer<vtkIntArray>::New();
113 if (this->OutputArrayName)
114 {
115 vertCompArr->SetName(this->OutputArrayName);
116 }
117 else
118 {
119 vertCompArr->SetName("biconnected component");
120 }
121 vertCompArr->SetNumberOfTuples(output->GetNumberOfVertices());
122 vtkSmartPointer<vtkVertexListIterator> vertIt = vtkSmartPointer<vtkVertexListIterator>::New();
123 vtkSmartPointer<vtkOutEdgeIterator> edgeIt = vtkSmartPointer<vtkOutEdgeIterator>::New();
124 output->GetVertices(vertIt);
125 while (vertIt->HasNext())
126 {
127 vtkIdType u = vertIt->Next();
128 output->GetOutEdges(u, edgeIt);
129 int comp = -1;
130 while (edgeIt->HasNext() && comp == -1)
131 {
132 vtkOutEdgeType e = edgeIt->Next();
133 int value = edgeCompArr->GetValue(e.Id);
134 comp = value;
135 }
136 if (comp == -1)
137 {
138 comp = static_cast<int>(numComp);
139 numComp++;
140 }
141 vertCompArr->SetValue(u, comp);
142 }
143
144 // Articulation points belong to multiple biconnected components.
145 // Indicate these by assigning a component value of -1.
146 // It belongs to whatever components its incident edges belong to.
147 std::vector<vtkIdType>::size_type i;
148 for (i = 0; i < artPoints.size(); i++)
149 {
150 vertCompArr->SetValue(artPoints[i], -1);
151 }
152
153 // Add edge and vertex component arrays to the output
154 output->GetEdgeData()->AddArray(edgeCompArr);
155 output->GetVertexData()->AddArray(vertCompArr);
156
157 return 1;
158 }
159
PrintSelf(ostream & os,vtkIndent indent)160 void vtkBoostBiconnectedComponents::PrintSelf(ostream& os, vtkIndent indent)
161 {
162 this->Superclass::PrintSelf(os, indent);
163
164 os << indent << "OutputArrayName: " << (this->OutputArrayName ? this->OutputArrayName : "(none)")
165 << endl;
166 }
167