DGtal  1.3.beta
ObjectBoostGraphInterface.h
1 
17 #pragma once
18 
31 #if defined(ObjectBoostGraphInterface_RECURSES)
32 #error Recursive header files inclusion detected in ObjectBoostGraphInterface.h
33 #else // defined(ObjectBoostGraphInterface_RECURSES)
34 
35 #define ObjectBoostGraphInterface_RECURSES
36 
37 #if !defined ObjectBoostGraphInterface_h
38 
39 #define ObjectBoostGraphInterface_h
40 
42 // Inclusions
43 #include <iostream>
44 #include <vector>
45 #include <boost/iterator/iterator_facade.hpp>
46 #include <boost/graph/graph_traits.hpp>
47 #include <boost/graph/properties.hpp>
48 #include <boost/property_map/property_map.hpp>
49 #include "DGtal/base/Common.h"
50 #include "DGtal/base/CountedPtr.h"
51 #include "DGtal/topology/Object.h"
53 
54 
55 // The interface to the Boost Graph should be defined in namespace boost.
56 namespace boost
57 {
58 
85  template < class TDigitalTopology, class TDigitalSet >
86  struct graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >
87  {
91  typedef undirected_tag directed_category;
95  typedef disallow_parallel_edge_tag edge_parallel_category;
96 
100  typedef typename Adapted::Size edges_size_type;
102  typedef typename Adapted::Size degree_size_type;
103 
105  typedef typename Adapted::Vertex Vertex;
109  typedef typename Adapted::Edge Edge;
115 
117  typedef std::vector< vertex_descriptor > AdjacentVertexContainer;
120 
121 
125  static
126  inline
128  {
129  return vertex_descriptor();
130  }
131 
165  class adjacency_iterator
166  : public iterator_facade< adjacency_iterator,
167  Vertex,
168  bidirectional_traversal_tag,
169  const Vertex & >
170  {
171  public:
173  inline
175  : myIterator(), myVertices( 0 ) {}
176 
186  inline
187  adjacency_iterator( typename AdjacentVertexContainer::const_iterator it,
189  : myIterator( it ), myVertices( vertices ) {}
190 
191  private:
196  inline
197  const Vertex & dereference() const
198  {
199  ASSERT( myIterator != myVertices->end() );
200  return *myIterator;
201  }
202 
211  inline
212  bool equal(const adjacency_iterator& other) const
213  {
214  bool thisAtEnd = ( myIterator == myVertices->end() );
215  bool otherAtEnd = ( other.myIterator == other.myVertices->end() );
216  if ( thisAtEnd || otherAtEnd ) return thisAtEnd && otherAtEnd;
217  else return *myIterator == *other.myIterator;
218  }
219 
224  inline
225  void increment() { ++myIterator; }
226 
231  inline
232  void decrement() { --myIterator; }
233 
234  // ///////////// Data Members ////////////////
235 
237  typename AdjacentVertexContainer::const_iterator myIterator;
244 
246  friend class iterator_core_access;
247  }; // end class adjacency_iterator
248 
282  class out_edge_iterator
283  : public iterator_facade< out_edge_iterator,
284  Edge,
285  bidirectional_traversal_tag,
286  const Edge & >
287  {
288  public:
290  inline
292  : myIterator(), myOutEdges( 0 ) {}
302  inline
303  out_edge_iterator( typename OutEdgeContainer::const_iterator it,
305  : myIterator( it ), myOutEdges( out_edges ) {}
306  private:
311  inline
312  const Edge & dereference() const
313  {
314  ASSERT( myIterator != myOutEdges->end() );
315  return *myIterator;
316  }
317 
326  inline
327  bool equal(const out_edge_iterator & other) const
328  {
329  bool thisAtEnd = ( myIterator == myOutEdges->end() );
330  bool otherAtEnd = ( other.myIterator == other.myOutEdges->end() );
331  if ( thisAtEnd || otherAtEnd ) return thisAtEnd && otherAtEnd;
332  else return *myIterator == *other.myIterator;
333  }
334 
339  inline
340  void increment() { ++myIterator; }
345  inline
346  void decrement() { --myIterator; }
347 
349  typename OutEdgeContainer::const_iterator myIterator;
355 
357  friend class iterator_core_access;
358  }; // end class out_edge_iterator
359 
364  using in_edge_iterator = out_edge_iterator ;
365 
398  class edge_iterator
399  : public iterator_facade< edge_iterator,
400  Edge,
401  forward_traversal_tag,
402  const Edge & >
403  {
404  public:
406  edge_iterator();
418  edge_iterator( const Adapted & graph,
419  const vertex_iterator & itB, const vertex_iterator & itE );
420 
421  private:
426  const Edge & dereference() const;
435  bool equal(const edge_iterator & other) const;
440  void increment();
441 
442  // /////////// Data Members //////////////
444  const Adapted* myGraph;
446  std::pair< vertex_iterator, vertex_iterator > myVertexRange;
448  std::pair< out_edge_iterator, out_edge_iterator > myOutEdgeRange;
449 
451  friend class iterator_core_access;
452  }; // end class out_edge_iterator
453 
454  }; // end struct graph_traits< >
455 
456 
458  // Functions for the boost graph interface to Object<TDigitalTopology, TDigitalSet>.
459 
465  template < class TDigitalTopology, class TDigitalSet >
466  inline
467  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_descriptor
468  source( typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_descriptor edge,
470  {
471  return obj.tail( edge );
472  }
478  template < class TDigitalTopology, class TDigitalSet >
479  inline
480  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_descriptor
481  target( typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_descriptor edge,
483  {
484  return obj.head( edge );
485  }
486 
492  template < class TDigitalTopology, class TDigitalSet >
493  std::pair<
494  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_iterator,
495  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_iterator
496  >
498 
503  template < class TDigitalTopology, class TDigitalSet >
504  inline
505  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertices_size_type
507  {
508  return obj.size();
509  }
510 
518  template < class TDigitalTopology, class TDigitalSet >
519  inline
520  std::pair<
521  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::adjacency_iterator,
522  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::adjacency_iterator
523  >
524  adjacent_vertices( typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_descriptor u,
526  {
527  typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >
528  ::adjacency_iterator Iterator;
529  typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >
530  ::AdjacentVertexContainer Container;
531  DGtal::CountedPtr<Container> ptrAdjVertices( new Container );
532  std::back_insert_iterator< Container > outIt = std::back_inserter( *ptrAdjVertices );
533  obj.writeNeighbors( outIt, u );
534  return std::make_pair( Iterator( ptrAdjVertices->begin(), ptrAdjVertices ),
535  Iterator( ptrAdjVertices->end(), ptrAdjVertices ) );
536  }
537 
538 
547  template < class TDigitalTopology, class TDigitalSet >
548  inline
549  std::pair<
550  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::out_edge_iterator,
551  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::out_edge_iterator
552  >
553  out_edges( typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_descriptor u,
555  {
556  typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >
557  ::out_edge_iterator Iterator;
558  typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >
559  ::OutEdgeContainer Container;
560  DGtal::CountedPtr<Container> ptrEdges( new Container( obj.outEdges( u ) ) );
561  return std::make_pair( Iterator( ptrEdges->begin(), ptrEdges ),
562  Iterator( ptrEdges->end(), ptrEdges ) );
563  }
564 
565 
572  template < class TDigitalTopology, class TDigitalSet >
573  inline
574  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::degree_size_type
575  out_degree( typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_descriptor u,
577  {
578  return obj.degree( u );
579  }
580 
587  template < class TDigitalTopology, class TDigitalSet >
588  inline
589  std::pair<
590  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_iterator,
591  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_iterator
592  >
594  {
595  typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_iterator
596  edge_iterator;
597  return std::make_pair( edge_iterator( obj, obj.begin(), obj.end() ),
598  edge_iterator( obj, obj.end(), obj.end() ) );
599  }
600 
605  template < class TDigitalTopology, class TDigitalSet >
606  inline
607  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edges_size_type
609  {
610  typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_iterator
611  edge_iterator;
612  typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edges_size_type
613  edges_size_type;
614  edges_size_type nbEdges = 0;
615  for ( std::pair< edge_iterator, edge_iterator > ve = boost::edges( obj );
616  ve.first != ve.second; ++ve.first )
617  ++nbEdges;
618  return nbEdges;
619  }
620 
621 } // namespace Boost
622 
623 
625 // Includes inline functions.
626 #include "DGtal/graph/ObjectBoostGraphInterface.ih"
627 
628 // //
630 
631 #endif // !defined ObjectBoostGraphInterface_h
632 
633 #undef ObjectBoostGraphInterface_RECURSES
634 #endif // else defined(ObjectBoostGraphInterface_RECURSES)
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_parallel_category
disallow_parallel_edge_tag edge_parallel_category
the graph does not allow parallel edges.
Definition: ObjectBoostGraphInterface.h:95
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_iterator::myOutEdgeRange
std::pair< out_edge_iterator, out_edge_iterator > myOutEdgeRange
Local pair of out_edge_iterator. Created within this iterator.
Definition: ObjectBoostGraphInterface.h:448
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::out_edge_iterator::decrement
void decrement()
Definition: ObjectBoostGraphInterface.h:346
boost::Container
Go to http://www.sgi.com/tech/stl/Container.html.
Definition: Boost.dox:104
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::null_vertex
static vertex_descriptor null_vertex()
Definition: ObjectBoostGraphInterface.h:127
boost::out_edges
std::pair< typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::out_edge_iterator, typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::out_edge_iterator > out_edges(typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor u, const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
Definition: DigitalSurfaceBoostGraphInterface.h:463
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::out_edge_iterator::myOutEdges
DGtal::CountedPtr< OutEdgeContainer > myOutEdges
Definition: ObjectBoostGraphInterface.h:354
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::out_edge_iterator::out_edge_iterator
out_edge_iterator(typename OutEdgeContainer::const_iterator it, const DGtal::CountedPtr< OutEdgeContainer > &out_edges)
Definition: ObjectBoostGraphInterface.h:303
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::adjacency_iterator::myVertices
DGtal::CountedPtr< AdjacentVertexContainer > myVertices
Definition: ObjectBoostGraphInterface.h:243
DGtal::Object::EdgeRange
std::vector< Edge > EdgeRange
Definition: Object.h:222
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::Adapted
DGtal::Object< TDigitalTopology, TDigitalSet > Adapted
the adapted DGtal graph class.
Definition: ObjectBoostGraphInterface.h:89
boost::edges
std::pair< typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_iterator, typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_iterator > edges(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
Definition: DigitalSurfaceBoostGraphInterface.h:503
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::directed_category
undirected_tag directed_category
the graph is undirected.
Definition: ObjectBoostGraphInterface.h:91
boost::num_edges
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edges_size_type num_edges(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
Definition: DigitalSurfaceBoostGraphInterface.h:518
boost
Definition: Boost.dox:28
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::out_edge_iterator::myIterator
OutEdgeContainer::const_iterator myIterator
The iterator pointing in the container of out edges.
Definition: ObjectBoostGraphInterface.h:349
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::adjacency_iterator::myIterator
AdjacentVertexContainer::const_iterator myIterator
The iterator pointing in the container of adjacent vertices.
Definition: ObjectBoostGraphInterface.h:237
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::in_edge_iterator
out_edge_iterator in_edge_iterator
Definition: ObjectBoostGraphInterface.h:364
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_iterator
Adapted::ConstIterator vertex_iterator
Definition: ObjectBoostGraphInterface.h:114
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::adjacency_iterator::equal
bool equal(const adjacency_iterator &other) const
Definition: ObjectBoostGraphInterface.h:212
boost::vertices
std::pair< typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_iterator, typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_iterator > vertices(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertices_size_type
Adapted::Size vertices_size_type
the type for counting vertices
Definition: ObjectBoostGraphInterface.h:98
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_iterator::myVertexRange
std::pair< vertex_iterator, vertex_iterator > myVertexRange
Vertex Range to iterator from. Set at constructor.
Definition: ObjectBoostGraphInterface.h:446
DGtal::Object::ConstIterator
DigitalSet::ConstIterator ConstIterator
Definition: Object.h:162
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::adjacency_iterator::increment
void increment()
Definition: ObjectBoostGraphInterface.h:225
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_iterator::myGraph
const Adapted * myGraph
Graph to iterate from.
Definition: ObjectBoostGraphInterface.h:444
boost::adjacent_vertices
std::pair< typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::adjacency_iterator, typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::adjacency_iterator > adjacent_vertices(typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor u, const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
Definition: DigitalSurfaceBoostGraphInterface.h:434
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::traversal_category
Object_graph_traversal_category traversal_category
the graph satisfies AdjacencyListGraph and VertexListGraph concepts.
Definition: ObjectBoostGraphInterface.h:93
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::adjacency_iterator::adjacency_iterator
adjacency_iterator()
Default, invalid, constructor.
Definition: ObjectBoostGraphInterface.h:174
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::out_edge_iterator::increment
void increment()
Definition: ObjectBoostGraphInterface.h:340
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::Vertex
Adapted::Vertex Vertex
Vertex type.
Definition: ObjectBoostGraphInterface.h:105
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::adjacency_iterator::adjacency_iterator
adjacency_iterator(typename AdjacentVertexContainer::const_iterator it, const DGtal::CountedPtr< AdjacentVertexContainer > &vertices)
Definition: ObjectBoostGraphInterface.h:187
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::adjacency_iterator::decrement
void decrement()
Definition: ObjectBoostGraphInterface.h:232
DGtal::Object::Edge
Definition: Object.h:165
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edges_size_type
Adapted::Size edges_size_type
the type for counting edges
Definition: ObjectBoostGraphInterface.h:100
DGtal::CountedPtr< AdjacentVertexContainer >
boost::Object_graph_traversal_category
Definition: Object.h:71
DGtal::Object::Size
DigitalSet::Size Size
Definition: Object.h:140
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::out_edge_iterator::out_edge_iterator
out_edge_iterator()
Default, invalid, constructor.
Definition: ObjectBoostGraphInterface.h:291
boost::source
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor source(typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_descriptor edge, const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
Definition: DigitalSurfaceBoostGraphInterface.h:378
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_descriptor
Vertex vertex_descriptor
Vertex type.
Definition: ObjectBoostGraphInterface.h:107
boost::out_degree
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::degree_size_type out_degree(typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor u, const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
Definition: DigitalSurfaceBoostGraphInterface.h:485
DGtal::PointVector< dim, Integer >
boost::target
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor target(typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_descriptor edge, const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
Definition: DigitalSurfaceBoostGraphInterface.h:391
boost::num_vertices
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertices_size_type num_vertices(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
Definition: DigitalSurfaceBoostGraphInterface.h:416
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::degree_size_type
Adapted::Size degree_size_type
the type for counting out or in edges
Definition: ObjectBoostGraphInterface.h:102
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_descriptor
Edge edge_descriptor
(oriented) edge type
Definition: ObjectBoostGraphInterface.h:111
DGtal::Object
Aim: An object (or digital object) represents a set in some digital space associated with a digital t...
Definition: Object.h:119
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::OutEdgeContainer
Adapted::EdgeRange OutEdgeContainer
This is the intermediate data structure that is used for storing out edges.
Definition: ObjectBoostGraphInterface.h:119
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::out_edge_iterator::equal
bool equal(const out_edge_iterator &other) const
Definition: ObjectBoostGraphInterface.h:327
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::AdjacentVertexContainer
std::vector< vertex_descriptor > AdjacentVertexContainer
This is the intermediate data structure that is used for visiting adjacent vertices.
Definition: ObjectBoostGraphInterface.h:117
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::out_edge_iterator::dereference
const Edge & dereference() const
Definition: ObjectBoostGraphInterface.h:312
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::Edge
Adapted::Edge Edge
(oriented) edge type
Definition: ObjectBoostGraphInterface.h:109
boost::graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::adjacency_iterator::dereference
const Vertex & dereference() const
Definition: ObjectBoostGraphInterface.h:197