CGAL users discussion list

[Andreas Fabri <>]

Laurent Le Guillou wrote:
> Hello,
>
> With CGAL, is there a way to enumerate (with an iterator
> or something) the neighboors of a vertex : for instance all the
> first neighboors ("order 1" neighboors), the second neighboors
> (neighboor of a neighboor, "order 2" neighboors), the third
> neighboors ("order 3"), and so on, but without enumerating the same
> vertex twice. I am a physicist, without a very deep knowledge of
> graph-related mathematics; I searched in graph-literature but did
> not found any simple algorithm. I need something quite fast as I
> want to select all the neighboors of a given vertex of "order" less
> than a fixed k, and I need to do this for all vertices, in order
> to compute local physical properties (a "local plane" and other
> mechanical properties).
>
> Thanks a lot if someone could give me a hint on how to do this
> in an efficient way (I may of course walk across the whole
> polyhedron data structure several times, but my polyhedrons
> have tens of thousands points...).
>
> Cheers,
>
> Laurent
>
> -----------------------------------------------------------------------
>   Laurent LE GUILLOU                      Tel +33 1 44 27 39 93
>   
>
>                       Fax +33 1 44 27 46 38
>   
>
>               GSM +33 6 20 05 75 22
>
>   LPNHE - Université Paris 6
>   Bureau 412 - Tour 33 RdC
>   Campus de Jussieu
>   4 place Jussieu
>   75252 Paris Cedex 05


Hello,

One way to do it is with the graph algorithms of the BGL applied to the 
Polyhedron.
Here comes how the code would look like.  Note that it needs the attached 
fixed
versions of the graph_traits for the Polyhedron. They must go in a directory
include/CGAL/boost/graph/
Note that this fixed version is there just to illustrate the case, and needs 
more
testing.  It will fo in the next bug-fix release.


For CGAL and the BGL see http://www.cgal.org/Pkg/BGL

Best regards,

Andreas Fabri



#include <CGAL/Cartesian.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/IO/Polyhedron_iostream.h>
#include <CGAL/Polyhedron_items_with_id_3.h>
#include <CGAL/boost/graph/graph_traits_Polyhedron_3.h>
#include <CGAL/boost/graph/properties_Polyhedron_3.h>

#include <boost/graph/breadth_first_search.hpp>

typedef CGAL::Cartesian<double>                                      Kernel;
typedef Kernel::Point_3                                              Point;
typedef CGAL::Polyhedron_3<Kernel,CGAL::Polyhedron_items_with_id_3>  
Polyhedron;

typedef boost::graph_traits<Polyhedron>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<Polyhedron>::vertex_iterator   vertex_iterator;



int main() {

  int i=0;
  Polyhedron P;
  std::cin >> P;

  // associate indices to the vertices using the "id()" field of the vertex.
  vertex_iterator vb, ve;
  int index = 0;

  // boost::tie assigns the first and second element of the std::pair
  // returned by boost::vertices to the variables vit and ve
  for(boost::tie(vb,ve)=boost::vertices(P); vb!=ve; ++vb ){
    vertex_descriptor  vd = *vb;
    vd->id() = index++;
  }

  // This is the vector where the distance gets written to
  std::vector<int> distance(P.size_of_vertices());


  // Here we start at an arbitrary vertex
  // Any other vertex could be the starting point
  boost::tie(vb,ve)=boost::vertices(P);
  vertex_descriptor  vd = *vb;

  std::cout << "We compute distances to " << vd->point() << std::endl;


  // bfs = breadth first search explores the graph
  // Just as the distance_recorder there is a way to record the predecessor 
of a vertex
  boost::breadth_first_search(P,
                              vd,
                              
visitor(boost::make_bfs_visitor(boost::record_distances(make_iterator_property_map(distance.begin(),
                                                                              
                                   get(boost::vertex_index, P)),
                                                                              
        boost::on_tree_edge()))));



  // Traverse all vertices and show at what distance they are
  for(boost::tie(vb,ve)=boost::vertices(P); vb!=ve; ++vb ){
    vd = *vb;
    std::cout <<  vd->point() << "  is " << distance[vd->id()] << " hops away" 
<< std::endl;
  }

  return 0;
}




