CGAL users discussion list

[Andreas Fabri <>]

Tux Han wrote:
> Dear CGAL users,
>
> I have a problem of integration of boost graph (BGL) and
> CGAL::Polyhedron_3. If I use dijkstra algorithm with Polyhedron_3, it
> will report some errors. I simplified the code and write a toy project.
> Can you point out the problem?
>
> Is it a bug of CGAL?

Hello,

Yes it is a bug. Please try the attached files. They are not the ultimate
way to do it, as they cast constness away, but they should work for
the time being, and we work on the proper solution.

Best regards,

andreas
// 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_HalfedgeDS.h
 $
// $Id: graph_traits_HalfedgeDS.h 40403 2007-09-20 14:10:09Z afabri $
// 
//
// Author(s)     : Andreas Fabri, Fernando Cacciola

#ifndef CGAL_BOOST_GRAPH_GRAPH_TRAITS_HALFEDGEDS_H
#define CGAL_BOOST_GRAPH_GRAPH_TRAITS_HALFEDGEDS_H

#include <boost/config.hpp>
#include <boost/iterator_adaptors.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>

#include <CGAL/basic.h>
#include <CGAL/Counting_iterator.h>

CGAL_BEGIN_NAMESPACE

template <class Circ, class E>
class HDS_in_halfedge_circulator : public Circ
{
private:
  mutable E e;

public:

  typedef E value_type;
  typedef E* pointer;
  typedef E& reference;

  HDS_in_halfedge_circulator()
    : Circ()
  {}

  HDS_in_halfedge_circulator(Circ c)
    : Circ(c)
  {}

  const E& operator*() const
  {
    e = *this;
    return e;
  }
};

template <class Circ, class E>
class HDS_out_halfedge_circulator : public Circ
{
private:
  mutable E e;

public:

  typedef E value_type;
  typedef E* pointer;
  typedef E& reference;

  HDS_out_halfedge_circulator()
    : Circ()
  {}

  HDS_out_halfedge_circulator(Circ c)
    : Circ(c)
  {}

  const E& operator*() const
  {
    e = *this;
    e = e->opposite();
    return e;
  }
};
  

//  The vertex iterator of the bgl must evaluate to a vertex handle, not to a 
vertex
template < class HDS, class Vertex_iterator, class Vertex_handle>
class HDS_all_vertices_iterator_base {
protected:
    Vertex_iterator nt;
public:
  typedef Vertex_iterator  Iterator;
  typedef HDS_all_vertices_iterator_base<HDS,Vertex_iterator,Vertex_handle> 
Self;

  typedef typename std::iterator_traits<Iterator>::iterator_category 
iterator_category;
  typedef typename std::iterator_traits<Iterator>::difference_type   
difference_type;
  typedef Vertex_handle                                              
value_type;
  typedef value_type                                                 
reference;
  typedef value_type                                                 pointer;

protected:

  HDS_all_vertices_iterator_base() {}
  HDS_all_vertices_iterator_base( Iterator j) : nt(j) {}

public:

  // OPERATIONS Forward Category
  // ---------------------------

  bool operator==( const Self& i) const { return ( nt == i.nt); }
  bool operator!=( const Self& i) const { return !(nt == i.nt );   }
  value_type  operator*() const  { return nt; }
  value_type    operator->()  { return nt; }

  Self& operator++() {
    ++nt;
    return *this;
  }

  Self  operator++(int) {
    Self tmp = *this;
    ++*this;
    return tmp;
  }
};

template < class HDS >
class HDS_all_vertices_const_iterator 
  : public HDS_all_vertices_iterator_base<HDS,typename 
HDS::Vertex_const_iterator,typename HDS::Vertex_const_handle>
{
  typedef HDS_all_vertices_iterator_base<HDS,typename 
HDS::Vertex_const_iterator,typename HDS::Vertex_const_handle> Base ;
  
public:

  typedef typename HDS::Vertex_const_iterator Iterator;

  HDS_all_vertices_const_iterator() {}
  HDS_all_vertices_const_iterator( Iterator j) : Base(j) {}
};


template < class HDS >
class HDS_all_vertices_iterator 
  : public HDS_all_vertices_iterator_base<HDS,typename 
HDS::Vertex_iterator,typename HDS::Vertex_handle>
{
  typedef HDS_all_vertices_iterator_base<HDS,typename 
HDS::Vertex_iterator,typename HDS::Vertex_handle> Base ;
  
public:

  typedef typename HDS::Vertex_iterator Iterator;

  HDS_all_vertices_iterator() {}
  HDS_all_vertices_iterator( Iterator j) : Base(j) {}
};

