VTK
vtkPBGLGraphAdapter.h
Go to the documentation of this file.
1 /*=========================================================================
2 
3  Program: Visualization Toolkit
4  Module: vtkPBGLGraphAdapter.h
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 (C) 2008 The Trustees of Indiana University.
17  * Use, modification and distribution is subject to the Boost Software
18  * License, Version 1.0. (See http://www.boost.org/LICENSE_1_0.txt)
19  */
29 #ifndef vtkPBGLGraphAdapter_h
30 #define vtkPBGLGraphAdapter_h
31 
32 #include "vtkBoostGraphAdapter.h" // for the sequential BGL adapters
33 
34 #include <map> // required for Boost 1.54.0
35 #include <boost/graph/use_mpi.hpp>
36 #include <boost/graph/distributed/mpi_process_group.hpp>
37 #include <boost/graph/properties.hpp>
38 #include <boost/graph/parallel/container_traits.hpp>
39 #include <boost/property_map/parallel/local_property_map.hpp>
40 #include <boost/property_map/parallel/distributed_property_map.hpp>
41 #include <boost/serialization/base_object.hpp>
42 #include <boost/functional/hash.hpp>
43 
46 
47 namespace boost {
48 
49 // Define specializations of class template property_map for
50 // vtkDirectedGraph and vtkUndirectedGraph, based on the
51 // specialization for vtkGraph.
52 #define SUBCLASS_PROPERTY_MAP_SPECIALIZATIONS(Property) \
53  template<> \
54  struct property_map<vtkDirectedGraph *, Property> \
55  : property_map<vtkGraph *, Property> { }; \
56  \
57  template<> \
58  struct property_map<vtkUndirectedGraph *, Property> \
59  : property_map<vtkGraph *, Property> { }; \
60  \
61  template<> \
62  struct property_map<vtkDirectedGraph * const, Property> \
63  : property_map<vtkGraph *, Property> { }; \
64  \
65  template<> \
66  struct property_map<vtkUndirectedGraph * const, Property> \
67  : property_map<vtkGraph *, Property> { }
68 
69  // Property map from a vertex descriptor to the owner of the vertex
71  {
72  // Default-construct an empty (useless!) vertex-owner map
74 
75  // Construct a vertex-owner map for a specific vtkGraph
76  explicit vtkVertexOwnerMap(vtkGraph* graph)
77  : helper(graph? graph->GetDistributedGraphHelper() : 0) { }
78 
79  // The distributed graph helper that will aid in mapping vertices
80  // to their owners.
82  };
83 
84  // Property map traits for the vertex-owner map
85  template<>
87  {
91  typedef readable_property_map_tag category;
92  };
93 
94  // Retrieve the owner of the given vertex (the key)
96  get(
97  vtkVertexOwnerMap owner_map,
99  {
100  return owner_map.helper->GetVertexOwner(key);
101  }
102 
103  // State that the vertex owner property map of a vtkGraph is the
104  // vtkVertexOwnerMap
105  template<>
106  struct property_map<vtkGraph*, vertex_owner_t>
107  {
110  };
111 
113 
114  // Retrieve the vertex-owner property map from a vtkGraph
115  inline vtkVertexOwnerMap
116  get(vertex_owner_t, vtkGraph* graph)
117  {
118  return vtkVertexOwnerMap(graph);
119  }
120 
121  // Property map from a vertex descriptor to the local descriptor of
122  // the vertex
124  {
125  // Default-construct an empty (useless!) vertex-local map
127 
128  // Construct a vertex-local map for a specific vtkGraph
129  explicit vtkVertexLocalMap(vtkGraph* graph)
130  : helper(graph? graph->GetDistributedGraphHelper() : 0) { }
131 
132  // The distributed graph helper that will aid in mapping vertices
133  // to their locals.
135  };
136 
137  // Property map traits for the vertex-local map
138  template<>
140  {
141  typedef int value_type;
142  typedef int reference;
144  typedef readable_property_map_tag category;
145  };
146 
147  // Retrieve the local descriptor of the given vertex (the key)
150  vtkVertexLocalMap local_map,
152  {
153  return local_map.helper->GetVertexIndex(key);
154  }
155 
156  // State that the vertex local property map of a vtkGraph is the
157  // vtkVertexLocalMap
158  template<>
159  struct property_map<vtkGraph*, vertex_local_t>
160  {
163  };
164 
166 
167  // Retrieve the vertex-local property map from a vtkGraph
168  inline vtkVertexLocalMap
169  get(vertex_local_t, vtkGraph* graph)
170  {
171  return vtkVertexLocalMap(graph);
172  }
173 
174  // Map from vertex descriptor to (owner, local descriptor)
176  {
178 
179  explicit vtkVertexGlobalMap(vtkGraph* graph)
180  : helper(graph? graph->GetDistributedGraphHelper() : 0) { }
181 
183  };
184 
185  template<>
187  {
188  typedef std::pair<int, vtkIdType> value_type;
191  typedef readable_property_map_tag category;
192  };
193 
196  vtkVertexGlobalMap global_map,
198  {
199  return std::pair<int,vtkIdType>(global_map.helper->GetVertexOwner(key),
200  global_map.helper->GetVertexIndex(key));
201  }
202 
203  //
204  template<>
205  struct property_map<vtkGraph*, vertex_global_t>
206  {
209  };
210 
211  SUBCLASS_PROPERTY_MAP_SPECIALIZATIONS(vertex_global_t);
212 
213  inline vtkVertexGlobalMap
214  get(vertex_global_t, vtkGraph* graph)
215  {
216  return vtkVertexGlobalMap(graph);
217  }
218 
219  // Map from edge descriptor to (owner, local descriptor)
221  {
223 
224  explicit vtkEdgeGlobalMap(vtkGraph* graph)
225  : helper(graph? graph->GetDistributedGraphHelper() : 0) { }
226 
228  };
229 
230  template<>
232  {
233  typedef std::pair<int, vtkIdType> value_type;
236  typedef readable_property_map_tag category;
237  };
238 
241  vtkEdgeGlobalMap global_map,
243  {
244  return std::pair<int, vtkIdType>
245  (global_map.helper->GetEdgeOwner(key.Id), key.Id);
246  }
247 
248  //
249  template<>
250  struct property_map<vtkGraph*, edge_global_t>
251  {
254  };
255 
257 
258  inline vtkEdgeGlobalMap
259  get(edge_global_t, vtkGraph* graph)
260  {
261  return vtkEdgeGlobalMap(graph);
262  }
263 
264 #undef SUBCLASS_PROPERTY_MAP_SPECIALIZATIONS
265 
266  //===========================================================================
267  // Hash functions
268  template<>
269  struct hash<vtkEdgeType>
270  {
271  std::size_t operator()(const vtkEdgeType& edge) const
272  {
273  return hash_value(edge.Id);
274  }
275  };
276 
277 } // namespace boost
278 
279 //----------------------------------------------------------------------------
280 // Extract the process group from a vtkGraph
281 //----------------------------------------------------------------------------
282 
283 namespace boost { namespace graph { namespace parallel {
284  template<>
285  struct process_group_type<vtkGraph *>
286  {
287  typedef boost::graph::distributed::mpi_process_group type;
288  };
289 
290  template<>
291  struct process_group_type<vtkDirectedGraph *>
293 
294  template<>
295  struct process_group_type<vtkUndirectedGraph *>
297 
298  template<>
299  struct process_group_type<vtkDirectedGraph * const>
301 
302  template<>
303  struct process_group_type<vtkUndirectedGraph * const>
305 } } } // end namespace boost::graph::parallel
306 
307 boost::graph::distributed::mpi_process_group process_group(vtkGraph *graph);
308 
309 inline boost::graph::distributed::mpi_process_group
311 {
312  return process_group(static_cast<vtkGraph *>(graph));
313 }
314 
315 inline boost::graph::distributed::mpi_process_group
317 {
318  return process_group(static_cast<vtkGraph *>(graph));
319 }
320 
321 //----------------------------------------------------------------------------
322 // Serialization support for simple VTK structures
323 //----------------------------------------------------------------------------
324 
325 //----------------------------------------------------------------------------
326 template<typename Archiver>
327 void serialize(Archiver& ar, vtkEdgeBase& edge, const unsigned int)
328 {
329  ar & edge.Id;
330 }
331 
332 template<typename Archiver>
333 void serialize(Archiver& ar, vtkOutEdgeType& edge, const unsigned int)
334 {
335  ar & boost::serialization::base_object<vtkEdgeBase>(edge)
336  & edge.Target;
337 }
338 
339 template<typename Archiver>
340 void serialize(Archiver& ar, vtkInEdgeType& edge, const unsigned int)
341 {
342  ar & boost::serialization::base_object<vtkEdgeBase>(edge)
343  & edge.Source;
344 }
345 
346 template<typename Archiver>
347 void serialize(Archiver& ar, vtkEdgeType& edge, const unsigned int)
348 {
349  ar & boost::serialization::base_object<vtkEdgeBase>(edge)
350  & edge.Source
351  & edge.Target;
352 }
353 
354 //----------------------------------------------------------------------------
355 // Simplified tools to build distributed property maps
356 //----------------------------------------------------------------------------
357 
365 typedef boost::local_property_map<boost::graph::distributed::mpi_process_group,
369 
371 
376 {
378  if (!helper)
379  {
380  vtkErrorWithObjectMacro(graph, "A vtkGraph without a distributed graph helper is not a distributed graph");
382  }
384 
387  if (!pbglHelper)
388  {
389  vtkErrorWithObjectMacro(graph, "A vtkGraph with a non-Parallel BGL distributed graph helper cannot be used with the Parallel BGL");
391  }
392 
396 }
397 
399 
403 template<typename DataArray>
405 {
406  typedef boost::parallel::distributed_property_map<
407  boost::graph::distributed::mpi_process_group,
409  DataArray*> type;
410 };
412 
417 template<typename DataArray>
420 {
422 
424  if (!helper)
425  {
426  vtkErrorWithObjectMacro(graph, "A vtkGraph without a distributed graph helper is not a distributed graph");
427  return MapType();
428  }
429 
432  if (!pbglHelper)
433  {
434  vtkErrorWithObjectMacro(graph, "A vtkGraph with a non-Parallel BGL distributed graph helper cannot be used with the Parallel BGL");
435  return MapType();
436  }
437 
438  return MapType(pbglHelper->GetProcessGroup(),
440  array);
441 }
442 
444 
448 template<typename DataArray>
450 {
451  typedef boost::parallel::distributed_property_map<
452  boost::graph::distributed::mpi_process_group,
454  DataArray*> type;
455 };
457 
462 template<typename DataArray>
464 MakeDistributedEdgePropertyMap(vtkGraph* graph, DataArray* array)
465 {
467 
469  if (!helper)
470  {
471  vtkErrorWithObjectMacro(graph, "A vtkGraph without a distributed graph helper is not a distributed graph");
472  return MapType();
473  }
474 
477  if (!pbglHelper)
478  {
479  vtkErrorWithObjectMacro(graph, "A vtkGraph with a non-Parallel BGL distributed graph helper cannot be used with the Parallel BGL");
480  return MapType();
481  }
482 
483  return MapType(pbglHelper->GetProcessGroup(),
485  array);
486 }
487 
488 #endif // vtkPBGLGraphAdapter_h
489 // VTK-HeaderTest-Exclude: vtkPBGLGraphAdapter.h
boost::vtkVertexLocalMap::helper
vtkDistributedGraphHelper * helper
Definition: vtkPBGLGraphAdapter.h:134
vtkEdgeBase::Id
vtkIdType Id
Definition: vtkGraph.h:255
serialize
void serialize(Archiver &ar, vtkEdgeBase &edge, const unsigned int)
Definition: vtkPBGLGraphAdapter.h:327
boost::graph::parallel::process_group_type< vtkUndirectedGraph * >
Definition: vtkPBGLGraphAdapter.h:295
vtkPBGLDistributedGraphHelper
end namespace boost::graph::distributed
Definition: vtkPBGLDistributedGraphHelper.h:55
boost::property_map< vtkGraph *, vertex_global_t >::const_type
vtkVertexGlobalMap const_type
Definition: vtkPBGLGraphAdapter.h:208
boost::property_map< vtkGraph *, vertex_global_t >::type
vtkVertexGlobalMap type
Definition: vtkPBGLGraphAdapter.h:207
vtkDistributedGraphHelper
helper for the vtkGraph class that allows the graph to be distributed across multiple memory spaces.
Definition: vtkDistributedGraphHelper.h:80
vtkGraph::GetDistributedGraphHelper
vtkDistributedGraphHelper * GetDistributedGraphHelper()
Retrieves the distributed graph helper for this graph.
vtkUndirectedGraph
An undirected graph.
Definition: vtkUndirectedGraph.h:54
vtkPBGLDistributedGraphHelper::GetProcessGroup
boost::graph::distributed::mpi_process_group GetProcessGroup()
Return the process group associated with this distributed graph.
boost::property_traits
Definition: vtkBoostGraphAdapter.h:58
vtkIdType
int vtkIdType
Definition: vtkType.h:287
boost::property_traits< vtkVertexOwnerMap >::category
readable_property_map_tag category
Definition: vtkPBGLGraphAdapter.h:91
vtkDistributedEdgePropertyMapType::type
boost::parallel::distributed_property_map< boost::graph::distributed::mpi_process_group, boost::vtkEdgeGlobalMap, DataArray * > type
Definition: vtkPBGLGraphAdapter.h:454
vtkDistributedVertexPropertyMapType
Retrieves the type of the distributed property map indexed by the vertices of a distributed graph.
Definition: vtkPBGLGraphAdapter.h:404
vtkX3D::key
Definition: vtkX3D.h:257
boost::vtkEdgeGlobalMap::vtkEdgeGlobalMap
vtkEdgeGlobalMap()
Definition: vtkPBGLGraphAdapter.h:222
vtkPBGLDistributedGraphHelper::SafeDownCast
static vtkPBGLDistributedGraphHelper * SafeDownCast(vtkObjectBase *o)
boost::vtkVertexLocalMap::vtkVertexLocalMap
vtkVertexLocalMap()
Definition: vtkPBGLGraphAdapter.h:126
boost::property_traits< vtkVertexLocalMap >::category
readable_property_map_tag category
Definition: vtkPBGLGraphAdapter.h:144
vtkDirectedGraph
A directed graph.
Definition: vtkDirectedGraph.h:47
boost
Forward declaration required for Boost serialization.
Definition: vtkVariantArray.h:44
MakeDistributedVertexIndexMap
vtkGraphDistributedVertexIndexMap MakeDistributedVertexIndexMap(vtkGraph *graph)
Creates the distributed vertex index property map for a vtkGraph.
Definition: vtkPBGLGraphAdapter.h:375
boost::property_traits< vtkVertexGlobalMap >::key_type
vtkIdType key_type
Definition: vtkPBGLGraphAdapter.h:190
vtkInEdgeType
Definition: vtkGraph.h:267
boost::SUBCLASS_PROPERTY_MAP_SPECIALIZATIONS
SUBCLASS_PROPERTY_MAP_SPECIALIZATIONS(vertex_owner_t)
boost::vtkVertexOwnerMap::helper
vtkDistributedGraphHelper * helper
Definition: vtkPBGLGraphAdapter.h:81
boost::vtkVertexLocalMap::vtkVertexLocalMap
vtkVertexLocalMap(vtkGraph *graph)
Definition: vtkPBGLGraphAdapter.h:129
vtkOutEdgeType::Target
vtkIdType Target
Definition: vtkGraph.h:264
vtkEdgeType::Source
vtkIdType Source
Definition: vtkGraph.h:283
boost::vtkVertexOwnerMap::vtkVertexOwnerMap
vtkVertexOwnerMap(vtkGraph *graph)
Definition: vtkPBGLGraphAdapter.h:76
boost::property_traits< vtkEdgeGlobalMap >::category
readable_property_map_tag category
Definition: vtkPBGLGraphAdapter.h:236
vtkGraphDistributedVertexIndexMap
boost::local_property_map< boost::graph::distributed::mpi_process_group, boost::vtkVertexGlobalMap, boost::vtkGraphIndexMap > vtkGraphDistributedVertexIndexMap
A property map used as the vertex index map for distributed vtkGraphs.
Definition: vtkPBGLGraphAdapter.h:368
vtkEdgeType
Definition: vtkGraph.h:276
boost::property_traits< vtkEdgeGlobalMap >::reference
value_type reference
Definition: vtkPBGLGraphAdapter.h:234
vtkDistributedGraphHelper::GetVertexOwner
vtkIdType GetVertexOwner(vtkIdType v) const
Returns owner of vertex v, by extracting top ceil(log2 P) bits of v.
boost::vtkVertexGlobalMap::vtkVertexGlobalMap
vtkVertexGlobalMap()
Definition: vtkPBGLGraphAdapter.h:177
vtkDistributedVertexPropertyMapType::type
boost::parallel::distributed_property_map< boost::graph::distributed::mpi_process_group, boost::vtkVertexGlobalMap, DataArray * > type
Definition: vtkPBGLGraphAdapter.h:409
boost::graph::parallel::process_group_type< vtkDirectedGraph * >
Definition: vtkPBGLGraphAdapter.h:291
boost::property_traits< vtkVertexGlobalMap >::value_type
std::pair< int, vtkIdType > value_type
Definition: vtkPBGLGraphAdapter.h:188
boost::get
double get(vtkDataArray *const &arr, vtkIdType key)
Definition: vtkBoostGraphAdapter.h:104
boost::property_traits< vtkVertexOwnerMap >::reference
vtkIdType reference
Definition: vtkPBGLGraphAdapter.h:89
boost::property_traits< vtkEdgeGlobalMap >::key_type
vtkEdgeType key_type
Definition: vtkPBGLGraphAdapter.h:235
MakeDistributedEdgePropertyMap
vtkDistributedEdgePropertyMapType< DataArray >::type MakeDistributedEdgePropertyMap(vtkGraph *graph, DataArray *array)
Build a distributed property map indexed by the edges of the given graph, using storage from the give...
Definition: vtkPBGLGraphAdapter.h:464
boost::vtkEdgeGlobalMap
Definition: vtkPBGLGraphAdapter.h:220
boost::property_map< vtkGraph *, vertex_owner_t >::const_type
vtkVertexOwnerMap const_type
Definition: vtkPBGLGraphAdapter.h:109
vtkDistributedGraphHelper::GetVertexIndex
vtkIdType GetVertexIndex(vtkIdType v) const
Returns local index of vertex v, by masking off top ceil(log2 P) bits of v.
vtkEdgeType::Target
vtkIdType Target
Definition: vtkGraph.h:284
boost::vtkGraphIndexMap
Definition: vtkBoostGraphAdapter.h:1034
boost::property_traits< vtkVertexLocalMap >::reference
int reference
Definition: vtkPBGLGraphAdapter.h:142
boost::property_map< vtkGraph *, vertex_local_t >::type
vtkVertexLocalMap type
Definition: vtkPBGLGraphAdapter.h:161
boost::property_traits< vtkVertexLocalMap >::key_type
vtkIdType key_type
Definition: vtkPBGLGraphAdapter.h:143
boost::property_traits< vtkVertexOwnerMap >::value_type
vtkIdType value_type
Definition: vtkPBGLGraphAdapter.h:88
boost::property_map< vtkGraph *, edge_global_t >::type
vtkEdgeGlobalMap type
Definition: vtkPBGLGraphAdapter.h:252
boost::vtkVertexOwnerMap
Definition: vtkPBGLGraphAdapter.h:70
boost::property_traits< vtkVertexOwnerMap >::key_type
vtkIdType key_type
Definition: vtkPBGLGraphAdapter.h:90
boost::vtkVertexGlobalMap::vtkVertexGlobalMap
vtkVertexGlobalMap(vtkGraph *graph)
Definition: vtkPBGLGraphAdapter.h:179
boost::property_traits< vtkVertexLocalMap >::value_type
int value_type
Definition: vtkPBGLGraphAdapter.h:141
boost::property_traits< vtkEdgeGlobalMap >::value_type
std::pair< int, vtkIdType > value_type
Definition: vtkPBGLGraphAdapter.h:233
vtkInEdgeType::Source
vtkIdType Source
Definition: vtkGraph.h:273
boost::property_traits< vtkVertexGlobalMap >::reference
value_type reference
Definition: vtkPBGLGraphAdapter.h:189
boost::graph::parallel::process_group_type< vtkGraph * >::type
boost::graph::distributed::mpi_process_group type
Definition: vtkPBGLGraphAdapter.h:287
boost::property_map< vtkGraph *, vertex_owner_t >::type
vtkVertexOwnerMap type
Definition: vtkPBGLGraphAdapter.h:108
vtkEdgeBase
Definition: vtkGraph.h:250
boost::vtkVertexOwnerMap::vtkVertexOwnerMap
vtkVertexOwnerMap()
Definition: vtkPBGLGraphAdapter.h:73
vtkBoostGraphAdapter.h
vtkPBGLDistributedGraphHelper.h
boost::property_map< vtkGraph *, edge_global_t >::const_type
vtkEdgeGlobalMap const_type
Definition: vtkPBGLGraphAdapter.h:253
boost::property_map< vtkGraph *, vertex_local_t >::const_type
vtkVertexLocalMap const_type
Definition: vtkPBGLGraphAdapter.h:162
boost::property_traits< vtkVertexGlobalMap >::category
readable_property_map_tag category
Definition: vtkPBGLGraphAdapter.h:191
vtkOutEdgeType
Definition: vtkGraph.h:258
boost::vtkVertexLocalMap
Definition: vtkPBGLGraphAdapter.h:123
process_group
boost::graph::distributed::mpi_process_group process_group(vtkGraph *graph)
vtkDistributedEdgePropertyMapType
Retrieves the type of the distributed property map indexed by the edges of a distributed graph.
Definition: vtkPBGLGraphAdapter.h:449
boost::graph::parallel::process_group_type< vtkGraph * >
Definition: vtkPBGLGraphAdapter.h:285
vtkVariantBoostSerialization.h
MakeDistributedVertexPropertyMap
vtkDistributedVertexPropertyMapType< DataArray >::type MakeDistributedVertexPropertyMap(vtkGraph *graph, DataArray *array)
Build a distributed property map indexed by the vertices of the given graph, using storage from the g...
Definition: vtkPBGLGraphAdapter.h:419
boost::vtkVertexGlobalMap
Definition: vtkPBGLGraphAdapter.h:175
vtkGraph
Base class for graph data types.
Definition: vtkGraph.h:287
vtkDistributedGraphHelper::GetEdgeOwner
vtkIdType GetEdgeOwner(vtkIdType e_id) const
Returns owner of edge with ID e_id, by extracting top ceil(log2 P) bits of e_id.
boost::vtkVertexGlobalMap::helper
vtkDistributedGraphHelper * helper
Definition: vtkPBGLGraphAdapter.h:182
boost::hash< vtkEdgeType >::operator()
std::size_t operator()(const vtkEdgeType &edge) const
Definition: vtkPBGLGraphAdapter.h:271
boost::vtkEdgeGlobalMap::vtkEdgeGlobalMap
vtkEdgeGlobalMap(vtkGraph *graph)
Definition: vtkPBGLGraphAdapter.h:224
boost::vtkEdgeGlobalMap::helper
vtkDistributedGraphHelper * helper
Definition: vtkPBGLGraphAdapter.h:227