stanford_graph.hpp

来自「CGAL is a collaborative effort of severa」· HPP 代码 · 共 582 行 · 第 1/2 页

#define SGB_PROPERTY_TAG(KIND,TAG) \
  template <class T> struct TAG##_property { \
    typedef KIND##_property_tag kind; \
    typedef T type; \
  };
  SGB_PROPERTY_TAG(vertex, u)
  SGB_PROPERTY_TAG(vertex, v)
  SGB_PROPERTY_TAG(vertex, w)
  SGB_PROPERTY_TAG(vertex, x)
  SGB_PROPERTY_TAG(vertex, y)
  SGB_PROPERTY_TAG(vertex, z)
 
  // Edge Property Tags
  SGB_PROPERTY_TAG(edge, a)
  SGB_PROPERTY_TAG(edge, b)

  // Various Utility Maps

  // helpers
  inline Vertex*& get_util(util& u, Vertex*) { return u.V; }
  inline Arc*& get_util(util& u, Arc*) { return u.A; }
  inline sgb_graph_ptr& get_util(util& u, sgb_graph_ptr) { return u.G; }
  inline char*& get_util(util& u, char*) { return u.S; }
  inline long& get_util(util& u, long) { return u.I; }

#define SGB_GET_UTIL_FIELD(KIND,X) \
  template <class T> \
  inline T& get_util_field(KIND* k, X##_property<T>) { \
    return get_util(k->X, T());  }

  SGB_GET_UTIL_FIELD(Vertex, u)
  SGB_GET_UTIL_FIELD(Vertex, v)
  SGB_GET_UTIL_FIELD(Vertex, w)
  SGB_GET_UTIL_FIELD(Vertex, x)
  SGB_GET_UTIL_FIELD(Vertex, y)
  SGB_GET_UTIL_FIELD(Vertex, z)

  SGB_GET_UTIL_FIELD(Arc, a)
  SGB_GET_UTIL_FIELD(Arc, b)

  // Vertex Utility Map
  template <class Tag, class Ref>
  class sgb_vertex_util_map
    : public boost::put_get_helper<Ref, sgb_vertex_util_map<Tag, Ref> >
  {
  public:
    typedef boost::lvalue_property_map_tag category;
    typedef typename Tag::type value_type;
    typedef Vertex* key_type;
    typedef Ref reference;
    reference operator[](Vertex* v) const {
      return get_util_field(v, Tag()); 
    }
  };

  // Edge Utility Map
  template <class Tag, class Ref>
  class sgb_edge_util_map
    : public boost::put_get_helper<Ref, sgb_edge_util_map<Tag, Ref> >
  {
  public:
    typedef boost::lvalue_property_map_tag category;
    typedef typename Tag::type value_type;
    typedef Vertex* key_type;
    typedef Ref reference;
    reference operator[](const sgb_edge& e) const {
      return get_util_field(e._arc, Tag()); 
    }
  };

#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION  

  template <class Tag>
  inline sgb_vertex_util_map<Tag, const typename Tag::type&>
  get_property_map(Tag, const sgb_graph_ptr& g, vertex_property_tag) {
    return sgb_vertex_util_map<Tag, const typename Tag::type&>();
  }
  template <class Tag>
  inline sgb_vertex_util_map<Tag, typename Tag::type&>
  get_property_map(Tag, sgb_graph_ptr& g, vertex_property_tag) {
    return sgb_vertex_util_map<Tag, typename Tag::type&>();
  }

  template <class Tag>
  inline sgb_edge_util_map<Tag, const typename Tag::type&> 
  get_property_map(Tag, const sgb_graph_ptr& g, edge_property_tag) {
    return sgb_edge_util_map<Tag, const typename Tag::type&>();
  }
  template <class Tag>
  inline sgb_edge_util_map<Tag, typename Tag::type&> 
  get_property_map(Tag, sgb_graph_ptr& g, edge_property_tag) {
    return sgb_edge_util_map<Tag, typename Tag::type&>();
  }

