DGtal  0.9.2
DigitalSurfaceBoostGraphInterface.h
1 
17 #pragma once
18 
31 #if defined(DigitalSurfaceBoostGraphInterface_RECURSES)
32 #error Recursive header files inclusion detected in DigitalSurfaceBoostGraphInterface.h
33 #else // defined(DigitalSurfaceBoostGraphInterface_RECURSES)
34 
35 #define DigitalSurfaceBoostGraphInterface_RECURSES
36 
37 #if !defined DigitalSurfaceBoostGraphInterface_h
38 
39 #define DigitalSurfaceBoostGraphInterface_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/ConstAlias.h"
51 #include "DGtal/base/CountedPtr.h"
52 #include "DGtal/topology/DigitalSurface.h"
54 
55 
56 // The interface to the Boost Graph should be defined in namespace boost.
57 namespace boost
58 {
59 
92  template < class TDigitalSurfaceContainer >
93  struct graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >
94  {
98  typedef undirected_tag directed_category;
102  typedef disallow_parallel_edge_tag edge_parallel_category;
103 
107  typedef typename Adapted::Size edges_size_type;
109  typedef typename Adapted::Size degree_size_type;
110 
112  typedef typename Adapted::Vertex Vertex;
114  typedef Vertex vertex_descriptor;
116  typedef typename Adapted::Arc Arc;
118  typedef Arc edge_descriptor;
122 
124  typedef std::vector< vertex_descriptor > AdjacentVertexContainer;
127 
128 
132  static
133  inline
134  vertex_descriptor null_vertex()
135  {
136  return vertex_descriptor( 0 );
137  }
138 
172  class adjacency_iterator
173  : public iterator_facade< adjacency_iterator,
174  Vertex,
175  bidirectional_traversal_tag,
176  const Vertex & >
177  {
178  public:
179  inline
181  : myIterator(), myVertices( 0 ) {}
182  inline
183  adjacency_iterator( typename AdjacentVertexContainer::const_iterator it,
185  : myIterator( it ), myVertices( vertices ) {}
186  private:
187  inline
188  const Vertex & dereference() const
189  {
190  ASSERT( myIterator != myVertices->end() );
191  return *myIterator;
192  }
193 
194  inline
195  bool equal(const adjacency_iterator& other) const
196  {
197  bool thisAtEnd = ( myIterator == myVertices->end() );
198  bool otherAtEnd = ( other.myIterator == other.myVertices->end() );
199  if ( thisAtEnd || otherAtEnd ) return thisAtEnd && otherAtEnd;
200  else return *myIterator == *other.myIterator;
201  }
202 
203  inline
204  void increment() { ++myIterator; }
205  inline
206  void decrement() { --myIterator; }
207 
209  typename AdjacentVertexContainer::const_iterator myIterator;
214 
215  friend class iterator_core_access;
216  }; // end class adjacency_iterator
217 
251  class out_edge_iterator
252  : public iterator_facade< out_edge_iterator,
253  Arc,
254  bidirectional_traversal_tag,
255  const Arc & >
256  {
257  public:
258  inline
260  : myIterator(), myOutEdges( 0 ) {}
261  inline
262  out_edge_iterator( typename OutEdgeContainer::const_iterator it,
264  : myIterator( it ), myOutEdges( out_edges ) {}
265  private:
266  inline
267  const Arc & dereference() const
268  {
269  ASSERT( myIterator != myOutEdges->end() );
270  return *myIterator;
271  }
272 
273  inline
274  bool equal(const out_edge_iterator & other) const
275  {
276  bool thisAtEnd = ( myIterator == myOutEdges->end() );
277  bool otherAtEnd = ( other.myIterator == other.myOutEdges->end() );
278  if ( thisAtEnd || otherAtEnd ) return thisAtEnd && otherAtEnd;
279  else return *myIterator == *other.myIterator;
280  }
281 
282  inline
283  void increment() { ++myIterator; }
284  inline
285  void decrement() { --myIterator; }
286 
288  typename OutEdgeContainer::const_iterator myIterator;
293 
294  friend class iterator_core_access;
295  }; // end class out_edge_iterator
296 
329  class edge_iterator
330  : public iterator_facade< edge_iterator,
331  Arc,
332  forward_traversal_tag,
333  const Arc & >
334  {
335  public:
336  edge_iterator();
337  edge_iterator( ConstAlias<Adapted> graph,
338  const vertex_iterator & itB, const vertex_iterator & itE );
339 
340  private:
341  const Arc & dereference() const;
342  bool equal(const edge_iterator & other) const;
343  void increment();
344 
345  const Adapted* myGraph;
346  std::pair< vertex_iterator, vertex_iterator > myVertexRange;
347  std::pair< out_edge_iterator, out_edge_iterator > myOutEdgeRange;
348 
349  friend class iterator_core_access;
350  }; // end class out_edge_iterator
351 
352  }; // end struct graph_traits< >
353 
360  // template < class TDigitalSurfaceContainer, typename TPropertyTag >
361  // struct property_map< DGtal::DigitalSurface< TDigitalSurfaceContainer >, TPropertyTag >
362  // {
363 
364  // };
365 
366 
368  // Functions for the boost graph interface to DigitalSurface<TDigitalSurfaceContainer>.
369 
375  template < class TDigitalSurfaceContainer >
376  inline
377  typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor
378  source( typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_descriptor edge,
380  {
381  return digSurf.tail( edge );
382  }
388  template < class TDigitalSurfaceContainer >
389  inline
390  typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor
391  target( typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_descriptor edge,
393  {
394  return digSurf.head( edge );
395  }
396 
402  template < class TDigitalSurfaceContainer >
403  std::pair<
404  typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_iterator,
405  typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_iterator
406  >
408 
413  template < class TDigitalSurfaceContainer >
414  inline
415  typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertices_size_type
417  {
418  return digSurf.size();
419  }
420 
428  template < class TDigitalSurfaceContainer >
429  inline
430  std::pair<
431  typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::adjacency_iterator,
432  typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::adjacency_iterator
433  >
434  adjacent_vertices( typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor u,
436  {
437  typedef typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >
438  ::adjacency_iterator Iterator;
439  typedef typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >
440  ::AdjacentVertexContainer Container;
441  DGtal::CountedPtr<Container> ptrAdjVertices( new Container );
442  std::back_insert_iterator< Container > outIt = std::back_inserter( *ptrAdjVertices );
443  digSurf.writeNeighbors( outIt, u );
444  return std::make_pair( Iterator( ptrAdjVertices->begin(), ptrAdjVertices ),
445  Iterator( ptrAdjVertices->end(), ptrAdjVertices ) );
446  }
447 
448 
457  template < class TDigitalSurfaceContainer >
458  inline
459  std::pair<
460  typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::out_edge_iterator,
461  typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::out_edge_iterator
462  >
463  out_edges( typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor u,
465  {
466  typedef typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >
467  ::out_edge_iterator Iterator;
468  typedef typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >
469  ::OutEdgeContainer Container;
470  DGtal::CountedPtr<Container> ptrOutEdges( new Container( digSurf.outArcs( u ) ) );
471  return std::make_pair( Iterator( ptrOutEdges->begin(), ptrOutEdges ),
472  Iterator( ptrOutEdges->end(), ptrOutEdges ) );
473  }
474 
482  template < class TDigitalSurfaceContainer >
483  inline
484  typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::degree_size_type
485  out_degree( typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor u,
487  {
488  return digSurf.degree( u );
489  }
490 
497  template < class TDigitalSurfaceContainer >
498  inline
499  std::pair<
500  typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_iterator,
501  typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_iterator
502  >
504  {
505  typedef typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_iterator
506  edge_iterator;
507  return std::make_pair( edge_iterator( digSurf, digSurf.begin(), digSurf.end() ),
508  edge_iterator( digSurf, digSurf.end(), digSurf.end() ) );
509  }
510 
515  template < class TDigitalSurfaceContainer >
516  inline
517  typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edges_size_type
519  {
520  typedef typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_iterator
521  edge_iterator;
522  typedef typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edges_size_type
523  edges_size_type;
524  edges_size_type nbEdges = 0;
525  for ( std::pair< edge_iterator, edge_iterator > ve = boost::edges( digSurf );
526  ve.first != ve.second; ++ve.first )
527  ++nbEdges;
528  return nbEdges;
529  }
530 
531 
532 } // namespace Boost
533 
534 
536 // Includes inline functions.
537 #include "DGtal/graph/DigitalSurfaceBoostGraphInterface.ih"
538 
539 // //
541 
542 #endif // !defined DigitalSurfaceBoostGraphInterface_h
543 
544 #undef DigitalSurfaceBoostGraphInterface_RECURSES
545 #endif // else defined(DigitalSurfaceBoostGraphInterface_RECURSES)
DigitalSurface_graph_traversal_category traversal_category
the graph satisfies AdjacencyListGraph and VertexListGraph concepts.
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor target(typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_descriptor edge, const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
std::vector< Arc > ArcRange
The range of arcs is defined as a vector.
ArcRange outArcs(const Vertex &v) const
Definition: Boost.dox:28
DigitalSurfaceContainer::SurfelConstIterator ConstIterator
OutEdgeContainer::const_iterator myIterator
The iterator pointing in the container of out 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)
Size size() const
AdjacentVertexContainer::const_iterator myIterator
The iterator pointing in the container of adjacent vertices.
Vertex tail(const Arc &a) const
Aim: Represents a set of n-1-cells in a nD space, together with adjacency relation between these cell...
void writeNeighbors(OutputIterator &it, const Vertex &v) const
adjacency_iterator(typename AdjacentVertexContainer::const_iterator it, const DGtal::CountedPtr< AdjacentVertexContainer > &vertices)
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertices_size_type num_vertices(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
DGtal::DigitalSurface< TDigitalSurfaceContainer > Adapted
the adapted DGtal graph class.
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)
out_edge_iterator(typename OutEdgeContainer::const_iterator it, const DGtal::CountedPtr< OutEdgeContainer > &out_edges)
Size degree(const Vertex &v) const
Surfel Vertex
Defines the type for a vertex.
DGtal is the top-level namespace which contains all DGtal functions and types.
Adapted::ArcRange OutEdgeContainer
This is the intermediate data structure that is used for storing out edges.
Vertex head(const Arc &a) 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)
std::pair< typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_iterator, typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_iterator > vertices(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
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.
ConstIterator begin() const
ConstIterator end() const
disallow_parallel_edge_tag edge_parallel_category
the graph does not allow parallel edges.
KSpace::Size Size
Defines how to represent a size (unsigned integral type).
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)