ObjectBoostGraphInterface.h

 
#pragma once
 
#if defined(ObjectBoostGraphInterface_RECURSES)
#error Recursive header files inclusion detected in ObjectBoostGraphInterface.h
#else // defined(ObjectBoostGraphInterface_RECURSES)
#define ObjectBoostGraphInterface_RECURSES
 
#if !defined ObjectBoostGraphInterface_h
#define ObjectBoostGraphInterface_h
 
// Inclusions
#include <iostream>
#include <vector>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/property_map/property_map.hpp>
#include "DGtal/base/Common.h"
#include "DGtal/base/CountedPtr.h"
#include "DGtal/topology/Object.h"
 
 
// The interface to the Boost Graph should be defined in namespace boost.
namespace boost
{
 
  template < class TDigitalTopology, class TDigitalSet >
  struct graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >
  {
    typedef DGtal::Object< TDigitalTopology, TDigitalSet > Adapted;
    typedef undirected_tag directed_category;
    typedef Object_graph_traversal_category traversal_category;
    typedef disallow_parallel_edge_tag edge_parallel_category;
 
    typedef typename Adapted::Size vertices_size_type;
    typedef typename Adapted::Size edges_size_type;
    typedef typename Adapted::Size degree_size_type;
 
    typedef typename Adapted::Vertex Vertex;
    typedef Vertex vertex_descriptor;
    typedef typename Adapted::Edge Edge;
    typedef Edge edge_descriptor;
    typedef typename Adapted::ConstIterator vertex_iterator;
 
    typedef std::vector< vertex_descriptor > AdjacentVertexContainer;
    typedef typename Adapted::EdgeRange OutEdgeContainer;
 
 
    static
    inline
    vertex_descriptor null_vertex()
    {
      return vertex_descriptor();
    }
 
    class adjacency_iterator
      : public iterator_facade< adjacency_iterator,
                                Vertex,
                                bidirectional_traversal_tag,
                                const Vertex & >
    {
    public:
      inline
      adjacency_iterator()
        : myIterator(), myVertices( 0 ) {}
 
      inline
      adjacency_iterator( typename AdjacentVertexContainer::const_iterator it,
                          const DGtal::CountedPtr< AdjacentVertexContainer > & vertices )
        : myIterator( it ), myVertices( vertices ) {}
 
    private:
      inline
      const Vertex & dereference() const
      {
        ASSERT( myIterator != myVertices->end() );
        return *myIterator;
      }
 
      inline
      bool equal(const adjacency_iterator& other) const
      {
        bool thisAtEnd = ( myIterator == myVertices->end() );
        bool otherAtEnd = ( other.myIterator == other.myVertices->end() );
        if ( thisAtEnd || otherAtEnd ) return thisAtEnd && otherAtEnd;
        else return *myIterator == *other.myIterator;
      }
 
      inline
      void increment() { ++myIterator; }
 
      inline
      void decrement() { --myIterator; }
 
      // ///////////// Data Members ////////////////
 
      typename AdjacentVertexContainer::const_iterator myIterator;
      DGtal::CountedPtr< AdjacentVertexContainer > myVertices;
 
      friend class iterator_core_access;
    }; // end class adjacency_iterator
 
    class out_edge_iterator
      : public iterator_facade< out_edge_iterator,
                                Edge,
                                bidirectional_traversal_tag,
                                const Edge & >
    {
    public:
      inline
      out_edge_iterator()
        : myIterator(), myOutEdges( 0 ) {}
      inline
      out_edge_iterator( typename OutEdgeContainer::const_iterator it,
                         const DGtal::CountedPtr< OutEdgeContainer > & out_edges )
        : myIterator( it ), myOutEdges( out_edges ) {}
    private:
      inline
      const Edge & dereference() const
      {
        ASSERT( myIterator != myOutEdges->end() );
        return *myIterator;
      }
 
      inline
      bool equal(const out_edge_iterator & other) const
      {
        bool thisAtEnd = ( myIterator == myOutEdges->end() );
        bool otherAtEnd = ( other.myIterator == other.myOutEdges->end() );
        if ( thisAtEnd || otherAtEnd ) return thisAtEnd && otherAtEnd;
        else return *myIterator == *other.myIterator;
      }
 
      inline
      void increment() { ++myIterator; }
      inline
      void decrement() { --myIterator; }
 
      typename OutEdgeContainer::const_iterator myIterator;
      DGtal::CountedPtr< OutEdgeContainer > myOutEdges;
 
      friend class iterator_core_access;
    }; // end class out_edge_iterator
 
    using in_edge_iterator = out_edge_iterator ;
 