#endif // ! BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

  // Edge Length Access
  template <class Ref>
  class sgb_edge_length_map
    : public boost::put_get_helper<Ref, sgb_edge_length_map<Ref> >
  {
  public:
    typedef boost::lvalue_property_map_tag category;
    typedef long value_type;
    typedef sgb_edge key_type;
    typedef Ref reference;
    reference operator[](const sgb_edge& e) const { 
      return e._arc->len; 
    }
  };

  inline sgb_edge_length_map<const long&>
  get(edge_length_t, const sgb_graph_ptr&) { 
    return sgb_edge_length_map<const long&>(); 
  }
  inline sgb_edge_length_map<const long&>
  get(edge_length_t, const sgb_const_graph_ptr&) { 
    return sgb_edge_length_map<const long&>(); 
  }
  inline sgb_edge_length_map<long&>
  get(edge_length_t, sgb_graph_ptr&) { 
    return sgb_edge_length_map<long&>(); 
  }
  inline long
  get(edge_length_t, const sgb_graph_ptr&, const sgb_edge& key) {
    return key._arc->len;
  }
  inline long
  get(edge_length_t, const sgb_const_graph_ptr&, const sgb_edge& key) {
    return key._arc->len;
  }
  inline void
  put(edge_length_t, sgb_graph_ptr&, const sgb_edge& key, long value)
  {
    key._arc->len = value;
  }

  // Property Map Traits Classes
  template <>
  struct property_map<sgb_graph_ptr, edge_length_t> {
    typedef sgb_edge_length_map<long&> type;
    typedef sgb_edge_length_map<const long&> const_type;
  };
  template <>
  struct property_map<sgb_graph_ptr, vertex_index_t> {
    typedef sgb_vertex_id_map type;
    typedef sgb_vertex_id_map const_type;
  };
  template <>
  struct property_map<sgb_graph_ptr, vertex_name_t> {
    typedef sgb_vertex_name_map type;
    typedef sgb_vertex_name_map const_type;
  };

  template <>
  struct property_map<sgb_const_graph_ptr, edge_length_t> {
    typedef sgb_edge_length_map<const long&> const_type;
  };
  template <>
  struct property_map<sgb_const_graph_ptr, vertex_index_t> {
    typedef sgb_vertex_id_map const_type;
  };
  template <>
  struct property_map<sgb_const_graph_ptr, vertex_name_t> {
    typedef sgb_vertex_name_map const_type;
  };

#if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)

  namespace detail {
    template <class Kind, class PropertyTag>
    struct sgb_choose_property_map { };
    template <class PropertyTag>
    struct sgb_choose_property_map<vertex_property_tag, PropertyTag> {
      typedef typename PropertyTag::type value_type;
      typedef sgb_vertex_util_map<PropertyTag, value_type&> type;
      typedef sgb_vertex_util_map<PropertyTag, const value_type&> const_type;
    };
    template <class PropertyTag>
    struct sgb_choose_property_map<edge_property_tag, PropertyTag> {
      typedef typename PropertyTag::type value_type;
      typedef sgb_edge_util_map<PropertyTag, value_type&> type;
      typedef sgb_edge_util_map<PropertyTag, const value_type&> const_type;
    };
  } // namespace detail
  template <class PropertyTag>
  struct property_map<sgb_graph_ptr, PropertyTag> {
    typedef typename property_kind<PropertyTag>::type Kind;
    typedef detail::sgb_choose_property_map<Kind, PropertyTag> Choice;
    typedef typename Choice::type type;
    typedef typename Choice::const_type const_type;
  };
  template <class PropertyTag>
  struct property_map<sgb_const_graph_ptr, PropertyTag> {
    typedef typename property_kind<PropertyTag>::type Kind;
    typedef detail::sgb_choose_property_map<Kind, PropertyTag> Choice;
    typedef typename Choice::const_type const_type;
  };

