VTK  9.0.1
vtkBoostGraphAdapter.h
Go to the documentation of this file.
1 /*=========================================================================
2 
3  Program: Visualization Toolkit
4  Module: vtkBoostGraphAdapter.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 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 -------------------------------------------------------------------------*/
30 #ifndef vtkBoostGraphAdapter_h
31 #define vtkBoostGraphAdapter_h
32 
33 #include "vtkAbstractArray.h"
34 #include "vtkDataArray.h"
35 #include "vtkDataObject.h"
36 #include "vtkDirectedGraph.h"
38 #include "vtkDoubleArray.h"
39 #include "vtkFloatArray.h"
40 #include "vtkIdTypeArray.h"
41 #include "vtkInformation.h"
42 #include "vtkIntArray.h"
45 #include "vtkTree.h"
46 #include "vtkUndirectedGraph.h"
47 #include "vtkVariant.h"
48 
49 #include <boost/version.hpp>
50 
51 namespace boost
52 {
53 //===========================================================================
54 // VTK arrays as property maps
55 // These need to be defined before including other boost stuff
56 
57 // Forward declarations are required here, so that we aren't forced
58 // to include boost/property_map.hpp.
59 template <typename>
61 struct read_write_property_map_tag;
62 
63 #define vtkPropertyMapMacro(T, V) \
64  template <> \
65  struct property_traits<T*> \
66  { \
67  typedef V value_type; \
68  typedef V reference; \
69  typedef vtkIdType key_type; \
70  typedef read_write_property_map_tag category; \
71  }; \
72  \
73  inline property_traits<T*>::reference get(T* const& arr, property_traits<T*>::key_type key) \
74  { \
75  return arr->GetValue(key); \
76  } \
77  \
78  inline void put( \
79  T* arr, property_traits<T*>::key_type key, const property_traits<T*>::value_type& value) \
80  { \
81  arr->InsertValue(key, value); \
82  }
83 
88 
89 // vtkDataArray
90 template <>
92 {
93  typedef double value_type;
94  typedef double reference;
96  typedef read_write_property_map_tag category;
97 };
98 
99 inline double get(vtkDataArray* const& arr, vtkIdType key)
100 {
101  return arr->GetTuple1(key);
102 }
103 
104 inline void put(vtkDataArray* arr, vtkIdType key, const double& value)
105 {
106  arr->SetTuple1(key, value);
107 }
108 
109 // vtkAbstractArray as a property map of vtkVariants
110 template <>
112 {
116  typedef read_write_property_map_tag category;
117 };
118 
119 inline vtkVariant get(vtkAbstractArray* const& arr, vtkIdType key)
120 {
121  return arr->GetVariantValue(key);
122 }
123 
124 inline void put(vtkAbstractArray* arr, vtkIdType key, const vtkVariant& value)
125 {
127 }
128 #if defined(_MSC_VER)
129 namespace detail
130 {
133 }
134 #endif
135 }
136 
137 #include <utility> // STL Header
138 
139 #include <boost/config.hpp>
140 #include <boost/graph/adjacency_iterator.hpp>
141 #include <boost/graph/graph_traits.hpp>
142 #include <boost/graph/properties.hpp>
143 #include <boost/iterator/iterator_facade.hpp>
144 
145 // The functions and classes in this file allows the user to
146 // treat a vtkDirectedGraph or vtkUndirectedGraph object
147 // as a boost graph "as is".
148 
149 namespace boost
150 {
151 
153  : public iterator_facade<vtk_vertex_iterator, vtkIdType, bidirectional_traversal_tag,
154  const vtkIdType&, vtkIdType>
155 {
156 public:
158  : index(i)
159  {
160  }
161 
162 private:
163  const vtkIdType& dereference() const { return index; }
164 
165  bool equal(const vtk_vertex_iterator& other) const { return index == other.index; }
166 
167  void increment() { index++; }
168  void decrement() { index--; }
169 
170  vtkIdType index;
171 
172  friend class iterator_core_access;
173 };
174 
176  : public iterator_facade<vtk_edge_iterator, vtkEdgeType, forward_traversal_tag,
177  const vtkEdgeType&, vtkIdType>
178 {
179 public:
180  explicit vtk_edge_iterator(vtkGraph* g = 0, vtkIdType v = 0)
181  : directed(false)
182  , vertex(v)
183  , lastVertex(v)
184  , iter(nullptr)
185  , end(nullptr)
186  , graph(g)
187  {
188  if (graph)
189  {
190  lastVertex = graph->GetNumberOfVertices();
191  }
192 
193  vtkIdType myRank = -1;
194  vtkDistributedGraphHelper* helper = this->graph ? this->graph->GetDistributedGraphHelper() : 0;
195  if (helper)
196  {
197  myRank = this->graph->GetInformation()->Get(vtkDataObject::DATA_PIECE_NUMBER());
198  vertex = helper->MakeDistributedId(myRank, vertex);
199  lastVertex = helper->MakeDistributedId(myRank, lastVertex);
200  }
201 
202  if (graph != 0)
203  {
204  directed = (vtkDirectedGraph::SafeDownCast(graph) != 0);
205  while (vertex < lastVertex && this->graph->GetOutDegree(vertex) == 0)
206  {
207  ++vertex;
208  }
209 
210  if (vertex < lastVertex)
211  {
212  // Get the outgoing edges of the first vertex that has outgoing
213  // edges
214  vtkIdType nedges;
215  graph->GetOutEdges(vertex, iter, nedges);
216  if (iter)
217  {
218  end = iter + nedges;
219 
220  if (!directed)
221  {
222  while ( // Skip non-local edges
223  (helper && helper->GetEdgeOwner(iter->Id) != myRank)
224  // Skip entirely-local edges where Source > Target
225  || (((helper && myRank == helper->GetVertexOwner(iter->Target)) || !helper) &&
226  vertex > iter->Target))
227  {
228  this->inc();
229  }
230  }
231  }
232  }
233  else
234  {
235  iter = nullptr;
236  }
237  }
238 
239  RecalculateEdge();
240  }
241 
242 private:
243  const vtkEdgeType& dereference() const
244  {
245  assert(iter);
246  return edge;
247  }
248 
249  bool equal(const vtk_edge_iterator& other) const
250  {
251  return vertex == other.vertex && iter == other.iter;
252  }
253 
254  void increment()
255  {
256  inc();
257  if (!directed)
258  {
259  vtkIdType myRank = -1;
260  vtkDistributedGraphHelper* helper =
261  this->graph ? this->graph->GetDistributedGraphHelper() : 0;
262  if (helper)
263  {
264  myRank = this->graph->GetInformation()->Get(vtkDataObject::DATA_PIECE_NUMBER());
265  }
266 
267  while (iter != 0 &&
268  ( // Skip non-local edges
269  (helper && helper->GetEdgeOwner(iter->Id) != myRank)
270  // Skip entirely-local edges where Source > Target
271  || (((helper && myRank == helper->GetVertexOwner(iter->Target)) || !helper) &&
272  vertex > iter->Target)))
273  {
274  inc();
275  }
276  }
277  RecalculateEdge();
278  }
279 
280  void inc()
281  {
282  ++iter;
283  if (iter == end)
284  {
285  // Find a vertex with nonzero out degree.
286  ++vertex;
287  while (vertex < lastVertex && this->graph->GetOutDegree(vertex) == 0)
288  {
289  ++vertex;
290  }
291 
292  if (vertex < lastVertex)
293  {
294  vtkIdType nedges;
295  graph->GetOutEdges(vertex, iter, nedges);
296  end = iter + nedges;
297  }
298  else
299  {
300  iter = nullptr;
301  }
302  }
303  }
304 
305  void RecalculateEdge()
306  {
307  if (iter)
308  {
309  edge = vtkEdgeType(vertex, iter->Target, iter->Id);
310  }
311  }
312 
313  bool directed;
314  vtkIdType vertex;
315  vtkIdType lastVertex;
316  const vtkOutEdgeType* iter;
317  const vtkOutEdgeType* end;
318  vtkGraph* graph;
319  vtkEdgeType edge;
320 
321  friend class iterator_core_access;
322 };
323 
325  : public iterator_facade<vtk_out_edge_pointer_iterator, vtkEdgeType, bidirectional_traversal_tag,
326  const vtkEdgeType&, ptrdiff_t>
327 {
328 public:
329  explicit vtk_out_edge_pointer_iterator(vtkGraph* g = 0, vtkIdType v = 0, bool end = false)
330  : vertex(v)
331  , iter(nullptr)
332  {
333  if (g)
334  {
335  vtkIdType nedges;
336  g->GetOutEdges(vertex, iter, nedges);
337  if (end)
338  {
339  iter += nedges;
340  }
341  }
342  RecalculateEdge();
343  }
344 
345 private:
346  const vtkEdgeType& dereference() const
347  {
348  assert(iter);
349  return edge;
350  }
351 
352  bool equal(const vtk_out_edge_pointer_iterator& other) const { return iter == other.iter; }
353 
354  void increment()
355  {
356  iter++;
357  RecalculateEdge();
358  }
359 
360  void decrement()
361  {
362  iter--;
363  RecalculateEdge();
364  }
365 
366  void RecalculateEdge()
367  {
368  if (iter)
369  {
370  edge = vtkEdgeType(vertex, iter->Target, iter->Id);
371  }
372  }
373 
374  vtkIdType vertex;
375  const vtkOutEdgeType* iter;
376  vtkEdgeType edge;
377 
378  friend class iterator_core_access;
379 };
380 
382  : public iterator_facade<vtk_in_edge_pointer_iterator, vtkEdgeType, bidirectional_traversal_tag,
383  const vtkEdgeType&, ptrdiff_t>
384 {
385 public:
386  explicit vtk_in_edge_pointer_iterator(vtkGraph* g = 0, vtkIdType v = 0, bool end = false)
387  : vertex(v)
388  , iter(nullptr)
389  {
390  if (g)
391  {
392  vtkIdType nedges;
393  g->GetInEdges(vertex, iter, nedges);
394  if (end)
395  {
396  iter += nedges;
397  }
398  }
399  RecalculateEdge();
400  }
401 
402 private:
403  const vtkEdgeType& dereference() const
404  {
405  assert(iter);
406  return edge;
407  }
408 
409  bool equal(const vtk_in_edge_pointer_iterator& other) const { return iter == other.iter; }
410 
411  void increment()
412  {
413  iter++;
414  RecalculateEdge();
415  }
416 
417  void decrement()
418  {
419  iter--;
420  RecalculateEdge();
421  }
422 
423  void RecalculateEdge()
424  {
425  if (iter)
426  {
427  edge = vtkEdgeType(iter->Source, vertex, iter->Id);
428  }
429  }
430 
431  vtkIdType vertex;
432  const vtkInEdgeType* iter;
433  vtkEdgeType edge;
434 
435  friend class iterator_core_access;
436 };
437 
438 //===========================================================================
439 // vtkGraph
440 // VertexAndEdgeListGraphConcept
441 // BidirectionalGraphConcept
442 // AdjacencyGraphConcept
443 
445  : public virtual bidirectional_graph_tag
446  , public virtual edge_list_graph_tag
447  , public virtual vertex_list_graph_tag
448  , public virtual adjacency_graph_tag
449 {
450 };
451 
452 template <>
453 struct graph_traits<vtkGraph*>
454 {
456  static vertex_descriptor null_vertex() { return -1; }
458  static edge_descriptor null_edge() { return vtkEdgeType(-1, -1, -1); }
461 
464 
465  typedef allow_parallel_edge_tag edge_parallel_category;
470 
473 };
474 
475 #if BOOST_VERSION >= 104500
476 template <>
477 struct graph_property_type<vtkGraph*>
478 {
479  typedef no_property type;
480 };
481 #endif
482 
483 template <>
484 struct vertex_property_type<vtkGraph*>
485 {
486  typedef no_property type;
487 };
488 
489 template <>
490 struct edge_property_type<vtkGraph*>
491 {
492  typedef no_property type;
493 };
494 
495 #if BOOST_VERSION >= 104500
496 template <>
497 struct graph_bundle_type<vtkGraph*>
498 {
499  typedef no_property type;
500 };
501 #endif
502 
503 template <>
504 struct vertex_bundle_type<vtkGraph*>
505 {
506  typedef no_property type;
507 };
508 
509 template <>
510 struct edge_bundle_type<vtkGraph*>
511 {
512  typedef no_property type;
513 };
514 
515 inline bool has_no_edges(vtkGraph* g)
516 {
517  return ((g->GetNumberOfEdges() > 0) ? false : true);
518 }
519 
520 inline void remove_edge(graph_traits<vtkGraph*>::edge_descriptor e, vtkGraph* g)
521 {
523  {
525  }
527  {
529  }
530 }
531 
532 //===========================================================================
533 // vtkDirectedGraph
534 
535 template <>
537 {
538  typedef directed_tag directed_category;
539 };
540 
541 // The graph_traits for a const graph are the same as a non-const graph.
542 template <>
544 {
545 };
546 
547 // The graph_traits for a const graph are the same as a non-const graph.
548 template <>
550 {
551 };
552 
553 #if BOOST_VERSION >= 104500
554 // Internal graph properties
555 template <>
556 struct graph_property_type<vtkDirectedGraph*> : graph_property_type<vtkGraph*>
557 {
558 };
559 
560 // Internal graph properties
561 template <>
562 struct graph_property_type<vtkDirectedGraph* const> : graph_property_type<vtkGraph*>
563 {
564 };
565 #endif
566 
567 // Internal vertex properties
568 template <>
569 struct vertex_property_type<vtkDirectedGraph*> : vertex_property_type<vtkGraph*>
570 {
571 };
572 
573 // Internal vertex properties
574 template <>
575 struct vertex_property_type<vtkDirectedGraph* const> : vertex_property_type<vtkGraph*>
576 {
577 };
578 
579 // Internal edge properties
580 template <>
581 struct edge_property_type<vtkDirectedGraph*> : edge_property_type<vtkGraph*>
582 {
583 };
584 
585 // Internal edge properties
586 template <>
587 struct edge_property_type<vtkDirectedGraph* const> : edge_property_type<vtkGraph*>
588 {
589 };
590 
591 #if BOOST_VERSION >= 104500
592 // Internal graph properties
593 template <>
594 struct graph_bundle_type<vtkDirectedGraph*> : graph_bundle_type<vtkGraph*>
595 {
596 };
597 
598 // Internal graph properties
599 template <>
600 struct graph_bundle_type<vtkDirectedGraph* const> : graph_bundle_type<vtkGraph*>
601 {
602 };
603 #endif
604 
605 // Internal vertex properties
606 template <>
607 struct vertex_bundle_type<vtkDirectedGraph*> : vertex_bundle_type<vtkGraph*>
608 {
609 };
610 
611 // Internal vertex properties
612 template <>
613 struct vertex_bundle_type<vtkDirectedGraph* const> : vertex_bundle_type<vtkGraph*>
614 {
615 };
616 
617 // Internal edge properties
618 template <>
620 {
621 };
622 
623 // Internal edge properties
624 template <>
625 struct edge_bundle_type<vtkDirectedGraph* const> : edge_bundle_type<vtkGraph*>
626 {
627 };
628 
629 //===========================================================================
630 // vtkTree
631 
632 template <>
634 {
635 };
636 
637 // The graph_traits for a const graph are the same as a non-const graph.
638 template <>
639 struct graph_traits<const vtkTree*> : graph_traits<vtkTree*>
640 {
641 };
642 
643 // The graph_traits for a const graph are the same as a non-const graph.
644 template <>
645 struct graph_traits<vtkTree* const> : graph_traits<vtkTree*>
646 {
647 };
648 
649 //===========================================================================
650 // vtkUndirectedGraph
651 template <>
653 {
654  typedef undirected_tag directed_category;
655 };
656 
657 // The graph_traits for a const graph are the same as a non-const graph.
658 template <>
660 {
661 };
662 
663 // The graph_traits for a const graph are the same as a non-const graph.
664 template <>
666 {
667 };
668 
669 #if BOOST_VERSION >= 104500
670 // Internal graph properties
671 template <>
672 struct graph_property_type<vtkUndirectedGraph*> : graph_property_type<vtkGraph*>
673 {
674 };
675 
676 // Internal graph properties
677 template <>
678 struct graph_property_type<vtkUndirectedGraph* const> : graph_property_type<vtkGraph*>
679 {
680 };
681 #endif
682 
683 // Internal vertex properties
684 template <>
686 {
687 };
688 
689 // Internal vertex properties
690 template <>
691 struct vertex_property_type<vtkUndirectedGraph* const> : vertex_property_type<vtkGraph*>
692 {
693 };
694 
695 // Internal edge properties
696 template <>
698 {
699 };
700 
701 // Internal edge properties
702 template <>
703 struct edge_property_type<vtkUndirectedGraph* const> : edge_property_type<vtkGraph*>
704 {
705 };
706 
707 #if BOOST_VERSION >= 104500
708 // Internal graph properties
709 template <>
710 struct graph_bundle_type<vtkUndirectedGraph*> : graph_bundle_type<vtkGraph*>
711 {
712 };
713 
714 // Internal graph properties
715 template <>
716 struct graph_bundle_type<vtkUndirectedGraph* const> : graph_bundle_type<vtkGraph*>
717 {
718 };
719 #endif
720 
721 // Internal vertex properties
722 template <>
724 {
725 };
726 
727 // Internal vertex properties
728 template <>
729 struct vertex_bundle_type<vtkUndirectedGraph* const> : vertex_bundle_type<vtkGraph*>
730 {
731 };
732 
733 // Internal edge properties
734 template <>
736 {
737 };
738 
739 // Internal edge properties
740 template <>
741 struct edge_bundle_type<vtkUndirectedGraph* const> : edge_bundle_type<vtkGraph*>
742 {
743 };
744 
745 //===========================================================================
746 // vtkMutableDirectedGraph
747 
748 template <>
750 {
751 };
752 
753 // The graph_traits for a const graph are the same as a non-const graph.
754 template <>
756 {
757 };
758 
759 // The graph_traits for a const graph are the same as a non-const graph.
760 template <>
762 {
763 };
764 
765 #if BOOST_VERSION >= 104500
766 // Internal graph properties
767 template <>
768 struct graph_property_type<vtkMutableDirectedGraph*> : graph_property_type<vtkDirectedGraph*>
769 {
770 };
771 
772 // Internal graph properties
773 template <>
774 struct graph_property_type<vtkMutableDirectedGraph* const> : graph_property_type<vtkDirectedGraph*>
775 {
776 };
777 #endif
778 
779 // Internal vertex properties
780 template <>
782 {
783 };
784 
785 // Internal vertex properties
786 template <>
787 struct vertex_property_type<vtkMutableDirectedGraph* const>
789 {
790 };
791 
792 // Internal edge properties
793 template <>
795 {
796 };
797 
798 // Internal edge properties
799 template <>
801 {
802 };
803 
804 #if BOOST_VERSION >= 104500
805 // Internal graph properties
806 template <>
807 struct graph_bundle_type<vtkMutableDirectedGraph*> : graph_bundle_type<vtkDirectedGraph*>
808 {
809 };
810 
811 // Internal graph properties
812 template <>
813 struct graph_bundle_type<vtkMutableDirectedGraph* const> : graph_bundle_type<vtkDirectedGraph*>
814 {
815 };
816 #endif
817 
818 // Internal vertex properties
819 template <>
821 {
822 };
823 
824 // Internal vertex properties
825 template <>
827 {
828 };
829 
830 // Internal edge properties
831 template <>
833 {
834 };
835 
836 // Internal edge properties
837 template <>
839 {
840 };
841 
842 //===========================================================================
843 // vtkMutableUndirectedGraph
844 
845 template <>
847 {
848 };
849 
850 // The graph_traits for a const graph are the same as a non-const graph.
851 template <>
853 {
854 };
855 
856 // The graph_traits for a const graph are the same as a non-const graph.
857 template <>
859 {
860 };
861 
862 #if BOOST_VERSION >= 104500
863 // Internal graph properties
864 template <>
865 struct graph_property_type<vtkMutableUndirectedGraph*> : graph_property_type<vtkUndirectedGraph*>
866 {
867 };
868 
869 // Internal graph properties
870 template <>
871 struct graph_property_type<vtkMutableUndirectedGraph* const>
872  : graph_property_type<vtkUndirectedGraph*>
873 {
874 };
875 #endif
876 
877 // Internal vertex properties
878 template <>
880 {
881 };
882 
883 // Internal vertex properties
884 template <>
885 struct vertex_property_type<vtkMutableUndirectedGraph* const>
887 {
888 };
889 
890 // Internal edge properties
891 template <>
893 {
894 };
895 
896 // Internal edge properties
897 template <>
898 struct edge_property_type<vtkMutableUndirectedGraph* const>
900 {
901 };
902 
903 #if BOOST_VERSION >= 104500
904 // Internal graph properties
905 template <>
906 struct graph_bundle_type<vtkMutableUndirectedGraph*> : graph_bundle_type<vtkUndirectedGraph*>
907 {
908 };
909 
910 // Internal graph properties
911 template <>
912 struct graph_bundle_type<vtkMutableUndirectedGraph* const> : graph_bundle_type<vtkUndirectedGraph*>
913 {
914 };
915 #endif
916 
917 // Internal vertex properties
918 template <>
920 {
921 };
922 
923 // Internal vertex properties
924 template <>
925 struct vertex_bundle_type<vtkMutableUndirectedGraph* const>
927 {
928 };
929 
930 // Internal edge properties
931 template <>
933 {
934 };
935 
936 // Internal edge properties
937 template <>
939 {
940 };
941 
942 //===========================================================================
943 // API implementation
944 template <>
945 class vertex_property<vtkGraph*>
946 {
947 public:
948  typedef vtkIdType type;
949 };
950 
951 template <>
952 class edge_property<vtkGraph*>
953 {
954 public:
955  typedef vtkIdType type;
956 };
957 } // end namespace boost
958 
959 inline boost::graph_traits<vtkGraph*>::vertex_descriptor source(
960  boost::graph_traits<vtkGraph*>::edge_descriptor e, vtkGraph*)
961 {
962  return e.Source;
963 }
964 
965 inline boost::graph_traits<vtkGraph*>::vertex_descriptor target(
966  boost::graph_traits<vtkGraph*>::edge_descriptor e, vtkGraph*)
967 {
968  return e.Target;
969 }
970 
971 inline std::pair<boost::graph_traits<vtkGraph*>::vertex_iterator,
972  boost::graph_traits<vtkGraph*>::vertex_iterator>
974 {
975  typedef boost::graph_traits<vtkGraph*>::vertex_iterator Iter;
976  vtkIdType start = 0;
978  {
980  start = helper->MakeDistributedId(rank, start);
981  }
982 
983  return std::make_pair(Iter(start), Iter(start + g->GetNumberOfVertices()));
984 }
985 
986 inline std::pair<boost::graph_traits<vtkGraph*>::edge_iterator,
987  boost::graph_traits<vtkGraph*>::edge_iterator>
989 {
990  typedef boost::graph_traits<vtkGraph*>::edge_iterator Iter;
991  return std::make_pair(Iter(g), Iter(g, g->GetNumberOfVertices()));
992 }
993 
994 inline std::pair<boost::graph_traits<vtkGraph*>::out_edge_iterator,
995  boost::graph_traits<vtkGraph*>::out_edge_iterator>
996 out_edges(boost::graph_traits<vtkGraph*>::vertex_descriptor u, vtkGraph* g)
997 {
998  typedef boost::graph_traits<vtkGraph*>::out_edge_iterator Iter;
999  std::pair<Iter, Iter> p = std::make_pair(Iter(g, u), Iter(g, u, true));
1000  return p;
1001 }
1002 
1003 inline std::pair<boost::graph_traits<vtkGraph*>::in_edge_iterator,
1004  boost::graph_traits<vtkGraph*>::in_edge_iterator>
1005 in_edges(boost::graph_traits<vtkGraph*>::vertex_descriptor u, vtkGraph* g)
1006 {
1007  typedef boost::graph_traits<vtkGraph*>::in_edge_iterator Iter;
1008  std::pair<Iter, Iter> p = std::make_pair(Iter(g, u), Iter(g, u, true));
1009  return p;
1010 }
1011 
1012 inline std::pair<boost::graph_traits<vtkGraph*>::adjacency_iterator,
1013  boost::graph_traits<vtkGraph*>::adjacency_iterator>
1014 adjacent_vertices(boost::graph_traits<vtkGraph*>::vertex_descriptor u, vtkGraph* g)
1015 {
1016  typedef boost::graph_traits<vtkGraph*>::adjacency_iterator Iter;
1017  typedef boost::graph_traits<vtkGraph*>::out_edge_iterator OutEdgeIter;
1018  std::pair<OutEdgeIter, OutEdgeIter> out = out_edges(u, g);
1019  return std::make_pair(Iter(out.first, &g), Iter(out.second, &g));
1020 }
1021 
1022 inline boost::graph_traits<vtkGraph*>::vertices_size_type num_vertices(vtkGraph* g)
1023 {
1024  return g->GetNumberOfVertices();
1025 }
1026 
1027 inline boost::graph_traits<vtkGraph*>::edges_size_type num_edges(vtkGraph* g)
1028 {
1029  return g->GetNumberOfEdges();
1030 }
1031 
1032 inline boost::graph_traits<vtkGraph*>::degree_size_type out_degree(
1033  boost::graph_traits<vtkGraph*>::vertex_descriptor u, vtkGraph* g)
1034 {
1035  return g->GetOutDegree(u);
1036 }
1037 
1038 inline boost::graph_traits<vtkDirectedGraph*>::degree_size_type in_degree(
1039  boost::graph_traits<vtkDirectedGraph*>::vertex_descriptor u, vtkDirectedGraph* g)
1040 {
1041  return g->GetInDegree(u);
1042 }
1043 
1044 inline boost::graph_traits<vtkGraph*>::degree_size_type degree(
1045  boost::graph_traits<vtkGraph*>::vertex_descriptor u, vtkGraph* g)
1046 {
1047  return g->GetDegree(u);
1048 }
1049 
1050 inline boost::graph_traits<vtkMutableDirectedGraph*>::vertex_descriptor add_vertex(
1052 {
1053  return g->AddVertex();
1054 }
1055 
1056 inline std::pair<boost::graph_traits<vtkMutableDirectedGraph*>::edge_descriptor, bool> add_edge(
1057  boost::graph_traits<vtkMutableDirectedGraph*>::vertex_descriptor u,
1058  boost::graph_traits<vtkMutableDirectedGraph*>::vertex_descriptor v, vtkMutableDirectedGraph* g)
1059 {
1060  boost::graph_traits<vtkMutableDirectedGraph*>::edge_descriptor e = g->AddEdge(u, v);
1061  return std::make_pair(e, true);
1062 }
1063 
1064 inline boost::graph_traits<vtkMutableUndirectedGraph*>::vertex_descriptor add_vertex(
1066 {
1067  return g->AddVertex();
1068 }
1069 
1070 inline std::pair<boost::graph_traits<vtkMutableUndirectedGraph*>::edge_descriptor, bool> add_edge(
1071  boost::graph_traits<vtkMutableUndirectedGraph*>::vertex_descriptor u,
1072  boost::graph_traits<vtkMutableUndirectedGraph*>::vertex_descriptor v,
1074 {
1075  boost::graph_traits<vtkMutableUndirectedGraph*>::edge_descriptor e = g->AddEdge(u, v);
1076  return std::make_pair(e, true);
1077 }
1078 
1079 namespace boost
1080 {
1081 //===========================================================================
1082 // An edge map for vtkGraph.
1083 // This is a common input needed for algorithms.
1084 
1086 {
1087 };
1088 
1089 template <>
1091 {
1095  typedef readable_property_map_tag category;
1096 };
1097 
1100 {
1101  return key.Id;
1102 }
1103 
1104 //===========================================================================
1105 // Helper for vtkGraph edge property maps
1106 // Automatically converts boost edge ids to vtkGraph edge ids.
1107 
1108 template <typename PMap>
1110 {
1111 public:
1113  : pmap(m)
1114  {
1115  }
1116  PMap pmap;
1121 
1122  reference operator[](const key_type& key) const { return get(pmap, key.Id); }
1123 };
1124 
1125 template <typename PMap>
1128 {
1129  return get(helper.pmap, key.Id);
1130 }
1131 
1132 template <typename PMap>
1134  const typename property_traits<PMap>::value_type& value)
1135 {
1136  put(helper.pmap, key.Id, value);
1137 }
1138 
1139 //===========================================================================
1140 // Helper for vtkGraph vertex property maps
1141 // Automatically converts boost vertex ids to vtkGraph vertex ids.
1142 
1143 template <typename PMap>
1145 {
1146 public:
1148  : pmap(m)
1149  {
1150  }
1151  PMap pmap;
1156 
1157  reference operator[](const key_type& key) const { return get(pmap, key); }
1158 };
1159 
1160 template <typename PMap>
1163 {
1164  return get(helper.pmap, key);
1165 }
1166 
1167 template <typename PMap>
1169  const typename property_traits<PMap>::value_type& value)
1170 {
1171  put(helper.pmap, key, value);
1172 }
1173 
1174 //===========================================================================
1175 // An index map for vtkGraph
1176 // This is a common input needed for algorithms
1177 
1179 {
1180 };
1181 
1182 template <>
1184 {
1188  typedef readable_property_map_tag category;
1189 };
1190 
1193 {
1194  return key;
1195 }
1196 
1197 //===========================================================================
1198 // Helper for vtkGraph property maps
1199 // Automatically multiplies the property value by some value (default 1)
1200 template <typename PMap>
1202 {
1203 public:
1204  vtkGraphPropertyMapMultiplier(PMap m, float multi = 1)
1205  : pmap(m)
1206  , multiplier(multi)
1207  {
1208  }
1209  PMap pmap;
1210  float multiplier;
1215 };
1216 
1217 template <typename PMap>
1220 {
1221  return multi.multiplier * get(multi.pmap, key);
1222 }
1223 
1224 template <typename PMap>
1226  const typename property_traits<PMap>::key_type& key,
1227  const typename property_traits<PMap>::value_type& value)
1228 {
1229  put(multi.pmap, key, value);
1230 }
1231 
1232 // Allow algorithms to automatically extract vtkGraphIndexMap from a
1233 // VTK graph
1234 template <>
1235 struct property_map<vtkGraph*, vertex_index_t>
1236 {
1239 };
1240 
1241 template <>
1242 struct property_map<vtkDirectedGraph*, vertex_index_t> : property_map<vtkGraph*, vertex_index_t>
1243 {
1244 };
1245 
1246 template <>
1247 struct property_map<vtkUndirectedGraph*, vertex_index_t> : property_map<vtkGraph*, vertex_index_t>
1248 {
1249 };
1250 
1251 inline vtkGraphIndexMap get(vertex_index_t, vtkGraph*)
1252 {
1253  return vtkGraphIndexMap();
1254 }
1255 
1256 template <>
1257 struct property_map<vtkGraph*, edge_index_t>
1258 {
1261 };
1262 
1263 template <>
1264 struct property_map<vtkDirectedGraph*, edge_index_t> : property_map<vtkGraph*, edge_index_t>
1265 {
1266 };
1267 
1268 template <>
1269 struct property_map<vtkUndirectedGraph*, edge_index_t> : property_map<vtkGraph*, edge_index_t>
1270 {
1271 };
1272 
1273 inline vtkGraphIndexMap get(edge_index_t, vtkGraph*)
1274 {
1275  return vtkGraphIndexMap();
1276 }
1277 
1278 // property_map specializations for const-qualified graphs
1279 template <>
1280 struct property_map<vtkDirectedGraph* const, vertex_index_t>
1282 {
1283 };
1284 
1285 template <>
1286 struct property_map<vtkUndirectedGraph* const, vertex_index_t>
1288 {
1289 };
1290 
1291 template <>
1292 struct property_map<vtkDirectedGraph* const, edge_index_t>
1294 {
1295 };
1296 
1297 template <>
1298 struct property_map<vtkUndirectedGraph* const, edge_index_t>
1300 {
1301 };
1302 } // namespace boost
1303 
1304 #if BOOST_VERSION > 104000
1305 #include <boost/property_map/vector_property_map.hpp>
1306 #else
1307 #include <boost/vector_property_map.hpp>
1308 #endif
1309 
1310 #endif // vtkBoostGraphAdapter_h
1311 // VTK-HeaderTest-Exclude: vtkBoostGraphAdapter.h
static vtkDirectedGraph * SafeDownCast(vtkObjectBase *o)
virtual vtkIdType GetNumberOfEdges()
The number of edges in the graph.
helper for the vtkGraph class that allows the graph to be distributed across multiple memory spaces...
property_traits< PMap >::reference reference
property_traits< PMap >::category category
vtk_out_edge_pointer_iterator(vtkGraph *g=0, vtkIdType v=0, bool end=false)
vtkEdgeType AddEdge(vtkIdType u, vtkIdType v)
Adds a directed edge from u to v, where u and v are vertex indices, and returns a vtkEdgeType structu...
virtual vtkInformation * GetInformation()
Set/Get the information object associated with this data object.
std::pair< boost::graph_traits< vtkGraph * >::in_edge_iterator, boost::graph_traits< vtkGraph * >::in_edge_iterator > in_edges(boost::graph_traits< vtkGraph *>::vertex_descriptor u, vtkGraph *g)
boost::graph_traits< vtkGraph * >::vertex_descriptor target(boost::graph_traits< vtkGraph *>::edge_descriptor e, vtkGraph *)
void put(vtkGraphPropertyMapMultiplier< PMap > multi, const typename property_traits< PMap >::key_type &key, const typename property_traits< PMap >::value_type &value)
vtkIdType AddVertex()
Adds a vertex to the graph and returns the index of the new vertex.
Forward declaration required for Boost serialization.
virtual vtkIdType GetNumberOfVertices()
The number of vertices in the graph.
vtk_out_edge_pointer_iterator out_edge_iterator
property_traits< PMap >::reference reference
vtkIdType GetEdgeOwner(vtkIdType e_id) const
Returns owner of edge with ID e_id, by extracting top ceil(log2 P) bits of e_id.
Abstract superclass for all arrays.
vtkGraphPropertyMapMultiplier(PMap m, float multi=1)
property_traits< PMap >::category category
vtkGraph_traversal_category traversal_category
vtk_in_edge_pointer_iterator in_edge_iterator
dynamic, self-adjusting array of float
Definition: vtkFloatArray.h:35
An undirected graph.
std::pair< boost::graph_traits< vtkGraph * >::out_edge_iterator, boost::graph_traits< vtkGraph * >::out_edge_iterator > out_edges(boost::graph_traits< vtkGraph *>::vertex_descriptor u, vtkGraph *g)
dynamic, self-adjusting array of vtkIdType
property_traits< PMap >::key_type key_type
int vtkIdType
Definition: vtkType.h:338
std::pair< boost::graph_traits< vtkGraph * >::vertex_iterator, boost::graph_traits< vtkGraph * >::vertex_iterator > vertices(vtkGraph *g)
property_traits< PMap >::reference reference
boost::graph_traits< vtkGraph * >::edges_size_type num_edges(vtkGraph *g)
boost::graph_traits< vtkGraph * >::vertices_size_type num_vertices(vtkGraph *g)
std::pair< boost::graph_traits< vtkGraph * >::adjacency_iterator, boost::graph_traits< vtkGraph * >::adjacency_iterator > adjacent_vertices(boost::graph_traits< vtkGraph *>::vertex_descriptor u, vtkGraph *g)
boost::graph_traits< vtkGraph * >::vertex_descriptor source(boost::graph_traits< vtkGraph *>::edge_descriptor e, vtkGraph *)
A atomic type representing the union of many types.
Definition: vtkVariant.h:65
dynamic, self-adjusting array of double
A directed graph.
Base class for graph data types.
Definition: vtkGraph.h:289
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:39
boost::graph_traits< vtkDirectedGraph * >::degree_size_type in_degree(boost::graph_traits< vtkDirectedGraph *>::vertex_descriptor u, vtkDirectedGraph *g)
static vtkInformationIntegerKey * DATA_PIECE_NUMBER()
adjacency_iterator_generator< vtkGraph *, vertex_descriptor, out_edge_iterator >::type adjacency_iterator
reference operator[](const key_type &key) const
vtkEdgeType AddEdge(vtkIdType u, vtkIdType v)
Adds an undirected edge from u to v, where u and v are vertex indices, and returns a vtkEdgeType stru...
virtual vtkIdType GetDegree(vtkIdType v)
The total of all incoming and outgoing vertices for vertex v.
static vertex_descriptor null_vertex()
allow_parallel_edge_tag edge_parallel_category
property_traits< PMap >::category category
int Get(vtkInformationIntegerKey *key)
Get/Set an integer-valued entry.
boost::graph_traits< vtkGraph * >::degree_size_type out_degree(boost::graph_traits< vtkGraph *>::vertex_descriptor u, vtkGraph *g)
abstract superclass for arrays of numeric data
Definition: vtkDataArray.h:49
void put(vtkDataArray *arr, vtkIdType key, const double &value)
reference operator[](const key_type &key) const
An editable directed graph.
bool has_no_edges(vtkGraph *g)
boost::graph_traits< vtkMutableDirectedGraph * >::vertex_descriptor add_vertex(vtkMutableDirectedGraph *g)
vtkIdType Id
Definition: vtkGraph.h:251
virtual void InsertVariantValue(vtkIdType valueIdx, vtkVariant value)=0
Insert a value into the array from a variant.
void SetTuple1(vtkIdType tupleIdx, double value)
These methods are included as convenience for the wrappers.
An editable undirected graph.
virtual vtkIdType GetInDegree(vtkIdType v)
The number of incoming edges to vertex v.
vtkIdType Target
Definition: vtkGraph.h:262
property_traits< PMap >::value_type value_type
static vtkMutableDirectedGraph * SafeDownCast(vtkObjectBase *o)
vtkDistributedGraphHelper * GetDistributedGraphHelper()
Retrieves the distributed graph helper for this graph.
vtkIdType GetVertexOwner(vtkIdType v) const
Returns owner of vertex v, by extracting top ceil(log2 P) bits of v.
vtkIdType Source
Definition: vtkGraph.h:273
vtk_in_edge_pointer_iterator(vtkGraph *g=0, vtkIdType v=0, bool end=false)
vtk_edge_iterator(vtkGraph *g=0, vtkIdType v=0)
property_traits< PMap >::value_type value_type
vtkIdType AddVertex()
Adds a vertex to the graph and returns the index of the new vertex.
A rooted tree data structure.
Definition: vtkTree.h:54
virtual void GetOutEdges(vtkIdType v, vtkOutEdgeIterator *it)
Initializes the out edge iterator to iterate over all outgoing edges of vertex v. ...
property_traits< PMap >::value_type value_type
std::pair< boost::graph_traits< vtkMutableDirectedGraph * >::edge_descriptor, bool > add_edge(boost::graph_traits< vtkMutableDirectedGraph *>::vertex_descriptor u, boost::graph_traits< vtkMutableDirectedGraph *>::vertex_descriptor v, vtkMutableDirectedGraph *g)
void RemoveEdge(vtkIdType e)
Removes the edge from the graph.
void RemoveEdge(vtkIdType e)
Removes the edge from the graph.
vtkIdType MakeDistributedId(int owner, vtkIdType local)
Builds a distributed ID consisting of the given owner and the local ID.
static vtkMutableUndirectedGraph * SafeDownCast(vtkObjectBase *o)
void remove_edge(graph_traits< vtkGraph *>::edge_descriptor e, vtkGraph *g)
boost::graph_traits< vtkGraph * >::degree_size_type degree(boost::graph_traits< vtkGraph *>::vertex_descriptor u, vtkGraph *g)
std::pair< boost::graph_traits< vtkGraph * >::edge_iterator, boost::graph_traits< vtkGraph * >::edge_iterator > edges(vtkGraph *g)
virtual vtkIdType GetOutDegree(vtkIdType v)
The number of outgoing edges from vertex v.
vtkGraphIndexMap get(edge_index_t, vtkGraph *)
vtkPropertyMapMacro(vtkIntArray, int)