    class edge_iterator
      : public iterator_facade< edge_iterator,
                                Edge,
                                forward_traversal_tag,
                                const Edge & >
    {
    public:
      edge_iterator();
      edge_iterator( const Adapted & graph,
                     const vertex_iterator & itB, const vertex_iterator & itE );
 
    private:
      const Edge & dereference() const;
      bool equal(const edge_iterator & other) const;
      void increment();
 
      // /////////// Data Members //////////////
      const Adapted* myGraph;
      std::pair< vertex_iterator, vertex_iterator > myVertexRange;
      std::pair< out_edge_iterator, out_edge_iterator > myOutEdgeRange;
 
      friend class iterator_core_access;
    }; // end class out_edge_iterator
 
  }; // end struct graph_traits< >
 
 
  // Functions for the boost graph interface to Object<TDigitalTopology, TDigitalSet>.
 
  template < class TDigitalTopology, class TDigitalSet >
  inline
  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_descriptor
  source( typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_descriptor edge,
          const DGtal::Object< TDigitalTopology, TDigitalSet > & obj )
  {
    return obj.tail( edge );
  }
  template < class TDigitalTopology, class TDigitalSet >
  inline
  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_descriptor
  target( typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_descriptor edge,
          const DGtal::Object< TDigitalTopology, TDigitalSet > & obj )
  {
    return obj.head( edge );
  }
 
  template < class TDigitalTopology, class TDigitalSet >
  std::pair<
    typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_iterator,
    typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_iterator
    >
  vertices( const DGtal::Object< TDigitalTopology, TDigitalSet > & obj );
 
  template < class TDigitalTopology, class TDigitalSet >
  inline
  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertices_size_type
  num_vertices( const DGtal::Object< TDigitalTopology, TDigitalSet > & obj )
  {
    return obj.size();
  }
 
  template < class TDigitalTopology, class TDigitalSet >
  inline
  std::pair<
    typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::adjacency_iterator,
    typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::adjacency_iterator
    >
  adjacent_vertices( typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_descriptor u,
                     const DGtal::Object< TDigitalTopology, TDigitalSet > & obj )
  {
    typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >
      ::adjacency_iterator Iterator;
    typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >
      ::AdjacentVertexContainer Container;
    DGtal::CountedPtr<Container> ptrAdjVertices( new Container );
    std::back_insert_iterator< Container > outIt = std::back_inserter( *ptrAdjVertices );
    obj.writeNeighbors( outIt, u );
    return std::make_pair( Iterator( ptrAdjVertices->begin(), ptrAdjVertices ),
                           Iterator( ptrAdjVertices->end(), ptrAdjVertices ) );
  }
 
 
  template < class TDigitalTopology, class TDigitalSet >
  inline
  std::pair<
    typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::out_edge_iterator,
    typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::out_edge_iterator
    >
  out_edges( typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_descriptor u,
             const DGtal::Object< TDigitalTopology, TDigitalSet > & obj )
  {
    typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >
      ::out_edge_iterator Iterator;
    typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >
      ::OutEdgeContainer Container;
    DGtal::CountedPtr<Container> ptrEdges( new Container( obj.outEdges( u ) ) );
    return std::make_pair( Iterator( ptrEdges->begin(), ptrEdges ),
                           Iterator( ptrEdges->end(), ptrEdges ) );
  }
 
 
  template < class TDigitalTopology, class TDigitalSet >
  inline
  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::degree_size_type
  out_degree( typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_descriptor u,
              const DGtal::Object< TDigitalTopology, TDigitalSet > & obj )
  {
    return obj.degree( u );
  }
 
  template < class TDigitalTopology, class TDigitalSet >
  inline
  std::pair<
    typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_iterator,
    typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_iterator
    >
  edges( const DGtal::Object< TDigitalTopology, TDigitalSet > & obj )
  {
    typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_iterator
      edge_iterator;
    return std::make_pair( edge_iterator( obj, obj.begin(), obj.end() ),
                           edge_iterator( obj, obj.end(), obj.end() ) );
  }
 
  template < class TDigitalTopology, class TDigitalSet >
  inline
  typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edges_size_type
  num_edges( const DGtal::Object< TDigitalTopology, TDigitalSet > & obj )
  {
    typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_iterator
      edge_iterator;
    typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edges_size_type
      edges_size_type;
    edges_size_type nbEdges = 0;
    for ( std::pair< edge_iterator, edge_iterator > ve = boost::edges( obj );
          ve.first != ve.second; ++ve.first )
      ++nbEdges;
    return nbEdges;
  }
 
} // namespace Boost
 
 
// Includes inline functions.
#include "DGtal/graph/ObjectBoostGraphInterface.ih"
 
//                                                                           //
 
#endif // !defined ObjectBoostGraphInterface_h
 
#undef ObjectBoostGraphInterface_RECURSES
#endif // else defined(ObjectBoostGraphInterface_RECURSES)