VTK
|
00001 /*========================================================================= 00002 00003 Program: Visualization Toolkit 00004 Module: vtkBoostGraphAdapter.h 00005 00006 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen 00007 All rights reserved. 00008 See Copyright.txt or http://www.kitware.com/Copyright.htm for details. 00009 00010 This software is distributed WITHOUT ANY WARRANTY; without even 00011 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 00012 PURPOSE. See the above copyright notice for more information. 00013 00014 =========================================================================*/ 00015 /*------------------------------------------------------------------------- 00016 Copyright 2008 Sandia Corporation. 00017 Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation, 00018 the U.S. Government retains certain rights in this software. 00019 -------------------------------------------------------------------------*/ 00029 #ifndef __vtkBoostGraphAdapter_h 00030 #define __vtkBoostGraphAdapter_h 00031 00032 #include "vtkAbstractArray.h" 00033 #include "vtkDirectedGraph.h" 00034 #include "vtkDistributedGraphHelper.h" 00035 #include "vtkDataObject.h" 00036 #include "vtkDataArray.h" 00037 #include "vtkDoubleArray.h" 00038 #include "vtkFloatArray.h" 00039 #include "vtkIdTypeArray.h" 00040 #include "vtkInformation.h" 00041 #include "vtkIntArray.h" 00042 #include "vtkMutableDirectedGraph.h" 00043 #include "vtkMutableUndirectedGraph.h" 00044 #include "vtkTree.h" 00045 #include "vtkUndirectedGraph.h" 00046 #include "vtkVariant.h" 00047 00048 namespace boost { 00049 //=========================================================================== 00050 // VTK arrays as property maps 00051 // These need to be defined before including other boost stuff 00052 00053 // Forward declarations are required here, so that we aren't forced 00054 // to include boost/property_map.hpp. 00055 template<typename> class property_traits; 00056 class read_write_property_map_tag; 00057 00058 #define vtkPropertyMapMacro(T, V) \ 00059 template <> \ 00060 struct property_traits<T*> \ 00061 { \ 00062 typedef V value_type; \ 00063 typedef V reference; \ 00064 typedef vtkIdType key_type; \ 00065 typedef read_write_property_map_tag category; \ 00066 }; \ 00067 \ 00068 inline property_traits<T*>::reference \ 00069 get( \ 00070 T* const & arr, \ 00071 property_traits<T*>::key_type key) \ 00072 { \ 00073 return arr->GetValue(key); \ 00074 } \ 00075 \ 00076 inline void \ 00077 put( \ 00078 T* arr, \ 00079 property_traits<T*>::key_type key, \ 00080 const property_traits<T*>::value_type & value) \ 00081 { \ 00082 arr->InsertValue(key, value); \ 00083 } 00084 00085 vtkPropertyMapMacro(vtkIntArray, int) 00086 vtkPropertyMapMacro(vtkIdTypeArray, vtkIdType) 00087 vtkPropertyMapMacro(vtkDoubleArray, double) 00088 vtkPropertyMapMacro(vtkFloatArray, float) 00089 00090 // vtkDataArray 00091 template<> 00092 struct property_traits<vtkDataArray*> 00093 { 00094 typedef double value_type; 00095 typedef double reference; 00096 typedef vtkIdType key_type; 00097 typedef read_write_property_map_tag category; 00098 }; 00099 00100 inline double 00101 get(vtkDataArray * const& arr, vtkIdType key) 00102 { 00103 return arr->GetTuple1(key); 00104 } 00105 00106 inline void 00107 put(vtkDataArray *arr, vtkIdType key, const double& value) 00108 { 00109 arr->SetTuple1(key, value); 00110 } 00111 00112 // vtkAbstractArray as a property map of vtkVariants 00113 template<> 00114 struct property_traits<vtkAbstractArray*> 00115 { 00116 typedef vtkVariant value_type; 00117 typedef vtkVariant reference; 00118 typedef vtkIdType key_type; 00119 typedef read_write_property_map_tag category; 00120 }; 00121 00122 inline vtkVariant 00123 get(vtkAbstractArray * const& arr, vtkIdType key) 00124 { 00125 return arr->GetVariantValue(key); 00126 } 00127 00128 inline void 00129 put(vtkAbstractArray *arr, vtkIdType key, const vtkVariant& value) 00130 { 00131 arr->InsertVariantValue(key, value); 00132 } 00133 } 00134 00135 #include <vtksys/stl/utility> // STL Header 00136 00137 #include <boost/config.hpp> 00138 #include <boost/iterator/iterator_facade.hpp> 00139 #include <boost/graph/graph_traits.hpp> 00140 #include <boost/graph/properties.hpp> 00141 #include <boost/graph/adjacency_iterator.hpp> 00142 00143 // The functions and classes in this file allows the user to 00144 // treat a vtkDirectedGraph or vtkUndirectedGraph object 00145 // as a boost graph "as is". 00146 00147 namespace boost { 00148 00149 class vtk_vertex_iterator : 00150 public iterator_facade<vtk_vertex_iterator, 00151 vtkIdType, 00152 bidirectional_traversal_tag, 00153 vtkIdType, 00154 vtkIdType> 00155 { 00156 public: 00157 explicit vtk_vertex_iterator(vtkIdType i = 0) : index(i) {} 00158 00159 private: 00160 vtkIdType dereference() const { return index; } 00161 00162 bool equal(const vtk_vertex_iterator& other) const 00163 { return index == other.index; } 00164 00165 void increment() { index++; } 00166 void decrement() { index--; } 00167 00168 vtkIdType index; 00169 00170 friend class iterator_core_access; 00171 }; 00172 00173 class vtk_edge_iterator : 00174 public iterator_facade<vtk_edge_iterator, 00175 vtkEdgeType, 00176 forward_traversal_tag, 00177 vtkEdgeType, 00178 vtkIdType> 00179 { 00180 public: 00181 explicit vtk_edge_iterator(vtkGraph *g = 0, vtkIdType v = 0) : 00182 directed(false), vertex(v), lastVertex(v), iter(0), end(0), graph(g) 00183 { 00184 if (graph) 00185 { 00186 lastVertex = graph->GetNumberOfVertices(); 00187 } 00188 00189 vtkIdType myRank = -1; 00190 vtkDistributedGraphHelper *helper 00191 = this->graph? this->graph->GetDistributedGraphHelper() : 0; 00192 if (helper) 00193 { 00194 myRank = this->graph->GetInformation()->Get(vtkDataObject::DATA_PIECE_NUMBER()); 00195 vertex = helper->MakeDistributedId(myRank, vertex); 00196 lastVertex = helper->MakeDistributedId(myRank, lastVertex); 00197 } 00198 00199 if (graph != 0) 00200 { 00201 directed = (vtkDirectedGraph::SafeDownCast(graph) != 0); 00202 while (vertex < lastVertex && this->graph->GetOutDegree(vertex) == 0) 00203 { 00204 ++vertex; 00205 } 00206 00207 if (vertex < lastVertex) 00208 { 00209 // Get the outgoing edges of the first vertex that has outgoing 00210 // edges 00211 vtkIdType nedges; 00212 graph->GetOutEdges(vertex, iter, nedges); 00213 end = iter + nedges; 00214 00215 if (!directed) 00216 { 00217 while(iter != 0 00218 && (// Skip non-local edges 00219 (helper && helper->GetEdgeOwner(iter->Id) != myRank) 00220 // Skip entirely-local edges where Source > Target 00221 || (((helper 00222 && myRank == helper->GetVertexOwner(iter->Target)) 00223 || !helper) 00224 && vertex > iter->Target))) 00225 { 00226 this->inc(); 00227 } 00228 } 00229 } 00230 else 00231 { 00232 iter = 0; 00233 } 00234 } 00235 } 00236 00237 private: 00238 vtkEdgeType dereference() const 00239 { return vtkEdgeType(vertex, iter->Target, iter->Id); } 00240 00241 bool equal(const vtk_edge_iterator& other) const 00242 { return vertex == other.vertex && iter == other.iter; } 00243 00244 void increment() 00245 { 00246 inc(); 00247 if (!directed) 00248 { 00249 vtkIdType myRank = -1; 00250 vtkDistributedGraphHelper *helper 00251 = this->graph? this->graph->GetDistributedGraphHelper() : 0; 00252 if (helper) 00253 { 00254 myRank = this->graph->GetInformation()->Get(vtkDataObject::DATA_PIECE_NUMBER()); 00255 } 00256 00257 while (iter != 0 00258 && (// Skip non-local edges 00259 (helper && helper->GetEdgeOwner(iter->Id) != myRank) 00260 // Skip entirely-local edges where Source > Target 00261 || (((helper 00262 && myRank == helper->GetVertexOwner(iter->Target)) 00263 || !helper) 00264 && vertex > iter->Target))) 00265 { 00266 inc(); 00267 } 00268 } 00269 } 00270 00271 void inc() 00272 { 00273 ++iter; 00274 if (iter == end) 00275 { 00276 // Find a vertex with nonzero out degree. 00277 ++vertex; 00278 while (vertex < lastVertex && this->graph->GetOutDegree(vertex) == 0) 00279 { 00280 ++vertex; 00281 } 00282 00283 if (vertex < lastVertex) 00284 { 00285 vtkIdType nedges; 00286 graph->GetOutEdges(vertex, iter, nedges); 00287 end = iter + nedges; 00288 } 00289 else 00290 { 00291 iter = 0; 00292 } 00293 } 00294 } 00295 00296 bool directed; 00297 vtkIdType vertex; 00298 vtkIdType lastVertex; 00299 const vtkOutEdgeType * iter; 00300 const vtkOutEdgeType * end; 00301 vtkGraph *graph; 00302 00303 friend class iterator_core_access; 00304 }; 00305 00306 class vtk_out_edge_pointer_iterator : 00307 public iterator_facade<vtk_out_edge_pointer_iterator, 00308 vtkEdgeType, 00309 bidirectional_traversal_tag, 00310 vtkEdgeType, 00311 ptrdiff_t> 00312 { 00313 public: 00314 explicit vtk_out_edge_pointer_iterator(vtkGraph *g = 0, vtkIdType v = 0, bool end = false) : 00315 vertex(v) 00316 { 00317 if (g) 00318 { 00319 vtkIdType nedges; 00320 g->GetOutEdges(vertex, iter, nedges); 00321 if (end) 00322 { 00323 iter += nedges; 00324 } 00325 } 00326 } 00327 00328 private: 00329 vtkEdgeType dereference() const { return vtkEdgeType(vertex, iter->Target, iter->Id); } 00330 00331 bool equal(const vtk_out_edge_pointer_iterator& other) const 00332 { return iter == other.iter; } 00333 00334 void increment() { iter++; } 00335 void decrement() { iter--; } 00336 00337 vtkIdType vertex; 00338 const vtkOutEdgeType *iter; 00339 00340 friend class iterator_core_access; 00341 }; 00342 00343 class vtk_in_edge_pointer_iterator : 00344 public iterator_facade<vtk_in_edge_pointer_iterator, 00345 vtkEdgeType, 00346 bidirectional_traversal_tag, 00347 vtkEdgeType, 00348 ptrdiff_t> 00349 { 00350 public: 00351 explicit vtk_in_edge_pointer_iterator(vtkGraph *g = 0, vtkIdType v = 0, bool end = false) : 00352 vertex(v) 00353 { 00354 if (g) 00355 { 00356 vtkIdType nedges; 00357 g->GetInEdges(vertex, iter, nedges); 00358 if (end) 00359 { 00360 iter += nedges; 00361 } 00362 } 00363 } 00364 00365 private: 00366 vtkEdgeType dereference() const { return vtkEdgeType(iter->Source, vertex, iter->Id); } 00367 00368 bool equal(const vtk_in_edge_pointer_iterator& other) const 00369 { return iter == other.iter; } 00370 00371 void increment() { iter++; } 00372 void decrement() { iter--; } 00373 00374 vtkIdType vertex; 00375 const vtkInEdgeType *iter; 00376 00377 friend class iterator_core_access; 00378 }; 00379 00380 //=========================================================================== 00381 // vtkGraph 00382 // VertexAndEdgeListGraphConcept 00383 // BidirectionalGraphConcept 00384 // AdjacencyGraphConcept 00385 00386 struct vtkGraph_traversal_category : 00387 public virtual bidirectional_graph_tag, 00388 public virtual edge_list_graph_tag, 00389 public virtual vertex_list_graph_tag, 00390 public virtual adjacency_graph_tag { }; 00391 00392 template <> 00393 struct graph_traits<vtkGraph*> { 00394 typedef vtkIdType vertex_descriptor; 00395 static vertex_descriptor null_vertex() { return -1; } 00396 typedef vtkEdgeType edge_descriptor; 00397 static edge_descriptor null_edge() { return vtkEdgeType(-1, -1, -1); } 00398 typedef vtk_out_edge_pointer_iterator out_edge_iterator; 00399 typedef vtk_in_edge_pointer_iterator in_edge_iterator; 00400 00401 typedef vtk_vertex_iterator vertex_iterator; 00402 typedef vtk_edge_iterator edge_iterator; 00403 00404 typedef allow_parallel_edge_tag edge_parallel_category; 00405 typedef vtkGraph_traversal_category traversal_category; 00406 typedef vtkIdType vertices_size_type; 00407 typedef vtkIdType edges_size_type; 00408 typedef vtkIdType degree_size_type; 00409 00410 typedef adjacency_iterator_generator<vtkGraph*, 00411 vertex_descriptor, out_edge_iterator>::type adjacency_iterator; 00412 }; 00413 00414 template<> 00415 struct vertex_property_type< vtkGraph* > { 00416 typedef no_property type; 00417 }; 00418 00419 template<> 00420 struct edge_property_type< vtkGraph* > { 00421 typedef no_property type; 00422 }; 00423 00424 //=========================================================================== 00425 // vtkDirectedGraph 00426 00427 template <> 00428 struct graph_traits<vtkDirectedGraph*> : graph_traits<vtkGraph*> 00429 { 00430 typedef directed_tag directed_category; 00431 }; 00432 00433 // The graph_traits for a const graph are the same as a non-const graph. 00434 template <> 00435 struct graph_traits<const vtkDirectedGraph*> : graph_traits<vtkDirectedGraph*> { }; 00436 00437 // The graph_traits for a const graph are the same as a non-const graph. 00438 template <> 00439 struct graph_traits<vtkDirectedGraph* const> : graph_traits<vtkDirectedGraph*> { }; 00440 00441 // Internal vertex properties 00442 template<> 00443 struct vertex_property_type< vtkDirectedGraph* > 00444 : vertex_property_type< vtkGraph* > { }; 00445 00446 // Internal vertex properties 00447 template<> 00448 struct vertex_property_type< vtkDirectedGraph* const > 00449 : vertex_property_type< vtkGraph* > { }; 00450 00451 // Internal edge properties 00452 template<> 00453 struct edge_property_type< vtkDirectedGraph* > 00454 : edge_property_type< vtkGraph* > { }; 00455 00456 // Internal edge properties 00457 template<> 00458 struct edge_property_type< vtkDirectedGraph* const > 00459 : edge_property_type< vtkGraph* > { }; 00460 00461 //=========================================================================== 00462 // vtkTree 00463 00464 template <> 00465 struct graph_traits<vtkTree*> : graph_traits<vtkDirectedGraph*> { }; 00466 00467 // The graph_traits for a const graph are the same as a non-const graph. 00468 template <> 00469 struct graph_traits<const vtkTree*> : graph_traits<vtkTree*> { }; 00470 00471 // The graph_traits for a const graph are the same as a non-const graph. 00472 template <> 00473 struct graph_traits<vtkTree* const> : graph_traits<vtkTree*> { }; 00474 00475 //=========================================================================== 00476 // vtkUndirectedGraph 00477 template <> 00478 struct graph_traits<vtkUndirectedGraph*> : graph_traits<vtkGraph*> 00479 { 00480 typedef undirected_tag directed_category; 00481 }; 00482 00483 // The graph_traits for a const graph are the same as a non-const graph. 00484 template <> 00485 struct graph_traits<const vtkUndirectedGraph*> : graph_traits<vtkUndirectedGraph*> { }; 00486 00487 // The graph_traits for a const graph are the same as a non-const graph. 00488 template <> 00489 struct graph_traits<vtkUndirectedGraph* const> : graph_traits<vtkUndirectedGraph*> { }; 00490 00491 // Internal vertex properties 00492 template<> 00493 struct vertex_property_type< vtkUndirectedGraph* > 00494 : vertex_property_type< vtkGraph* > { }; 00495 00496 // Internal vertex properties 00497 template<> 00498 struct vertex_property_type< vtkUndirectedGraph* const > 00499 : vertex_property_type< vtkGraph* > { }; 00500 00501 // Internal edge properties 00502 template<> 00503 struct edge_property_type< vtkUndirectedGraph* > 00504 : edge_property_type< vtkGraph* > { }; 00505 00506 // Internal edge properties 00507 template<> 00508 struct edge_property_type< vtkUndirectedGraph* const > 00509 : edge_property_type< vtkGraph* > { }; 00510 00511 //=========================================================================== 00512 // vtkMutableDirectedGraph 00513 00514 template <> 00515 struct graph_traits<vtkMutableDirectedGraph*> : graph_traits<vtkDirectedGraph*> { }; 00516 00517 // The graph_traits for a const graph are the same as a non-const graph. 00518 template <> 00519 struct graph_traits<const vtkMutableDirectedGraph*> : graph_traits<vtkMutableDirectedGraph*> { }; 00520 00521 // The graph_traits for a const graph are the same as a non-const graph. 00522 template <> 00523 struct graph_traits<vtkMutableDirectedGraph* const> : graph_traits<vtkMutableDirectedGraph*> { }; 00524 00525 // Internal vertex properties 00526 template<> 00527 struct vertex_property_type< vtkMutableDirectedGraph* > 00528 : vertex_property_type< vtkDirectedGraph* > { }; 00529 00530 // Internal vertex properties 00531 template<> 00532 struct vertex_property_type< vtkMutableDirectedGraph* const > 00533 : vertex_property_type< vtkDirectedGraph* > { }; 00534 00535 // Internal edge properties 00536 template<> 00537 struct edge_property_type< vtkMutableDirectedGraph* > 00538 : edge_property_type< vtkDirectedGraph* > { }; 00539 00540 // Internal edge properties 00541 template<> 00542 struct edge_property_type< vtkMutableDirectedGraph* const > 00543 : edge_property_type< vtkDirectedGraph* > { }; 00544 00545 //=========================================================================== 00546 // vtkMutableUndirectedGraph 00547 00548 template <> 00549 struct graph_traits<vtkMutableUndirectedGraph*> : graph_traits<vtkUndirectedGraph*> { }; 00550 00551 // The graph_traits for a const graph are the same as a non-const graph. 00552 template <> 00553 struct graph_traits<const vtkMutableUndirectedGraph*> : graph_traits<vtkMutableUndirectedGraph*> { }; 00554 00555 // The graph_traits for a const graph are the same as a non-const graph. 00556 template <> 00557 struct graph_traits<vtkMutableUndirectedGraph* const> : graph_traits<vtkMutableUndirectedGraph*> { }; 00558 00559 // Internal vertex properties 00560 template<> 00561 struct vertex_property_type< vtkMutableUndirectedGraph* > 00562 : vertex_property_type< vtkUndirectedGraph* > { }; 00563 00564 // Internal vertex properties 00565 template<> 00566 struct vertex_property_type< vtkMutableUndirectedGraph* const > 00567 : vertex_property_type< vtkUndirectedGraph* > { }; 00568 00569 // Internal edge properties 00570 template<> 00571 struct edge_property_type< vtkMutableUndirectedGraph* > 00572 : edge_property_type< vtkUndirectedGraph* > { }; 00573 00574 // Internal edge properties 00575 template<> 00576 struct edge_property_type< vtkMutableUndirectedGraph* const > 00577 : edge_property_type< vtkUndirectedGraph* > { }; 00578 00579 //=========================================================================== 00580 // API implementation 00581 template <> 00582 class vertex_property< vtkGraph* > { 00583 public: 00584 typedef vtkIdType type; 00585 }; 00586 00587 template <> 00588 class edge_property< vtkGraph* > { 00589 public: 00590 typedef vtkIdType type; 00591 }; 00592 } // end namespace boost 00593 00594 inline boost::graph_traits< vtkGraph* >::vertex_descriptor 00595 source(boost::graph_traits< vtkGraph* >::edge_descriptor e, 00596 vtkGraph *) 00597 { 00598 return e.Source; 00599 } 00600 00601 inline boost::graph_traits< vtkGraph* >::vertex_descriptor 00602 target(boost::graph_traits< vtkGraph* >::edge_descriptor e, 00603 vtkGraph *) 00604 { 00605 return e.Target; 00606 } 00607 00608 inline vtksys_stl::pair< 00609 boost::graph_traits< vtkGraph* >::vertex_iterator, 00610 boost::graph_traits< vtkGraph* >::vertex_iterator > 00611 vertices(vtkGraph *g) 00612 { 00613 typedef boost::graph_traits< vtkGraph* >::vertex_iterator Iter; 00614 vtkIdType start = 0; 00615 if (vtkDistributedGraphHelper *helper = g->GetDistributedGraphHelper()) 00616 { 00617 int rank = 00618 g->GetInformation()->Get(vtkDataObject::DATA_PIECE_NUMBER()); 00619 start = helper->MakeDistributedId(rank, start); 00620 } 00621 00622 return vtksys_stl::make_pair( Iter(start), 00623 Iter(start + g->GetNumberOfVertices()) ); 00624 } 00625 00626 inline vtksys_stl::pair< 00627 boost::graph_traits< vtkGraph* >::edge_iterator, 00628 boost::graph_traits< vtkGraph* >::edge_iterator > 00629 edges(vtkGraph *g) 00630 { 00631 typedef boost::graph_traits< vtkGraph* >::edge_iterator Iter; 00632 return vtksys_stl::make_pair( Iter(g), Iter(g, g->GetNumberOfVertices()) ); 00633 } 00634 00635 inline vtksys_stl::pair< 00636 boost::graph_traits< vtkGraph* >::out_edge_iterator, 00637 boost::graph_traits< vtkGraph* >::out_edge_iterator > 00638 out_edges( 00639 boost::graph_traits< vtkGraph* >::vertex_descriptor u, 00640 vtkGraph *g) 00641 { 00642 typedef boost::graph_traits< vtkGraph* >::out_edge_iterator Iter; 00643 vtksys_stl::pair<Iter, Iter> p = vtksys_stl::make_pair( Iter(g, u), Iter(g, u, true) ); 00644 return p; 00645 } 00646 00647 inline vtksys_stl::pair< 00648 boost::graph_traits< vtkGraph* >::in_edge_iterator, 00649 boost::graph_traits< vtkGraph* >::in_edge_iterator > 00650 in_edges( 00651 boost::graph_traits< vtkGraph* >::vertex_descriptor u, 00652 vtkGraph *g) 00653 { 00654 typedef boost::graph_traits< vtkGraph* >::in_edge_iterator Iter; 00655 vtksys_stl::pair<Iter, Iter> p = vtksys_stl::make_pair( Iter(g, u), Iter(g, u, true) ); 00656 return p; 00657 } 00658 00659 inline vtksys_stl::pair< 00660 boost::graph_traits< vtkGraph* >::adjacency_iterator, 00661 boost::graph_traits< vtkGraph* >::adjacency_iterator > 00662 adjacent_vertices( 00663 boost::graph_traits< vtkGraph* >::vertex_descriptor u, 00664 vtkGraph *g) 00665 { 00666 typedef boost::graph_traits< vtkGraph* >::adjacency_iterator Iter; 00667 typedef boost::graph_traits< vtkGraph* >::out_edge_iterator OutEdgeIter; 00668 vtksys_stl::pair<OutEdgeIter, OutEdgeIter> out = out_edges(u, g); 00669 return vtksys_stl::make_pair( Iter(out.first, &g), Iter(out.second, &g) ); 00670 } 00671 00672 inline boost::graph_traits< vtkGraph* >::vertices_size_type 00673 num_vertices(vtkGraph *g) 00674 { 00675 return g->GetNumberOfVertices(); 00676 } 00677 00678 inline boost::graph_traits< vtkGraph* >::edges_size_type 00679 num_edges(vtkGraph *g) 00680 { 00681 return g->GetNumberOfEdges(); 00682 } 00683 00684 inline boost::graph_traits< vtkGraph* >::degree_size_type 00685 out_degree( 00686 boost::graph_traits< vtkGraph* >::vertex_descriptor u, 00687 vtkGraph *g) 00688 { 00689 return g->GetOutDegree(u); 00690 } 00691 00692 inline boost::graph_traits< vtkDirectedGraph* >::degree_size_type 00693 in_degree( 00694 boost::graph_traits< vtkDirectedGraph* >::vertex_descriptor u, 00695 vtkDirectedGraph *g) 00696 { 00697 return g->GetInDegree(u); 00698 } 00699 00700 inline boost::graph_traits< vtkGraph* >::degree_size_type 00701 degree( 00702 boost::graph_traits< vtkGraph* >::vertex_descriptor u, 00703 vtkGraph *g) 00704 { 00705 return g->GetDegree(u); 00706 } 00707 00708 inline boost::graph_traits< vtkMutableDirectedGraph* >::vertex_descriptor 00709 add_vertex(vtkMutableDirectedGraph *g) 00710 { 00711 return g->AddVertex(); 00712 } 00713 00714 inline vtksys_stl::pair< 00715 boost::graph_traits< vtkMutableDirectedGraph* >::edge_descriptor, 00716 bool> 00717 add_edge( 00718 boost::graph_traits< vtkMutableDirectedGraph* >::vertex_descriptor u, 00719 boost::graph_traits< vtkMutableDirectedGraph* >::vertex_descriptor v, 00720 vtkMutableDirectedGraph *g) 00721 { 00722 boost::graph_traits< vtkMutableDirectedGraph* >::edge_descriptor e = g->AddEdge(u, v); 00723 return vtksys_stl::make_pair(e, true); 00724 } 00725 00726 inline boost::graph_traits< vtkMutableUndirectedGraph* >::vertex_descriptor 00727 add_vertex(vtkMutableUndirectedGraph *g) 00728 { 00729 return g->AddVertex(); 00730 } 00731 00732 inline vtksys_stl::pair< 00733 boost::graph_traits< vtkMutableUndirectedGraph* >::edge_descriptor, 00734 bool> 00735 add_edge( 00736 boost::graph_traits< vtkMutableUndirectedGraph* >::vertex_descriptor u, 00737 boost::graph_traits< vtkMutableUndirectedGraph* >::vertex_descriptor v, 00738 vtkMutableUndirectedGraph *g) 00739 { 00740 boost::graph_traits< vtkMutableUndirectedGraph* >::edge_descriptor e = g->AddEdge(u, v); 00741 return vtksys_stl::make_pair(e, true); 00742 } 00743 00744 namespace boost { 00745 //=========================================================================== 00746 // An edge map for vtkGraph. 00747 // This is a common input needed for algorithms. 00748 00749 struct vtkGraphEdgeMap { }; 00750 00751 template <> 00752 struct property_traits<vtkGraphEdgeMap> 00753 { 00754 typedef vtkIdType value_type; 00755 typedef vtkIdType reference; 00756 typedef vtkEdgeType key_type; 00757 typedef readable_property_map_tag category; 00758 }; 00759 00760 inline property_traits<vtkGraphEdgeMap>::reference 00761 get( 00762 vtkGraphEdgeMap vtkNotUsed(arr), 00763 property_traits<vtkGraphEdgeMap>::key_type key) 00764 { 00765 return key.Id; 00766 } 00767 00768 //=========================================================================== 00769 // Helper for vtkGraph edge property maps 00770 // Automatically converts boost edge ids to vtkGraph edge ids. 00771 00772 template<typename PMap> 00773 class vtkGraphEdgePropertyMapHelper 00774 { 00775 public: 00776 vtkGraphEdgePropertyMapHelper(PMap m) : pmap(m) { } 00777 PMap pmap; 00778 typedef typename property_traits<PMap>::value_type value_type; 00779 typedef typename property_traits<PMap>::reference reference; 00780 typedef vtkEdgeType key_type; 00781 typedef typename property_traits<PMap>::category category; 00782 }; 00783 00784 template<typename PMap> 00785 inline typename property_traits<PMap>::reference 00786 get( 00787 vtkGraphEdgePropertyMapHelper<PMap> helper, 00788 vtkEdgeType key) 00789 { 00790 return get(helper.pmap, key.Id); 00791 } 00792 00793 template<typename PMap> 00794 inline void 00795 put( 00796 vtkGraphEdgePropertyMapHelper<PMap> helper, 00797 vtkEdgeType key, 00798 const typename property_traits<PMap>::value_type & value) 00799 { 00800 put(helper.pmap, key.Id, value); 00801 } 00802 00803 //=========================================================================== 00804 // An index map for vtkGraph 00805 // This is a common input needed for algorithms 00806 00807 struct vtkGraphIndexMap { }; 00808 00809 template <> 00810 struct property_traits<vtkGraphIndexMap> 00811 { 00812 typedef vtkIdType value_type; 00813 typedef vtkIdType reference; 00814 typedef vtkIdType key_type; 00815 typedef readable_property_map_tag category; 00816 }; 00817 00818 inline property_traits<vtkGraphIndexMap>::reference 00819 get( 00820 vtkGraphIndexMap vtkNotUsed(arr), 00821 property_traits<vtkGraphIndexMap>::key_type key) 00822 { 00823 return key; 00824 } 00825 00826 //=========================================================================== 00827 // Helper for vtkGraph property maps 00828 // Automatically multiplies the property value by some value (default 1) 00829 template<typename PMap> 00830 class vtkGraphPropertyMapMultiplier 00831 { 00832 public: 00833 vtkGraphPropertyMapMultiplier(PMap m, float multi=1) : pmap(m),multiplier(multi){} 00834 PMap pmap; 00835 float multiplier; 00836 typedef typename property_traits<PMap>::value_type value_type; 00837 typedef typename property_traits<PMap>::reference reference; 00838 typedef typename property_traits<PMap>::key_type key_type; 00839 typedef typename property_traits<PMap>::category category; 00840 }; 00841 00842 template<typename PMap> 00843 inline typename property_traits<PMap>::reference 00844 get( 00845 vtkGraphPropertyMapMultiplier<PMap> multi, 00846 const typename property_traits<PMap>::key_type key) 00847 { 00848 return multi.multiplier * get(multi.pmap, key); 00849 } 00850 00851 template<typename PMap> 00852 inline void 00853 put( 00854 vtkGraphPropertyMapMultiplier<PMap> multi, 00855 const typename property_traits<PMap>::key_type key, 00856 const typename property_traits<PMap>::value_type & value) 00857 { 00858 put(multi.pmap, key, value); 00859 } 00860 00861 // Allow algorithms to automatically extract vtkGraphIndexMap from a 00862 // VTK graph 00863 template<> 00864 struct property_map<vtkGraph*, vertex_index_t> 00865 { 00866 typedef vtkGraphIndexMap type; 00867 typedef vtkGraphIndexMap const_type; 00868 }; 00869 00870 template<> 00871 struct property_map<vtkDirectedGraph*, vertex_index_t> 00872 : property_map<vtkGraph*, vertex_index_t> { }; 00873 00874 template<> 00875 struct property_map<vtkUndirectedGraph*, vertex_index_t> 00876 : property_map<vtkGraph*, vertex_index_t> { }; 00877 00878 inline vtkGraphIndexMap get(vertex_index_t, vtkGraph*) { return vtkGraphIndexMap(); } 00879 00880 template<> 00881 struct property_map<vtkGraph*, edge_index_t> 00882 { 00883 typedef vtkGraphIndexMap type; 00884 typedef vtkGraphIndexMap const_type; 00885 }; 00886 00887 template<> 00888 struct property_map<vtkDirectedGraph*, edge_index_t> 00889 : property_map<vtkGraph*, edge_index_t> { }; 00890 00891 template<> 00892 struct property_map<vtkUndirectedGraph*, edge_index_t> 00893 : property_map<vtkGraph*, edge_index_t> { }; 00894 00895 inline vtkGraphIndexMap get(edge_index_t, vtkGraph*) { return vtkGraphIndexMap(); } 00896 00897 // property_map specializations for const-qualified graphs 00898 template<> 00899 struct property_map<vtkDirectedGraph* const, vertex_index_t> 00900 : property_map<vtkDirectedGraph*, vertex_index_t> { }; 00901 00902 template<> 00903 struct property_map<vtkUndirectedGraph* const, vertex_index_t> 00904 : property_map<vtkUndirectedGraph*, vertex_index_t> { }; 00905 00906 template<> 00907 struct property_map<vtkDirectedGraph* const, edge_index_t> 00908 : property_map<vtkDirectedGraph*, edge_index_t> { }; 00909 00910 template<> 00911 struct property_map<vtkUndirectedGraph* const, edge_index_t> 00912 : property_map<vtkUndirectedGraph*, edge_index_t> { }; 00913 00914 } // namespace boost 00915 00916 #include <boost/version.hpp> 00917 #if BOOST_VERSION > 104000 00918 #include <boost/property_map/vector_property_map.hpp> 00919 #else 00920 #include <boost/vector_property_map.hpp> 00921 #endif 00922 00923 00924 #endif // __vtkBoostGraphAdapter_h