DGtal  0.9.2
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;
107  typedef Vertex vertex_descriptor;
109  typedef typename Adapted::Edge Edge;
111  typedef Edge edge_descriptor;
115 
117  typedef std::vector< vertex_descriptor > AdjacentVertexContainer;
120 
121 
125  static
126  inline
127  vertex_descriptor null_vertex()
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)
DigitalSet::Size Size
Definition: Object.h:140
Aim: An object (or digital object) represents a set in some digital space associated with a digital t...
Definition: Object.h:119
Adapted::Size degree_size_type
the type for counting out or in edges
ConstIterator begin() const
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor target(typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_descriptor edge, const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
DGtal::Object< TDigitalTopology, TDigitalSet > Adapted
the adapted DGtal graph class.
OutEdgeContainer::const_iterator myIterator
The iterator pointing in the container of out edges.
Size degree(const Vertex &v) const
EdgeRange outEdges(const Vertex &v) const
Definition: Boost.dox:28
disallow_parallel_edge_tag edge_parallel_category
the graph does not allow parallel 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)
Vertex head(const Edge &e) const
void writeNeighbors(OutputIterator &it, const Vertex &v) const
std::pair< out_edge_iterator, out_edge_iterator > myOutEdgeRange
Local pair of out_edge_iterator. Created within this iterator.
ConstIterator end() const
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertices_size_type num_vertices(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
DigitalSet::Point Vertex
Definition: Object.h:157
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)
adjacency_iterator(typename AdjacentVertexContainer::const_iterator it, const DGtal::CountedPtr< AdjacentVertexContainer > &vertices)
AdjacentVertexContainer::const_iterator myIterator
The iterator pointing in the container of adjacent vertices.
DigitalSet::ConstIterator ConstIterator
Definition: Object.h:162
Object_graph_traversal_category traversal_category
the graph satisfies AdjacencyListGraph and VertexListGraph concepts.
DGtal is the top-level namespace which contains all DGtal functions and types.
Size size() const
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)
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor source(typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_descriptor edge, const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
Vertex tail(const Edge &e) const
std::pair< typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_iterator, typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_iterator > vertices(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
out_edge_iterator(typename OutEdgeContainer::const_iterator it, const DGtal::CountedPtr< OutEdgeContainer > &out_edges)
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::degree_size_type out_degree(typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor u, const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
std::vector< vertex_descriptor > AdjacentVertexContainer
This is the intermediate data structure that is used for visiting adjacent vertices.
std::vector< Edge > EdgeRange
Definition: Object.h:222
Adapted::EdgeRange OutEdgeContainer
This is the intermediate data structure that is used for storing out edges.
std::pair< vertex_iterator, vertex_iterator > myVertexRange
Vertex Range to iterator from. Set at constructor.
Go to http://www.sgi.com/tech/stl/Container.html.
Definition: Boost.dox:104
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edges_size_type num_edges(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)