#define SGB_UTIL_ACCESSOR(KIND,X) \
  template <class T> \
  inline sgb_##KIND##_util_map< X##_property<T>, T&> \
  get(X##_property<T>, sgb_graph_ptr&) { \
    return sgb_##KIND##_util_map< X##_property<T>, T&>(); \
  } \
  template <class T> \
  inline sgb_##KIND##_util_map< X##_property<T>, const T&> \
  get(X##_property<T>, const sgb_graph_ptr&) { \
    return sgb_##KIND##_util_map< X##_property<T>, const T&>(); \
  } \
  template <class T> \
  inline sgb_##KIND##_util_map< X##_property<T>, const T&> \
  get(X##_property<T>, const sgb_const_graph_ptr&) { \
    return sgb_##KIND##_util_map< X##_property<T>, const T&>(); \
  } \
  template <class T, class Key> \
  inline typename \
  sgb_##KIND##_util_map< X##_property<T>, const T&>::value_type \
  get(X##_property<T>, const sgb_graph_ptr&, const Key& key) { \
    return sgb_##KIND##_util_map< X##_property<T>, const T&>()[key]; \
  } \
  template <class T, class Key> \
  inline typename \
  sgb_##KIND##_util_map< X##_property<T>, const T&>::value_type \
  get(X##_property<T>, const sgb_const_graph_ptr&, const Key& key) { \
    return sgb_##KIND##_util_map< X##_property<T>, const T&>()[key]; \
  } \
  template <class T, class Key, class Value> \
  inline  void \
  put(X##_property<T>, sgb_graph_ptr&, const Key& key, const Value& value) { \
    sgb_##KIND##_util_map< X##_property<T>, T&>()[key] = value; \
  }

#else // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

#define SGB_UTIL_ACCESSOR_TYPE(KIND,TAG,TYPE) \
  inline sgb_##KIND##_util_map< TAG<TYPE>, TYPE& > \
  get(TAG<TYPE>, sgb_graph_ptr&) { \
    return sgb_##KIND##_util_map< TAG<TYPE>, TYPE& >(); \
  } \
  inline sgb_##KIND##_util_map< TAG<TYPE>, const TYPE& > \
  get(TAG<TYPE>, const sgb_graph_ptr&) { \
    return sgb_##KIND##_util_map< TAG<TYPE>, const TYPE& >(); \
  } \
  inline sgb_##KIND##_util_map< TAG<TYPE>, const TYPE& > \
  get(TAG<TYPE>, const sgb_const_graph_ptr&) { \
    return sgb_##KIND##_util_map< TAG<TYPE>, const TYPE& >(); \
  } \
  template <class Key> \
  inline typename sgb_##KIND##_util_map< TAG<TYPE>, const TYPE& >::value_type \
  get(TAG<TYPE>, const sgb_graph_ptr&, const Key& key) { \
    return sgb_##KIND##_util_map< TAG<TYPE>, const TYPE& >()[key]; \
  } \
  template <class Key> \
  inline typename sgb_##KIND##_util_map< TAG<TYPE>, const TYPE& >::value_type \
  get(TAG<TYPE>, const sgb_const_graph_ptr&, const Key& key) { \
    return sgb_##KIND##_util_map< TAG<TYPE>, const TYPE& >()[key]; \
  } \
  template <class Key, class Value> \
  inline  void \
  put(TAG<TYPE>, sgb_graph_ptr&, const Key& key, const Value& value) { \
    sgb_##KIND##_util_map< TAG<TYPE>, TYPE& >()[key] = value; \
  } \
  template <> struct property_map<sgb_graph_ptr, TAG<TYPE> > { \
    typedef sgb_##KIND##_util_map< TAG<TYPE>, TYPE&> type; \
    typedef sgb_##KIND##_util_map< TAG<TYPE>, const TYPE&> const_type; \
  }

#define SGB_UTIL_ACCESSOR(KIND,TAG) \
  SGB_UTIL_ACCESSOR_TYPE(KIND, TAG##_property, Vertex*); \
  SGB_UTIL_ACCESSOR_TYPE(KIND, TAG##_property, Arc*); \
  SGB_UTIL_ACCESSOR_TYPE(KIND, TAG##_property, sgb_graph_ptr); \
  SGB_UTIL_ACCESSOR_TYPE(KIND, TAG##_property, long); \
  SGB_UTIL_ACCESSOR_TYPE(KIND, TAG##_property, char*);

#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

  SGB_UTIL_ACCESSOR(vertex, u)
  SGB_UTIL_ACCESSOR(vertex, v)
  SGB_UTIL_ACCESSOR(vertex, w)
  SGB_UTIL_ACCESSOR(vertex, x)
  SGB_UTIL_ACCESSOR(vertex, y)
  SGB_UTIL_ACCESSOR(vertex, z)

  SGB_UTIL_ACCESSOR(edge, a)
  SGB_UTIL_ACCESSOR(edge, b)

} // namespace boost

#endif // BOOST_GRAPH_SGB_GRAPH_HPP