// Copyright (c) 2007  GeometryFactory (France).  All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public License as
// published by the Free Software Foundation; version 2.1 of the License.
// See the file LICENSE.LGPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the 
software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: 
svn+ssh:///svn/cgal/trunk/BGL/include/CGAL/boost/graph/graph_traits_Polyhedron_3.h
 $
// $Id: graph_traits_Polyhedron_3.h 37284 2007-03-19 19:36:49Z afabri $
// 
//
// Author(s)     : Andreas Fabri, Fernando Cacciola

#ifndef CGAL_BOOST_GRAPH_GRAPH_TRAITS_POLYHEDRON_3_H
#define CGAL_BOOST_GRAPH_GRAPH_TRAITS_POLYHEDRON_3_H

#include <CGAL/boost/graph/graph_traits_HalfedgeDS.h>

#include <CGAL/Polyhedron_3.h>

#ifndef CGAL_CFG_NO_TMPL_IN_TMPL_PARAM
#  define CGAL_HDS_PARAM_ template < class Traits, class Items, class Alloc> 
class HDS
#else
#  define CGAL_HDS_PARAM_ class HDS
#endif


namespace boost
{ 

 
template<class Gt, class I, CGAL_HDS_PARAM_, class A>
typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> >::vertices_size_type
num_vertices(const CGAL::Polyhedron_3<Gt,I,HDS,A>& p)
{
  return p.size_of_vertices();
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> const>::edges_size_type 
num_edges(const CGAL::Polyhedron_3<Gt,I,HDS,A>& p)
{
  return p.size_of_halfedges() ;
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> >::degree_size_type
degree(typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::vertex_descriptor v, const CGAL::Polyhedron_3<Gt,I,HDS,A>&)
{
  return v->vertex_degree() * 2 ;
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> >::degree_size_type
out_degree(typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::vertex_descriptor v, const CGAL::Polyhedron_3<Gt,I,HDS,A>&)
{
  return v->vertex_degree();
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> >::degree_size_type
in_degree(typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::vertex_descriptor v,  const CGAL::Polyhedron_3<Gt,I,HDS,A>&)
{
  return v->vertex_degree();
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
struct graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> >
   : CGAL::HDS_graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> >
{};


template<class Gt, class I, CGAL_HDS_PARAM_, class A>
typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> >::vertex_descriptor
source(typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::edge_descriptor e, const CGAL::Polyhedron_3<Gt,I,HDS,A> & )
{
  return e->opposite()->vertex();
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> >::vertex_descriptor
target(typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::edge_descriptor e, const CGAL::Polyhedron_3<Gt,I,HDS,A> & )
{
  return e->vertex();
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
inline std::pair<typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::vertex_iterator
                ,typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::vertex_iterator 
                >  
vertices( const CGAL::Polyhedron_3<Gt,I,HDS,A>& p)
{
  typedef typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::vertex_iterator Iter;
  CGAL::Polyhedron_3<Gt,I,HDS,A>& ncp = 
const_cast<CGAL::Polyhedron_3<Gt,I,HDS,A>&>(p);
  return std::make_pair( Iter(ncp.vertices_begin()), Iter(ncp.vertices_end()) 
);
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
inline std::pair<typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::edge_iterator
                ,typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::edge_iterator 
                >  
edges( const CGAL::Polyhedron_3<Gt,I,HDS,A>& p)
{
  typedef typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::edge_iterator Iter;
  CGAL::Polyhedron_3<Gt,I,HDS,A>& ncp = 
const_cast<CGAL::Polyhedron_3<Gt,I,HDS,A>&>(p);
  return std::make_pair( Iter(ncp.halfedges_begin()), 
Iter(ncp.halfedges_end()) );
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
inline std::pair<typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::in_edge_iterator
                ,typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::in_edge_iterator
                >  
in_edges( typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::vertex_descriptor u, const CGAL::Polyhedron_3<Gt,I,HDS,A>& g)
{
  typename CGAL::Polyhedron_3<Gt,I,HDS,A>::Halfedge_around_vertex_circulator 
ec = u->vertex_begin();
  typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> >::edges_size_type 
in_deg = in_degree(u,g);
  typedef typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::in_edge_iterator Iter;
  return std::make_pair( Iter(ec), Iter(ec,in_deg) );
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
inline std::pair<typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::out_edge_iterator
                ,typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::out_edge_iterator 
                >  
out_edges( typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::vertex_descriptor u, const CGAL::Polyhedron_3<Gt,I,HDS,A>& g)
{
  typename CGAL::Polyhedron_3<Gt,I,HDS,A>::Halfedge_around_vertex_circulator 
ec = u->vertex_begin();
  typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> >::edges_size_type 
out_deg = out_degree(u,g);
  typedef typename graph_traits< CGAL::Polyhedron_3<Gt,I,HDS,A> 
>::out_edge_iterator Iter;
  return std::make_pair( Iter(ec), Iter(ec,out_deg) );
}
        
} // namespace boost

#undef CGAL_HDS_

#endif // CGAL_BOOST_GRAPH_GRAPH_TRAITS_POLYHEDRON_3_H
// Copyright (c) 2007  GeometryFactory (France).  All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public License as
// published by the Free Software Foundation; version 2.1 of the License.
// See the file LICENSE.LGPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the 
software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: 
svn+ssh:///svn/cgal/trunk/BGL/include/CGAL/boost/graph/properties_Polyhedron_3.h
 $
// $Id: properties_Polyhedron_3.h 40030 2007-08-24 12:57:55Z spion $
// 
//
// Author(s)     : Andreas Fabri, Fernando Cacciola

#ifndef CGAL_BOOST_GRAPH_PROPERTIES_POLYHEDRON_3_H
#define CGAL_BOOST_GRAPH_PROPERTIES_POLYHEDRON_3_H

#include <CGAL/boost/graph/properties.h>
#include <CGAL/boost/graph/graph_traits_Polyhedron_3.h>
#include <CGAL/Unique_hash_map.h>

#ifndef CGAL_CFG_NO_TMPL_IN_TMPL_PARAM
#  define CGAL_HDS_PARAM_ template < class Traits, class Items, class Alloc> 
class HDS
#else
#  define CGAL_HDS_PARAM_ class HDS
#endif

CGAL_BEGIN_NAMESPACE

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
class Polyhedron_edge_weight_map : public boost::put_get_helper<double, 
Polyhedron_edge_weight_map<Gt, I, HDS, A> >
{
private:

  typedef CGAL::Polyhedron_3<Gt,I,HDS,A> Polyhedron ;
  
public:

  typedef boost::readable_property_map_tag                                
category;
  typedef double                                                          
value_type;
  typedef double                                                          
reference;
  typedef typename boost::graph_traits<Polyhedron>::edge_descriptor key_type;

  Polyhedron_edge_weight_map( Polyhedron const& ) {}

  reference operator[](key_type const& e) const
  {
    return CGAL::squared_distance(e->vertex()->point(), 
e->opposite()->vertex()->point());
  }
};

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
class Polyhedron_edge_is_border_map : public boost::put_get_helper<bool, 
Polyhedron_edge_is_border_map<Gt, I, HDS, A> >
{
private:

  typedef CGAL::Polyhedron_3<Gt,I,HDS,A> Polyhedron ;
  
public:

  typedef boost::readable_property_map_tag                                
category;
  typedef bool                                                            
value_type;
  typedef bool                                                            
reference;
  typedef typename boost::graph_traits<Polyhedron>::edge_descriptor key_type;

  Polyhedron_edge_is_border_map( Polyhedron const& ) {}

  reference operator[](key_type const& e) const { return e->is_border(); }
};

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
class Polyhedron_edge_index_map_stored : public 
boost::put_get_helper<std::size_t, Polyhedron_edge_index_map_stored<Gt, I, 
HDS, A> >
{
private:

  typedef CGAL::Polyhedron_3<Gt,I,HDS,A> Polyhedron ;
  
public:

  typedef boost::readable_property_map_tag                                
category;
  typedef std::size_t                                                     
value_type;
  typedef std::size_t                                                     
reference;
  typedef typename boost::graph_traits<Polyhedron>::edge_descriptor key_type;

  Polyhedron_edge_index_map_stored( Polyhedron const& ) {}

  reference operator[](key_type const& e) const { return e->id(); }
};

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
class Polyhedron_edge_index_map_external : public 
boost::put_get_helper<std::size_t, Polyhedron_edge_index_map_external<Gt, I, 
HDS, A> >
{
private:

  typedef CGAL::Polyhedron_3<Gt,I,HDS,A> Polyhedron ;
  
public:

  typedef boost::readable_property_map_tag                                
category;
  typedef std::size_t                                                     
value_type;
  typedef std::size_t                                                     
reference;
  typedef typename boost::graph_traits<Polyhedron>::edge_descriptor key_type;

  Polyhedron_edge_index_map_external( Polyhedron const& p) 
    : map( 
p.halfedges_begin(),p.halfedges_end(),0,std::size_t(-1),p.size_of_halfedges() 
)
  {}

  reference operator[](key_type const& e) const { return map[e]; }
  
private:

  CGAL::Unique_hash_map<key_type,std::size_t> map ;
};


template<class Gt, class I, CGAL_HDS_PARAM_, class A>
class Polyhedron_vertex_point_map : public boost::put_get_helper< typename 
Gt::Point_3&, Polyhedron_vertex_point_map<Gt, I, HDS, A> >
{
private:

  typedef CGAL::Polyhedron_3<Gt,I,HDS,A> Polyhedron ;

public:

  typedef typename Gt::Point_3 Point_3 ;
  
  typedef boost::lvalue_property_map_tag                              
category;
  typedef Point_3                                                     
value_type;
  typedef Point_3&                                                    
reference;
  typedef typename boost::graph_traits<Polyhedron>::vertex_descriptor 
key_type;

  Polyhedron_vertex_point_map( Polyhedron& ) {}

  reference operator[](key_type const& v) const { return v->point(); }
};

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
class Polyhedron_vertex_point_const_map : public boost::put_get_helper< 
typename Gt::Point_3 const&
                                                                      , 
Polyhedron_vertex_point_const_map<Gt, I, HDS, A> 
                                                                      >
{
private:

  typedef CGAL::Polyhedron_3<Gt,I,HDS,A> Polyhedron ;

public:

  typedef typename Gt::Point_3 Point_3 ;
  
  typedef boost::readable_property_map_tag                                  
category;
  typedef Point_3                                                           
value_type;
  typedef Point_3 const&                                                    
reference;
  typedef typename boost::graph_traits<Polyhedron>::vertex_descriptor 
key_type;

  Polyhedron_vertex_point_const_map( Polyhedron const& ) {}

  reference operator[](key_type const& v) const { return v->point(); }
};

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
class Polyhedron_vertex_index_map_stored : public 
boost::put_get_helper<std::size_t, Polyhedron_vertex_index_map_stored<Gt, I, 
HDS, A> >
{
private:

  typedef CGAL::Polyhedron_3<Gt,I,HDS,A> Polyhedron ;

public:

  typedef boost::readable_property_map_tag                                  
category;
  typedef std::size_t                                                       
value_type;
  typedef std::size_t                                                       
reference;
  typedef typename boost::graph_traits<Polyhedron>::vertex_descriptor 
key_type;

  Polyhedron_vertex_index_map_stored( Polyhedron const& ) {}

  reference operator[](key_type const& v) const { return v->id(); }
};

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
class Polyhedron_vertex_index_map_external : public 
boost::put_get_helper<std::size_t, Polyhedron_vertex_index_map_external<Gt, 
I, HDS, A> >
{
private:

  typedef CGAL::Polyhedron_3<Gt,I,HDS,A> Polyhedron ;
  
public:

  typedef boost::readable_property_map_tag                                  
category;
  typedef std::size_t                                                       
value_type;
  typedef std::size_t                                                       
reference;
  typedef typename boost::graph_traits<Polyhedron>::vertex_descriptor 
key_type;

  Polyhedron_vertex_index_map_external( Polyhedron const& p) 
    : map( 
p.vertices_begin(),p.vertices_end(),0,std::size_t(-1),p.size_of_vertices() )
  {}

  reference operator[](key_type const& v) const { return map[v]; }
  
private:

  CGAL::Unique_hash_map<key_type,std::size_t> map ;
};


template <class Tag>
struct Polyhedron_property_map {};

template <>
struct Polyhedron_property_map<boost::edge_weight_t> 
{
  template<class Gt, class I, CGAL_HDS_PARAM_, class A>
  struct bind_ 
  {
    typedef Polyhedron_edge_weight_map<Gt,I,HDS,A> type;
    typedef Polyhedron_edge_weight_map<Gt,I,HDS,A> const_type;
  };
};


template <>
struct Polyhedron_property_map<boost::edge_index_t> 
{
  template<class Gt, class I, CGAL_HDS_PARAM_, class A>
  struct bind_ 
  {
    typedef Polyhedron_edge_index_map_stored<Gt,I,HDS,A> type;
    typedef Polyhedron_edge_index_map_stored<Gt,I,HDS,A> const_type;
  };
};

template <>
struct Polyhedron_property_map<edge_external_index_t> 
{
  template<class Gt, class I, CGAL_HDS_PARAM_, class A>
  struct bind_ 
  {
    typedef Polyhedron_edge_index_map_external<Gt,I,HDS,A> type;
    typedef Polyhedron_edge_index_map_external<Gt,I,HDS,A> const_type;
  };
};

template <>
struct Polyhedron_property_map<edge_is_border_t> 
{
  template<class Gt, class I, CGAL_HDS_PARAM_, class A>
  struct bind_ 
  {
    typedef Polyhedron_edge_is_border_map<Gt,I,HDS,A> type;
    typedef Polyhedron_edge_is_border_map<Gt,I,HDS,A> const_type;
  };
};

template <>
struct Polyhedron_property_map<vertex_point_t> 
{
  template<class Gt, class I, CGAL_HDS_PARAM_, class A>
  struct bind_ 
  {
    typedef Polyhedron_vertex_point_map      <Gt,I,HDS,A> type;
    typedef Polyhedron_vertex_point_const_map<Gt,I,HDS,A> const_type;
  };
};

template <>
struct Polyhedron_property_map<boost::vertex_index_t> 
{
  template<class Gt, class I, CGAL_HDS_PARAM_, class A>
  struct bind_ 
  {
    typedef Polyhedron_vertex_index_map_stored<Gt,I,HDS,A> type;
    typedef Polyhedron_vertex_index_map_stored<Gt,I,HDS,A> const_type;
  };
};

template <>
struct Polyhedron_property_map<vertex_external_index_t> 
{
  template<class Gt, class I, CGAL_HDS_PARAM_, class A>
  struct bind_ 
  {
    typedef Polyhedron_vertex_index_map_external<Gt,I,HDS,A> type;
    typedef Polyhedron_vertex_index_map_external<Gt,I,HDS,A> const_type;
  };
};

CGAL_END_NAMESPACE

namespace boost
{

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
inline 
CGAL::Polyhedron_edge_weight_map<Gt,I,HDS,A> get( edge_weight_t, 
CGAL::Polyhedron_3<Gt,I,HDS,A> const& p) 
{
  CGAL::Polyhedron_edge_weight_map<Gt,I,HDS,A> m(p);
  return m;
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
inline 
CGAL::Polyhedron_edge_is_border_map<Gt,I,HDS,A> get( CGAL::edge_is_border_t, 
CGAL::Polyhedron_3<Gt,I,HDS,A> const& p) 
{
  CGAL::Polyhedron_edge_is_border_map<Gt,I,HDS,A> m(p);
  return m;
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
inline 
CGAL::Polyhedron_edge_index_map_stored<Gt,I,HDS,A> get( edge_index_t, 
CGAL::Polyhedron_3<Gt,I,HDS,A> const& p) 
{
  CGAL::Polyhedron_edge_index_map_stored<Gt,I,HDS,A> m(p);
  return m;
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
inline 
CGAL::Polyhedron_edge_index_map_external<Gt,I,HDS,A> get( 
CGAL::edge_external_index_t, CGAL::Polyhedron_3<Gt,I,HDS,A> const& p) 
{
  CGAL::Polyhedron_edge_index_map_external<Gt,I,HDS,A> m(p);
  return m;
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
inline
CGAL::Polyhedron_vertex_point_map<Gt,I,HDS,A> get(CGAL::vertex_point_t, 
CGAL::Polyhedron_3<Gt,I,HDS,A>& p) 
{
  CGAL::Polyhedron_vertex_point_map<Gt,I,HDS,A> m(p);
  return m;
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
inline
CGAL::Polyhedron_vertex_point_const_map<Gt,I,HDS,A> get(CGAL::vertex_point_t, 
CGAL::Polyhedron_3<Gt,I,HDS,A> const& p) 
{
  CGAL::Polyhedron_vertex_point_const_map<Gt,I,HDS,A> m(p);
  return m;
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
inline 
CGAL::Polyhedron_vertex_index_map_stored<Gt,I,HDS,A> get(vertex_index_t, 
CGAL::Polyhedron_3<Gt,I,HDS,A> const& p) 
{
  CGAL::Polyhedron_vertex_index_map_stored<Gt,I,HDS,A> m(p);
  return m;
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
inline 
CGAL::Polyhedron_vertex_index_map_external<Gt,I,HDS,A> 
get(CGAL::vertex_external_index_t, CGAL::Polyhedron_3<Gt,I,HDS,A> const& p) 
{
  CGAL::Polyhedron_vertex_index_map_external<Gt,I,HDS,A> m(p);
  return m;
}


template<class Gt, class I, CGAL_HDS_PARAM_, class A, class Tag>
struct property_map<CGAL::Polyhedron_3<Gt,I,HDS,A>, Tag> 
{
  typedef typename CGAL::Polyhedron_property_map<Tag>::
      template bind_<Gt,I,HDS,A> map_gen;
  typedef typename map_gen::type       type;
  typedef typename map_gen::const_type const_type;
};

template<class Gt, class I, CGAL_HDS_PARAM_, class A, class PropertyTag, 
class Key>
inline
typename property_traits<typename 
property_map<CGAL::Polyhedron_3<Gt,I,HDS,A>,PropertyTag>::type>::reference
get(PropertyTag p, CGAL::Polyhedron_3<Gt,I,HDS,A>& g, const Key& key) 
{
  return get(get(p, g), key);
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A, class PropertyTag, 
class Key>
inline
typename property_traits<typename 
property_map<CGAL::Polyhedron_3<Gt,I,HDS,A>,PropertyTag>::const_type>::reference
get(PropertyTag p, CGAL::Polyhedron_3<Gt,I,HDS,A> const& g, const Key& key) 
{
  return get(get(p, g), key);
}

template<class Gt, class I, CGAL_HDS_PARAM_, class A, class PropertyTag, 
class Key,class Value>
inline 
void put(PropertyTag p, CGAL::Polyhedron_3<Gt,I,HDS,A>& g, const Key& key, 
const Value& value)
{
  typedef typename property_map<CGAL::Polyhedron_3<Gt,I,HDS,A>, 
PropertyTag>::type Map;
  Map pmap = get(p, g);
  put(pmap, key, value);
}


// What are those needed for ???
template<class Gt, class I, CGAL_HDS_PARAM_, class A>
struct edge_property_type<CGAL::Polyhedron_3<Gt,I,HDS,A> > 
{
  typedef edge_weight_t type;
};  

template<class Gt, class I, CGAL_HDS_PARAM_, class A>
struct vertex_property_type<CGAL::Polyhedron_3<Gt,I,HDS,A> > 
{
  typedef CGAL::vertex_point_t type;
};
        
} // namespace boost

#undef CGAL_HDS_PARAM_

#endif // CGAL_BOOST_GRAPH_PROPERTIES_POLYHEDRON_3_H