1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkPBGLBreadthFirstSearch.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 /*-------------------------------------------------------------------------
17 Copyright 2008 Sandia Corporation.
18 Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
19 the U.S. Government retains certain rights in this software.
20 -------------------------------------------------------------------------*/
21 /*
22 * Copyright (C) 2008 The Trustees of Indiana University.
23 * Use, modification and distribution is subject to the Boost Software
24 * License, Version 1.0. (See http://www.boost.org/LICENSE_1_0.txt)
25 */
26 #include "vtkPBGLBreadthFirstSearch.h"
27
28 #if !defined(VTK_LEGACY_REMOVE)
29
30 #include "vtkBoostGraphAdapter.h"
31 #include "vtkCellArray.h"
32 #include "vtkCellData.h"
33 #include "vtkConvertSelection.h"
34 #include "vtkDataArray.h"
35 #include "vtkDirectedGraph.h"
36 #include "vtkDistributedGraphHelper.h"
37 #include "vtkFloatArray.h"
38 #include "vtkInformation.h"
39 #include "vtkInformationVector.h"
40 #include "vtkMath.h"
41 #include "vtkObjectFactory.h"
42 #include "vtkPBGLDistributedGraphHelper.h"
43 #include "vtkPBGLGraphAdapter.h"
44 #include "vtkPointData.h"
45 #include "vtkSelection.h"
46 #include "vtkSelectionNode.h"
47 #include "vtkSmartPointer.h"
48 #include "vtkStreamingDemandDrivenPipeline.h"
49 #include "vtkStringArray.h"
50 #include "vtkUndirectedGraph.h"
51
52 #include <boost/graph/use_mpi.hpp> // must precede all pbgl includes
53 #include <boost/graph/breadth_first_search.hpp>
54 #include <boost/graph/distributed/breadth_first_search.hpp>
55 #include <boost/graph/parallel/algorithm.hpp>
56 #include <boost/graph/visitors.hpp>
57 #include <boost/property_map/property_map.hpp>
58 #include <boost/property_map/vector_property_map.hpp>
59 #include <boost/pending/queue.hpp>
60
61 #include <vtksys/stl/utility> // for pair
62
63 using namespace boost;
64
65 vtkStandardNewMacro(vtkPBGLBreadthFirstSearch);
66
67 // Redefine the bfs visitor, the only visitor we
68 // are using is the tree_edge visitor.
69 template <typename DistanceMap>
70 class pbgl_bfs_distance_recorder : public default_bfs_visitor
71 {
72 public:
pbgl_bfs_distance_recorder()73 pbgl_bfs_distance_recorder() { }
pbgl_bfs_distance_recorder(DistanceMap dist,vtkIdType * far)74 pbgl_bfs_distance_recorder(DistanceMap dist, vtkIdType* far)
75 : d(dist), far_vertex(far), far_dist(-1) { *far_vertex = -1; }
76
77 template <typename Vertex, typename Graph>
examine_vertex(Vertex v,const Graph & vtkNotUsed (g))78 void examine_vertex(Vertex v, const Graph& vtkNotUsed(g))
79 {
80 if (get(d, v) > far_dist)
81 {
82 *far_vertex = v;
83 far_dist = get(d, v);
84 }
85 }
86
87 template <typename Edge, typename Graph>
tree_edge(Edge e,const Graph & g)88 void tree_edge(Edge e, const Graph& g)
89 {
90 typename graph_traits<Graph>::vertex_descriptor
91 u = source(e, g), v = target(e, g);
92 put(d, v, get(d, u) + 1);
93 }
94
95 private:
96 DistanceMap d;
97 vtkIdType* far_vertex;
98 vtkIdType far_dist;
99 };
100
101 // Function object used to reduce (vertex, distance) pairs to find
102 // the furthest vertex. This ordering favors vertices on processors
103 // with a lower rank. Used only for the Parallel BGL breadth-first
104 // search.
105 class furthest_vertex
106 {
107 public:
furthest_vertex()108 furthest_vertex() : graph(0) { }
109
furthest_vertex(vtkGraph * g)110 furthest_vertex(vtkGraph *g) : graph(g) { }
111
operator ()(std::pair<vtkIdType,int> x,std::pair<vtkIdType,int> y) const112 std::pair<vtkIdType, int> operator()(std::pair<vtkIdType, int> x, std::pair<vtkIdType, int> y) const
113 {
114 vtkDistributedGraphHelper *helper = graph->GetDistributedGraphHelper();
115 if (x.second > y.second
116 || (x.second == y.second
117 && helper->GetVertexOwner(x.first) < helper->GetVertexOwner(y.first))
118 || (x.second == y.second
119 && helper->GetVertexOwner(x.first) == helper->GetVertexOwner(y.first)
120 && helper->GetVertexIndex(x.first) < helper->GetVertexIndex(y.first)))
121 {
122 return x;
123 }
124 else
125 {
126 return y;
127 }
128 }
129
130 private:
131 vtkGraph *graph;
132 };
133
134 // Constructor/Destructor
vtkPBGLBreadthFirstSearch()135 vtkPBGLBreadthFirstSearch::vtkPBGLBreadthFirstSearch()
136 {
137 // Default values for the origin vertex
138 this->OriginVertexIndex = 0;
139 this->InputArrayName = 0;
140 this->OutputArrayName = 0;
141 this->OutputSelectionType = 0;
142 this->SetOutputSelectionType("MAX_DIST_FROM_ROOT");
143 this->OriginValue = -1;
144 this->OutputSelection = false;
145 this->OriginFromSelection = false;
146 this->SetNumberOfInputPorts(2);
147 this->SetNumberOfOutputPorts(2);
148
149 VTK_LEGACY_BODY(vtkPBGLBreadthFirstSearch::vtkPBGLBreadthFirstSearch, "VTK 6.2");
150 }
151
~vtkPBGLBreadthFirstSearch()152 vtkPBGLBreadthFirstSearch::~vtkPBGLBreadthFirstSearch()
153 {
154 this->SetInputArrayName(0);
155 this->SetOutputArrayName(0);
156 }
157
SetOriginSelection(vtkSelection * s)158 void vtkPBGLBreadthFirstSearch::SetOriginSelection(vtkSelection* s)
159 {
160 this->SetInputData(s);
161 }
162
163 // Description:
164 // Set the index (into the vertex array) of the
165 // breadth first search 'origin' vertex.
SetOriginVertex(vtkIdType index)166 void vtkPBGLBreadthFirstSearch::SetOriginVertex(vtkIdType index)
167 {
168 this->OriginVertexIndex = index;
169 this->InputArrayName = NULL; // Reset any origin set by another method
170 this->Modified();
171 }
172
173 // Description:
174 // Set the breadth first search 'origin' vertex.
175 // This method is basically the same as above
176 // but allows the application to simply specify
177 // an array name and value, instead of having to
178 // know the specific index of the vertex.
SetOriginVertex(vtkStdString arrayName,vtkVariant value)179 void vtkPBGLBreadthFirstSearch::SetOriginVertex(
180 vtkStdString arrayName, vtkVariant value)
181 {
182 this->SetInputArrayName(arrayName);
183 this->OriginValue = value;
184 this->Modified();
185 }
186
SetOriginVertexString(char * arrayName,char * value)187 void vtkPBGLBreadthFirstSearch::SetOriginVertexString(
188 char* arrayName, char* value)
189 {
190 this->SetOriginVertex(arrayName, value);
191 }
192
GetVertexIndex(vtkAbstractArray * abstract,vtkVariant value)193 vtkIdType vtkPBGLBreadthFirstSearch::GetVertexIndex(
194 vtkAbstractArray *abstract,vtkVariant value)
195 {
196
197 // Okay now what type of array is it
198 if (abstract->IsNumeric())
199 {
200 vtkDataArray *dataArray = vtkDataArray::SafeDownCast(abstract);
201 int intValue = value.ToInt();
202 for(int i=0; i<dataArray->GetNumberOfTuples(); ++i)
203 {
204 if (intValue == static_cast<int>(dataArray->GetTuple1(i)))
205 {
206 return i;
207 }
208 }
209 }
210 else
211 {
212 vtkStringArray *stringArray = vtkStringArray::SafeDownCast(abstract);
213 vtkStdString stringValue(value.ToString());
214 for(int i=0; i<stringArray->GetNumberOfTuples(); ++i)
215 {
216 if (stringValue == stringArray->GetValue(i))
217 {
218 return i;
219 }
220 }
221 }
222
223 // Failed
224 vtkErrorMacro("Did not find a valid vertex index...");
225 return 0;
226 }
227
228
RequestData(vtkInformation * vtkNotUsed (request),vtkInformationVector ** inputVector,vtkInformationVector * outputVector)229 int vtkPBGLBreadthFirstSearch::RequestData(
230 vtkInformation *vtkNotUsed(request),
231 vtkInformationVector **inputVector,
232 vtkInformationVector *outputVector)
233 {
234 // get the info objects
235 vtkInformation *inInfo = inputVector[0]->GetInformationObject(0);
236 vtkInformation *outInfo = outputVector->GetInformationObject(0);
237
238 // get the input and output
239 vtkGraph *input = vtkGraph::SafeDownCast(
240 inInfo->Get(vtkDataObject::DATA_OBJECT()));
241 vtkGraph *output = vtkGraph::SafeDownCast(
242 outInfo->Get(vtkDataObject::DATA_OBJECT()));
243
244 // Send the data to output.
245 output->ShallowCopy(input);
246
247 // Sanity check
248 // The Boost BFS likes to crash on empty datasets
249 if (input->GetNumberOfVertices() == 0)
250 {
251 //vtkWarningMacro("Empty input into " << this->GetClassName());
252 return 1;
253 }
254
255 if (this->OriginFromSelection)
256 {
257 vtkSelection* selection = vtkSelection::GetData(inputVector[1], 0);
258 if (selection == NULL)
259 {
260 vtkErrorMacro("OriginFromSelection set but selection input undefined.");
261 return 0;
262 }
263 vtkSmartPointer<vtkIdTypeArray> idArr =
264 vtkSmartPointer<vtkIdTypeArray>::New();
265 vtkConvertSelection::GetSelectedVertices(selection, input, idArr);
266 if (idArr->GetNumberOfTuples() == 0)
267 {
268 vtkErrorMacro("Origin selection is empty.");
269 return 0;
270 }
271 this->OriginVertexIndex = idArr->GetValue(0);
272 }
273 else
274 {
275 // Now figure out the origin vertex of the
276 // breadth first search
277 if (this->InputArrayName)
278 {
279 vtkAbstractArray* abstract = input->GetVertexData()->GetAbstractArray(this->InputArrayName);
280
281 // Does the array exist at all?
282 if (abstract == NULL)
283 {
284 vtkErrorMacro("Could not find array named " << this->InputArrayName);
285 return 0;
286 }
287
288 this->OriginVertexIndex = this->GetVertexIndex(abstract,this->OriginValue);
289 }
290 }
291
292 // Create the attribute array
293 vtkIntArray* BFSArray = vtkIntArray::New();
294 if (this->OutputArrayName)
295 {
296 BFSArray->SetName(this->OutputArrayName);
297 }
298 else
299 {
300 BFSArray->SetName("BFS");
301 }
302 BFSArray->SetNumberOfTuples(output->GetNumberOfVertices());
303
304 // Initialize the BFS array to all 0's
305 for(int i=0;i< BFSArray->GetNumberOfTuples(); ++i)
306 {
307 BFSArray->SetValue(i, VTK_INT_MAX);
308 }
309
310 vtkIdType maxFromRootVertex = this->OriginVertexIndex;
311
312 // Create a color map (used for marking visited nodes)
313 vector_property_map<default_color_type> color(output->GetNumberOfVertices());
314
315 vtkDistributedGraphHelper *helper = output->GetDistributedGraphHelper();
316 if (!helper)
317 {
318 vtkErrorMacro("Distributed vtkGraph is required.");
319 return 1;
320 }
321
322 // We can only deal with Parallel BGL-distributed graphs.
323 vtkPBGLDistributedGraphHelper *pbglHelper
324 = vtkPBGLDistributedGraphHelper::SafeDownCast(helper);
325 if (!pbglHelper)
326 {
327 vtkErrorMacro("Can only perform parallel breadth-first-search on a Parallel BGL distributed graph");
328 return 1;
329 }
330
331 // Set the distance to the source vertex to zero
332 int myRank = outInfo->Get(vtkStreamingDemandDrivenPipeline::UPDATE_PIECE_NUMBER());
333
334 if (helper->GetVertexOwner(this->OriginVertexIndex) == myRank)
335 {
336 BFSArray->SetValue(helper->GetVertexIndex(this->OriginVertexIndex), 0);
337 }
338
339 // Distributed color map
340 typedef boost::parallel::distributed_property_map<
341 boost::graph::distributed::mpi_process_group,
342 boost::vtkVertexGlobalMap,
343 vector_property_map<default_color_type>
344 > DistributedColorMap;
345 DistributedColorMap distribColor(pbglHelper->GetProcessGroup(),
346 boost::vtkVertexGlobalMap(output),
347 color);
348
349 // Distributed distance map
350 typedef vtkDistributedVertexPropertyMapType<vtkIntArray>::type
351 DistributedDistanceMap;
352
353 // Distributed distance recorder
354 DistributedDistanceMap distribBFSArray
355 = MakeDistributedVertexPropertyMap(output, BFSArray);
356 set_property_map_role(boost::vertex_distance, distribBFSArray);
357 pbgl_bfs_distance_recorder<DistributedDistanceMap>
358 bfsVisitor(distribBFSArray, &maxFromRootVertex);
359
360 // The use of parallel_bfs_helper works around the fact that a
361 // vtkGraph (and its descendents) will not be viewed as a
362 // distributed graph by the Parallel BGL.
363 if (vtkDirectedGraph::SafeDownCast(output))
364 {
365 vtkDirectedGraph *g = vtkDirectedGraph::SafeDownCast(output);
366 boost::detail::parallel_bfs_helper(g, this->OriginVertexIndex,
367 distribColor,
368 bfsVisitor,
369 boost::detail::error_property_not_found(),
370 get(vertex_index, g));
371 }
372 else
373 {
374 vtkUndirectedGraph *g = vtkUndirectedGraph::SafeDownCast(output);
375 boost::detail::parallel_bfs_helper(g, this->OriginVertexIndex,
376 distribColor, bfsVisitor,
377 boost::detail::error_property_not_found(),
378 get(vertex_index, g));
379 }
380
381 // Compute maxFromRootVertex globally
382 using boost::parallel::all_reduce;
383 int maxDistance = 0;
384 if (helper->GetVertexOwner(maxFromRootVertex) == myRank)
385 {
386 maxDistance = BFSArray->GetValue(helper->GetVertexIndex(maxFromRootVertex));
387 }
388 maxFromRootVertex = all_reduce(pbglHelper->GetProcessGroup(),
389 std::make_pair(maxFromRootVertex,
390 maxDistance),
391 furthest_vertex(output)).first;
392
393 // Add attribute array to the output
394 output->GetVertexData()->AddArray(BFSArray);
395 BFSArray->Delete();
396
397 if (this->OutputSelection)
398 {
399 vtkSelection* sel = vtkSelection::GetData(outputVector, 1);
400 vtkIdTypeArray* ids = vtkIdTypeArray::New();
401
402 // Set the output based on the output selection type
403 if (!strcmp(OutputSelectionType,"MAX_DIST_FROM_ROOT"))
404 {
405 ids->InsertNextValue(maxFromRootVertex);
406 }
407
408 vtkSmartPointer<vtkSelectionNode> node = vtkSmartPointer<vtkSelectionNode>::New();
409 sel->AddNode(node);
410 node->SetSelectionList(ids);
411 node->GetProperties()->Set(vtkSelectionNode::CONTENT_TYPE(), vtkSelectionNode::INDICES);
412 node->GetProperties()->Set(vtkSelectionNode::FIELD_TYPE(), vtkSelectionNode::POINT);
413 ids->Delete();
414 }
415
416 return 1;
417 }
418
PrintSelf(ostream & os,vtkIndent indent)419 void vtkPBGLBreadthFirstSearch::PrintSelf(ostream& os, vtkIndent indent)
420 {
421 this->Superclass::PrintSelf(os, indent);
422
423 os << indent << "OriginVertexIndex: " << this->OriginVertexIndex << endl;
424
425 os << indent << "InputArrayName: "
426 << (this->InputArrayName ? this->InputArrayName : "(none)") << endl;
427
428 os << indent << "OutputArrayName: "
429 << (this->OutputArrayName ? this->OutputArrayName : "(none)") << endl;
430
431 os << indent << "OriginValue: " << this->OriginValue.ToString() << endl;
432
433 os << indent << "OutputSelection: "
434 << (this->OutputSelection ? "on" : "off") << endl;
435
436 os << indent << "OriginFromSelection: "
437 << (this->OriginFromSelection ? "on" : "off") << endl;
438
439 os << indent << "OutputSelectionType: "
440 << (this->OutputSelectionType ? this->OutputSelectionType : "(none)") << endl;
441 }
442
443 //----------------------------------------------------------------------------
FillInputPortInformation(int port,vtkInformation * info)444 int vtkPBGLBreadthFirstSearch::FillInputPortInformation(
445 int port, vtkInformation* info)
446 {
447 // now add our info
448 if (port == 0)
449 {
450 info->Set(vtkAlgorithm::INPUT_REQUIRED_DATA_TYPE(), "vtkGraph");
451 }
452 else if (port == 1)
453 {
454 info->Set(vtkAlgorithm::INPUT_REQUIRED_DATA_TYPE(), "vtkSelection");
455 info->Set(vtkAlgorithm::INPUT_IS_OPTIONAL(), 1);
456 }
457 return 1;
458 }
459
460 //----------------------------------------------------------------------------
FillOutputPortInformation(int port,vtkInformation * info)461 int vtkPBGLBreadthFirstSearch::FillOutputPortInformation(
462 int port, vtkInformation* info)
463 {
464 // now add our info
465 if (port == 0)
466 {
467 info->Set(vtkDataObject::DATA_TYPE_NAME(), "vtkGraph");
468 }
469 else if (port == 1)
470 {
471 info->Set(vtkDataObject::DATA_TYPE_NAME(), "vtkSelection");
472 }
473 return 1;
474 }
475
476 #endif //VTK_LEGACY_REMOVE
477