template < class HDS, class Iterator_, class Value_type>
class HDS_all_edges_iterator_base {
protected:
  Iterator_ nt;
public:
  typedef Iterator_  Iterator;
  typedef HDS_all_edges_iterator_base<HDS,Iterator_,Value_type> Self;

  typedef typename std::iterator_traits<Iterator>::iterator_category 
iterator_category;
  typedef typename std::iterator_traits<Iterator>::difference_type   
difference_type;
  typedef Value_type                                                 
value_type;
  typedef value_type                                                 
reference;
  typedef value_type                                                 pointer;
  
protected:

  HDS_all_edges_iterator_base() {}
  HDS_all_edges_iterator_base( Iterator j) : nt(j) {}

public:

  // OPERATIONS Forward Category
  // ---------------------------


  bool operator==( const Self& i) const { return ( nt == i.nt); }
  bool operator!=( const Self& i) const { return !(nt == i.nt );   }
  value_type  operator*() const  { return nt; }
  value_type    operator->()  { return nt; }

  Self& operator++() {
    ++nt;
    return *this;
  }

  Self  operator++(int) {
    Self tmp = *this;
    ++*this;
    return tmp;
  }
};

template < class HDS >
class HDS_all_halfedges_const_iterator 
  : public HDS_all_edges_iterator_base<HDS,typename 
HDS::Halfedge_const_iterator,typename HDS::Halfedge_const_handle>
{
  typedef HDS_all_edges_iterator_base<HDS,typename 
HDS::Halfedge_const_iterator,typename HDS::Halfedge_const_handle> Base ;
  
public:

  typedef typename HDS::Halfedge_const_iterator Iterator;

  HDS_all_halfedges_const_iterator() {}
  HDS_all_halfedges_const_iterator( Iterator j) : Base(j) {}
};

template < class HDS >
class HDS_all_halfedges_iterator 
  : public HDS_all_edges_iterator_base<HDS,typename 
HDS::Halfedge_iterator,typename HDS::Halfedge_handle>
{
  typedef HDS_all_edges_iterator_base<HDS,typename 
HDS::Halfedge_iterator,typename HDS::Halfedge_handle> Base ;
  
public:

  typedef typename HDS::Halfedge_iterator Iterator;

  HDS_all_halfedges_iterator() {}
  HDS_all_halfedges_iterator( Iterator j) : Base(j) {}
};

template <class HDS_>
struct HDS_graph_traits
{
public :
  
  struct HDS_graph_traversal_category : public virtual 
boost::bidirectional_graph_tag,
                                        //                                    
    public virtual boost::adjacency_graph_tag,
                                        public virtual 
boost::vertex_list_graph_tag,
                                        public virtual 
boost::edge_list_graph_tag
  {};

  typedef HDS_ HDS;

  typedef typename HDS::Vertex_handle   vertex_descriptor;
  typedef typename HDS::Halfedge_handle edge_descriptor;
  
  typedef HDS_all_vertices_iterator<HDS>  vertex_iterator;
  typedef HDS_all_halfedges_iterator<HDS>  edge_iterator;
  
private:

  typedef typename HDS::Halfedge_around_vertex_circulator 
Halfedge_around_vertex_circulator ;
  
  typedef 
HDS_out_halfedge_circulator<Halfedge_around_vertex_circulator,edge_descriptor>
 out_edge_circulator ;
  typedef HDS_in_halfedge_circulator 
<Halfedge_around_vertex_circulator,edge_descriptor> in_edge_circulator ;
  
public :

  typedef Counting_iterator<out_edge_circulator, edge_descriptor> 
out_edge_iterator;
  typedef Counting_iterator<in_edge_circulator , edge_descriptor> 
in_edge_iterator;
                                 
  typedef boost::directed_tag               directed_category;
  typedef boost::disallow_parallel_edge_tag edge_parallel_category; 
  typedef HDS_graph_traversal_category      traversal_category;
  
  typedef typename HDS::size_type vertices_size_type;
  typedef vertices_size_type      edges_size_type;
  typedef vertices_size_type      degree_size_type;
};


CGAL_END_NAMESPACE

#endif // CGAL_BOOST_GRAPH_GRAPH_TRAITS_HALFEDGEDS_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/graph_traits_Polyhedron_3.h
 $
// $Id: graph_traits_Polyhedron_3.h 40403 2007-09-20 14:10:09Z 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> >::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 40403 2007-09-20 14:10:09Z afabri $
// 
//
// 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