Chris@16: //=======================================================================
Chris@16: // Copyright 1997-2001 University of Notre Dame.
Chris@16: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: #ifndef BOOST_GRAPH_SGB_GRAPH_HPP
Chris@16: #define BOOST_GRAPH_SGB_GRAPH_HPP
Chris@16: 
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/iterator.hpp>
Chris@16: #include <boost/operators.hpp>
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/graph/properties.hpp>
Chris@16: 
Chris@16: // Thanks to Andreas Scherer for numerous suggestions and fixes!
Chris@16: 
Chris@16: // This file adapts a Stanford GraphBase (SGB) Graph pointer into a
Chris@16: // VertexListGraph. Note that a graph adaptor class is not needed, 
Chris@16: // SGB's Graph* is used as is. The VertexListGraph concept is fulfilled by
Chris@16: // defining the appropriate non-member functions for Graph*.
Chris@16: //
Chris@16: // The PROTOTYPES change file extensions to SGB must be applied so
Chris@16: // that the SGB functions have real prototypes which are necessary for
Chris@16: // the C++ compiler. To apply the PROTOTYPES extensions, before you do
Chris@16: // "make tests install" for SGB do "ln -s PROTOTYPES/* ." to the SGB
Chris@16: // root directory (or just copy all the files from the PROTOTYPES
Chris@16: // directory to the SGB root directory).
Chris@16: //
Chris@16: extern "C" {
Chris@16:         // We include all global definitions for the general stuff
Chris@16:         // of The Stanford GraphBase and its various graph generator
Chris@16:         // functions by reading all SGB headerfiles as in section 2 of
Chris@16:         // the "test_sample" program.
Chris@16: #include <gb_graph.h> /* SGB data structures */
Chris@16: #include <gb_io.h> /* SGB input/output routines */
Chris@16: #include <gb_flip.h> /* random number generator */
Chris@16: #include <gb_dijk.h> /* routines for shortest paths */
Chris@16: #include <gb_basic.h> /* the basic graph operations */
Chris@16: #undef empty /* avoid name clash with C++ standard library */
Chris@16:         inline Graph* empty( long n ) /* and provide workaround */
Chris@16:         { return board(n,0L,0L,0L,2L,0L,0L); }
Chris@16: #include <gb_books.h> /* graphs based on literature */
Chris@16: #include <gb_econ.h> /* graphs based on economic data */
Chris@16: #include <gb_games.h> /* graphs based on football scores */
Chris@16: #include <gb_gates.h> /* graphs based on logic circuits */
Chris@16: #undef val /* avoid name clash with g++ headerfile stl_tempbuf.h */
Chris@16:         // val ==> Vertex::x.I
Chris@16: #include <gb_lisa.h> /* graphs based on Mona Lisa */
Chris@16: #include <gb_miles.h> /* graphs based on mileage data */
Chris@16: #include <gb_plane.h> /* planar graphs */
Chris@16: #include <gb_raman.h> /* Ramanujan graphs */
Chris@16: #include <gb_rand.h> /* random graphs */
Chris@16: #include <gb_roget.h> /* graphs based on Roget's Thesaurus */
Chris@16: #include <gb_save.h> /* we save results in ASCII format */
Chris@16: #include <gb_words.h> /* five-letter-word graphs */
Chris@16: #undef weight /* avoid name clash with BGL parameter */
Chris@16:         // weight ==> Vertex::u.I
Chris@16: }
Chris@16: 
Chris@16: namespace boost {
Chris@16:   class sgb_edge;
Chris@16: }
Chris@16: 
Chris@16: class sgb_out_edge_iterator;
Chris@16: class sgb_adj_iterator;
Chris@16: class sgb_vertex_iterator;
Chris@16: 
Chris@16: namespace boost {
Chris@16:   typedef Graph* sgb_graph_ptr;
Chris@16:   typedef const Graph* sgb_const_graph_ptr;
Chris@16: 
Chris@16:   struct sgb_traversal_tag :
Chris@16:     public virtual vertex_list_graph_tag,
Chris@16:     public virtual incidence_graph_tag,
Chris@16:     public virtual adjacency_graph_tag { };
Chris@16: 
Chris@16:   template <> struct graph_traits<sgb_graph_ptr> {
Chris@16:     typedef Vertex* vertex_descriptor;
Chris@16:     typedef boost::sgb_edge edge_descriptor;
Chris@16:     typedef sgb_out_edge_iterator out_edge_iterator;
Chris@16:     typedef void in_edge_iterator;
Chris@16:     typedef sgb_adj_iterator adjacency_iterator;
Chris@16:     typedef sgb_vertex_iterator vertex_iterator;
Chris@16:     typedef void edge_iterator;
Chris@16:     typedef long vertices_size_type;
Chris@16:     typedef long edge_size_type;
Chris@16:     typedef long degree_size_type;
Chris@16:     typedef directed_tag directed_category;
Chris@16:     typedef sgb_traversal_tag traversal_category;
Chris@16:     typedef allow_parallel_edge_tag edge_parallel_category;
Chris@16:   };
Chris@16:   template <> struct graph_traits<sgb_const_graph_ptr> {
Chris@16:     typedef Vertex* vertex_descriptor;
Chris@16:     typedef boost::sgb_edge edge_descriptor;
Chris@16:     typedef sgb_out_edge_iterator out_edge_iterator;
Chris@16:     typedef void in_edge_iterator;
Chris@16:     typedef sgb_adj_iterator adjacency_iterator;
Chris@16:     typedef sgb_vertex_iterator vertex_iterator;
Chris@16:     typedef void edge_iterator;
Chris@16:     typedef long vertices_size_type;
Chris@16:     typedef long edge_size_type;
Chris@16:     typedef long degree_size_type;
Chris@16:     typedef directed_tag directed_category;
Chris@16:     typedef sgb_traversal_tag traversal_category;
Chris@16:     typedef allow_parallel_edge_tag edge_parallel_category;
Chris@16:   };
Chris@16: }
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   struct edge_length_t {
Chris@16:     typedef edge_property_tag kind;
Chris@16:   };
Chris@16: 
Chris@16:   // We could just use Arc* as the edge descriptor type, but
Chris@16:   // we want to add the source(e,g) function which requires
Chris@16:   // that we carry along a pointer to the source vertex.
Chris@16:   class sgb_edge {
Chris@16:     typedef sgb_edge self;
Chris@16:   public:
Chris@16:     sgb_edge() : _arc(0), _src(0) { }
Chris@16:     sgb_edge(Arc* a, Vertex* s) : _arc(a), _src(s) { }
Chris@16:     friend Vertex* source(self e, sgb_const_graph_ptr) { return e._src; }
Chris@16:     friend Vertex* target(self e, sgb_const_graph_ptr) { return e._arc->tip; }
Chris@16:     friend bool operator==(const self& a, const self& b) {
Chris@16:       return a._arc == b._arc; }
Chris@16:     friend bool operator!=(const self& a, const self& b) {
Chris@16:       return a._arc != b._arc; }
Chris@16: #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
Chris@16:     template <class Ref> friend class sgb_edge_length_map;
Chris@16:     template <class Tag, class Ref> friend class sgb_edge_util_map;
Chris@16:     friend long get(edge_length_t, const sgb_graph_ptr&, const sgb_edge& key);
Chris@16:     friend long get(edge_length_t, const sgb_const_graph_ptr&, const sgb_edge& key);
Chris@16:     friend void put(edge_length_t, sgb_graph_ptr&, const sgb_edge& key, long value);
Chris@16:   protected:
Chris@16: #endif
Chris@16:     Arc* _arc;
Chris@16:     Vertex* _src;
Chris@16:   };
Chris@16: } // namespace boost
Chris@16: 
Chris@16:   class sgb_out_edge_iterator
Chris@16:     : public boost::forward_iterator_helper<
Chris@16:         sgb_out_edge_iterator, boost::sgb_edge, 
Chris@16:         std::ptrdiff_t, boost::sgb_edge*, boost::sgb_edge>
Chris@16:   {
Chris@16:     typedef sgb_out_edge_iterator self;
Chris@16:   public:
Chris@16:     sgb_out_edge_iterator() : _src(0), _arc(0) {}
Chris@16:     sgb_out_edge_iterator(Vertex* s, Arc* d) : _src(s), _arc(d) {}
Chris@16:     boost::sgb_edge operator*() { return boost::sgb_edge(_arc, _src); }
Chris@16:     self& operator++() { _arc = _arc->next; return *this; }
Chris@16:     friend bool operator==(const self& x, const self& y) {
Chris@16:       return x._arc == y._arc; }
Chris@16:   protected:
Chris@16:     Vertex* _src;
Chris@16:     Arc* _arc;
Chris@16:   };
Chris@16: 
Chris@16:   class sgb_adj_iterator
Chris@16:     : public boost::forward_iterator_helper<
Chris@16:         sgb_adj_iterator, Vertex*, std::ptrdiff_t, Vertex**,Vertex*>
Chris@16:   {
Chris@16:     typedef sgb_adj_iterator self;
Chris@16:   public:
Chris@16:     sgb_adj_iterator() : _arc(0) {}
Chris@16:     sgb_adj_iterator(Arc* d) : _arc(d) {}
Chris@16:     Vertex* operator*() { return _arc->tip; }
Chris@16:     self& operator++() { _arc = _arc->next; return *this; }
Chris@16:     friend bool operator==(const self& x, const self& y) {
Chris@16:       return x._arc == y._arc; }
Chris@16:   protected:
Chris@16:     Arc* _arc;
Chris@16:   };
Chris@16: 
Chris@16:   // The reason we have this instead of just using Vertex* is that we
Chris@16:   // want to use Vertex* as the vertex_descriptor instead of just
Chris@16:   // Vertex, which avoids problems with boost passing vertex descriptors
Chris@16:   // by value and how that interacts with the sgb_vertex_id_map.
Chris@16:   class sgb_vertex_iterator
Chris@16:     : public boost::forward_iterator_helper<
Chris@16:         sgb_vertex_iterator, Vertex*, std::ptrdiff_t, Vertex**, Vertex*>
Chris@16:   {
Chris@16:     typedef sgb_vertex_iterator self;
Chris@16:   public:
Chris@16:     sgb_vertex_iterator() : _v(0) { }
Chris@16:     sgb_vertex_iterator(Vertex* v) : _v(v) { }
Chris@16:     Vertex* operator*() { return _v; }
Chris@16:     self& operator++() { ++_v; return *this; }
Chris@16:     friend bool operator==(const self& x, const self& y) {
Chris@16:       return x._v == y._v; }
Chris@16:   protected:
Chris@16:     Vertex* _v;
Chris@16:   };
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   inline std::pair<sgb_vertex_iterator,sgb_vertex_iterator>
Chris@16:   vertices(sgb_const_graph_ptr g)
Chris@16:   {
Chris@16:     return std::make_pair(sgb_vertex_iterator(g->vertices),
Chris@16:                           sgb_vertex_iterator(g->vertices + g->n));
Chris@16:   }
Chris@16: 
Chris@16:   inline std::pair<sgb_out_edge_iterator,sgb_out_edge_iterator>
Chris@16:   out_edges(Vertex* u, sgb_const_graph_ptr)
Chris@16:   {
Chris@16:     return std::make_pair( sgb_out_edge_iterator(u, u->arcs),
Chris@16:                            sgb_out_edge_iterator(u, 0) );
Chris@16:   }
Chris@16: 
Chris@16:   inline boost::graph_traits<sgb_graph_ptr>::degree_size_type
Chris@16:   out_degree(Vertex* u, sgb_const_graph_ptr g)
Chris@16:   {
Chris@16:     boost::graph_traits<sgb_graph_ptr>::out_edge_iterator i, i_end;
Chris@16:     boost::tie(i, i_end) = out_edges(u, g);
Chris@16:     return std::distance(i, i_end);
Chris@16:   }
Chris@16: 
Chris@16:   // in_edges?
Chris@16: 
Chris@16:   inline std::pair<sgb_adj_iterator,sgb_adj_iterator>
Chris@16:   adjacent_vertices(Vertex* u, sgb_const_graph_ptr)
Chris@16:   {
Chris@16:     return std::make_pair( sgb_adj_iterator(u->arcs),
Chris@16:                            sgb_adj_iterator(0) );
Chris@16:   }
Chris@16: 
Chris@16:   inline long num_vertices(sgb_const_graph_ptr g) { return g->n; }
Chris@16:   inline long num_edges(sgb_const_graph_ptr g) { return g->m; }
Chris@16: 
Chris@16:   inline Vertex* vertex(long v, sgb_const_graph_ptr g)
Chris@16:     { return g->vertices + v; }
Chris@16: 
Chris@16:   // Various Property Maps
Chris@16: 
Chris@16:   // Vertex ID
Chris@16:   class sgb_vertex_id_map
Chris@16:     : public boost::put_get_helper<long, sgb_vertex_id_map>
Chris@16:   {
Chris@16:   public:
Chris@16:     typedef boost::readable_property_map_tag category;
Chris@16:     typedef long value_type;
Chris@16:     typedef long reference;
Chris@16:     typedef Vertex* key_type;
Chris@16:     sgb_vertex_id_map() : _g(0) { }
Chris@16:     sgb_vertex_id_map(sgb_graph_ptr g) : _g(g) { }
Chris@16:     long operator[](Vertex* v) const { return v - _g->vertices; }
Chris@16:   protected:
Chris@16:     sgb_graph_ptr _g;
Chris@16:   };
Chris@16:   inline sgb_vertex_id_map get(vertex_index_t, sgb_graph_ptr g) {
Chris@16:     return sgb_vertex_id_map(g);
Chris@16:   }
Chris@16: 
Chris@16:   // Vertex Name  
Chris@16:   class sgb_vertex_name_map
Chris@16:     : public boost::put_get_helper<char*, sgb_vertex_name_map>
Chris@16:   {
Chris@16:   public:
Chris@16:     typedef boost::readable_property_map_tag category;
Chris@16:     typedef char* value_type;
Chris@16:     typedef char* reference;
Chris@16:     typedef Vertex* key_type;
Chris@16:     char* operator[](Vertex* v) const { return v->name; }
Chris@16:   };
Chris@16:   inline sgb_vertex_name_map get(vertex_name_t, sgb_graph_ptr) {
Chris@16:     return sgb_vertex_name_map();
Chris@16:   }
Chris@16: 
Chris@16:   // Vertex Property Tags
Chris@16: #define SGB_PROPERTY_TAG(KIND,TAG) \
Chris@16:   template <class T> struct TAG##_property { \
Chris@16:     typedef KIND##_property_tag kind; \
Chris@16:     typedef T type; \
Chris@16:   };
Chris@16:   SGB_PROPERTY_TAG(vertex, u)
Chris@16:   SGB_PROPERTY_TAG(vertex, v)
Chris@16:   SGB_PROPERTY_TAG(vertex, w)
Chris@16:   SGB_PROPERTY_TAG(vertex, x)
Chris@16:   SGB_PROPERTY_TAG(vertex, y)
Chris@16:   SGB_PROPERTY_TAG(vertex, z)
Chris@16:  
Chris@16:   // Edge Property Tags
Chris@16:   SGB_PROPERTY_TAG(edge, a)
Chris@16:   SGB_PROPERTY_TAG(edge, b)
Chris@16: 
Chris@16:   // Various Utility Maps
Chris@16: 
Chris@16:   // helpers
Chris@16:   inline Vertex*& get_util(util& u, Vertex*) { return u.V; }
Chris@16:   inline Arc*& get_util(util& u, Arc*) { return u.A; }
Chris@16:   inline sgb_graph_ptr& get_util(util& u, sgb_graph_ptr) { return u.G; }
Chris@16:   inline char*& get_util(util& u, char*) { return u.S; }
Chris@16:   inline long& get_util(util& u, long) { return u.I; }
Chris@16: 
Chris@16: #define SGB_GET_UTIL_FIELD(KIND,X) \
Chris@16:   template <class T> \
Chris@16:   inline T& get_util_field(KIND* k, X##_property<T>) { \
Chris@16:     return get_util(k->X, T());  }
Chris@16: 
Chris@16:   SGB_GET_UTIL_FIELD(Vertex, u)
Chris@16:   SGB_GET_UTIL_FIELD(Vertex, v)
Chris@16:   SGB_GET_UTIL_FIELD(Vertex, w)
Chris@16:   SGB_GET_UTIL_FIELD(Vertex, x)
Chris@16:   SGB_GET_UTIL_FIELD(Vertex, y)
Chris@16:   SGB_GET_UTIL_FIELD(Vertex, z)
Chris@16: 
Chris@16:   SGB_GET_UTIL_FIELD(Arc, a)
Chris@16:   SGB_GET_UTIL_FIELD(Arc, b)
Chris@16: 
Chris@16:   // Vertex Utility Map
Chris@16:   template <class Tag, class Ref>
Chris@16:   class sgb_vertex_util_map
Chris@16:     : public boost::put_get_helper<Ref, sgb_vertex_util_map<Tag, Ref> >
Chris@16:   {
Chris@16:     Tag tag;
Chris@16:   public:
Chris@16:     explicit sgb_vertex_util_map(Tag tag = Tag()): tag(tag) {}
Chris@16:     typedef boost::lvalue_property_map_tag category;
Chris@16:     typedef typename Tag::type value_type;
Chris@16:     typedef Vertex* key_type;
Chris@16:     typedef Ref reference;
Chris@16:     reference operator[](Vertex* v) const {
Chris@16:       return get_util_field(v, tag); 
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   // Edge Utility Map
Chris@16:   template <class Tag, class Ref>
Chris@16:   class sgb_edge_util_map
Chris@16:     : public boost::put_get_helper<Ref, sgb_edge_util_map<Tag, Ref> >
Chris@16:   {
Chris@16:     Tag tag;
Chris@16:   public:
Chris@16:     explicit sgb_edge_util_map(Tag tag = Tag()): tag(tag) {}
Chris@16:     typedef boost::lvalue_property_map_tag category;
Chris@16:     typedef typename Tag::type value_type;
Chris@16:     typedef Vertex* key_type;
Chris@16:     typedef Ref reference;
Chris@16:     reference operator[](const sgb_edge& e) const {
Chris@16:       return get_util_field(e._arc, tag); 
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16: 
Chris@16:   template <class Tag>
Chris@16:   inline sgb_vertex_util_map<Tag, const typename Tag::type&>
Chris@16:   get_property_map(Tag, const sgb_graph_ptr& g, vertex_property_tag) {
Chris@16:     return sgb_vertex_util_map<Tag, const typename Tag::type&>();
Chris@16:   }
Chris@16:   template <class Tag>
Chris@16:   inline sgb_vertex_util_map<Tag, typename Tag::type&>
Chris@16:   get_property_map(Tag, sgb_graph_ptr& g, vertex_property_tag) {
Chris@16:     return sgb_vertex_util_map<Tag, typename Tag::type&>();
Chris@16:   }
Chris@16: 
Chris@16:   template <class Tag>
Chris@16:   inline sgb_edge_util_map<Tag, const typename Tag::type&> 
Chris@16:   get_property_map(Tag, const sgb_graph_ptr& g, edge_property_tag) {
Chris@16:     return sgb_edge_util_map<Tag, const typename Tag::type&>();
Chris@16:   }
Chris@16:   template <class Tag>
Chris@16:   inline sgb_edge_util_map<Tag, typename Tag::type&> 
Chris@16:   get_property_map(Tag, sgb_graph_ptr& g, edge_property_tag) {
Chris@16:     return sgb_edge_util_map<Tag, typename Tag::type&>();
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   // Edge Length Access
Chris@16:   template <class Ref>
Chris@16:   class sgb_edge_length_map
Chris@16:     : public boost::put_get_helper<Ref, sgb_edge_length_map<Ref> >
Chris@16:   {
Chris@16:   public:
Chris@16:     typedef boost::lvalue_property_map_tag category;
Chris@16:     typedef long value_type;
Chris@16:     typedef sgb_edge key_type;
Chris@16:     typedef Ref reference;
Chris@16:     reference operator[](const sgb_edge& e) const { 
Chris@16:       return e._arc->len; 
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   inline sgb_edge_length_map<const long&>
Chris@16:   get(edge_length_t, const sgb_graph_ptr&) { 
Chris@16:     return sgb_edge_length_map<const long&>(); 
Chris@16:   }
Chris@16:   inline sgb_edge_length_map<const long&>
Chris@16:   get(edge_length_t, const sgb_const_graph_ptr&) { 
Chris@16:     return sgb_edge_length_map<const long&>(); 
Chris@16:   }
Chris@16:   inline sgb_edge_length_map<long&>
Chris@16:   get(edge_length_t, sgb_graph_ptr&) { 
Chris@16:     return sgb_edge_length_map<long&>(); 
Chris@16:   }
Chris@16:   inline long
Chris@16:   get(edge_length_t, const sgb_graph_ptr&, const sgb_edge& key) {
Chris@16:     return key._arc->len;
Chris@16:   }
Chris@16:   inline long
Chris@16:   get(edge_length_t, const sgb_const_graph_ptr&, const sgb_edge& key) {
Chris@16:     return key._arc->len;
Chris@16:   }
Chris@16:   inline void
Chris@16:   put(edge_length_t, sgb_graph_ptr&, const sgb_edge& key, long value)
Chris@16:   {
Chris@16:     key._arc->len = value;
Chris@16:   }
Chris@16: 
Chris@16:   // Property Map Traits Classes
Chris@16:   template <>
Chris@16:   struct property_map<sgb_graph_ptr, edge_length_t> {
Chris@16:     typedef sgb_edge_length_map<long&> type;
Chris@16:     typedef sgb_edge_length_map<const long&> const_type;
Chris@16:   };
Chris@16:   template <>
Chris@16:   struct property_map<sgb_graph_ptr, vertex_index_t> {
Chris@16:     typedef sgb_vertex_id_map type;
Chris@16:     typedef sgb_vertex_id_map const_type;
Chris@16:   };
Chris@16:   template <>
Chris@16:   struct property_map<sgb_graph_ptr, vertex_name_t> {
Chris@16:     typedef sgb_vertex_name_map type;
Chris@16:     typedef sgb_vertex_name_map const_type;
Chris@16:   };
Chris@16: 
Chris@16:   template <>
Chris@16:   struct property_map<sgb_const_graph_ptr, edge_length_t> {
Chris@16:     typedef sgb_edge_length_map<const long&> const_type;
Chris@16:   };
Chris@16:   template <>
Chris@16:   struct property_map<sgb_const_graph_ptr, vertex_index_t> {
Chris@16:     typedef sgb_vertex_id_map const_type;
Chris@16:   };
Chris@16:   template <>
Chris@16:   struct property_map<sgb_const_graph_ptr, vertex_name_t> {
Chris@16:     typedef sgb_vertex_name_map const_type;
Chris@16:   };
Chris@16: 
Chris@16: 
Chris@16:   namespace detail {
Chris@16:     template <class Kind, class PropertyTag>
Chris@16:     struct sgb_choose_property_map { };
Chris@16:     template <class PropertyTag>
Chris@16:     struct sgb_choose_property_map<vertex_property_tag, PropertyTag> {
Chris@16:       typedef typename PropertyTag::type value_type;
Chris@16:       typedef sgb_vertex_util_map<PropertyTag, value_type&> type;
Chris@16:       typedef sgb_vertex_util_map<PropertyTag, const value_type&> const_type;
Chris@16:     };
Chris@16:     template <class PropertyTag>
Chris@16:     struct sgb_choose_property_map<edge_property_tag, PropertyTag> {
Chris@16:       typedef typename PropertyTag::type value_type;
Chris@16:       typedef sgb_edge_util_map<PropertyTag, value_type&> type;
Chris@16:       typedef sgb_edge_util_map<PropertyTag, const value_type&> const_type;
Chris@16:     };
Chris@16:   } // namespace detail
Chris@16:   template <class PropertyTag>
Chris@16:   struct property_map<sgb_graph_ptr, PropertyTag> {
Chris@16:     typedef typename property_kind<PropertyTag>::type Kind;
Chris@16:     typedef detail::sgb_choose_property_map<Kind, PropertyTag> Choice;
Chris@16:     typedef typename Choice::type type;
Chris@16:     typedef typename Choice::const_type const_type;
Chris@16:   };
Chris@16:   template <class PropertyTag>
Chris@16:   struct property_map<sgb_const_graph_ptr, PropertyTag> {
Chris@16:     typedef typename property_kind<PropertyTag>::type Kind;
Chris@16:     typedef detail::sgb_choose_property_map<Kind, PropertyTag> Choice;
Chris@16:     typedef typename Choice::const_type const_type;
Chris@16:   };
Chris@16: 
Chris@16: #define SGB_UTIL_ACCESSOR(KIND,X) \
Chris@16:   template <class T> \
Chris@16:   inline sgb_##KIND##_util_map< X##_property<T>, T&> \
Chris@16:   get(X##_property<T>, sgb_graph_ptr&) { \
Chris@16:     return sgb_##KIND##_util_map< X##_property<T>, T&>(); \
Chris@16:   } \
Chris@16:   template <class T> \
Chris@16:   inline sgb_##KIND##_util_map< X##_property<T>, const T&> \
Chris@16:   get(X##_property<T>, const sgb_graph_ptr&) { \
Chris@16:     return sgb_##KIND##_util_map< X##_property<T>, const T&>(); \
Chris@16:   } \
Chris@16:   template <class T> \
Chris@16:   inline sgb_##KIND##_util_map< X##_property<T>, const T&> \
Chris@16:   get(X##_property<T>, const sgb_const_graph_ptr&) { \
Chris@16:     return sgb_##KIND##_util_map< X##_property<T>, const T&>(); \
Chris@16:   } \
Chris@16:   template <class T, class Key> \
Chris@16:   inline typename \
Chris@16:   sgb_##KIND##_util_map< X##_property<T>, const T&>::value_type \
Chris@16:   get(X##_property<T>, const sgb_graph_ptr&, const Key& key) { \
Chris@16:     return sgb_##KIND##_util_map< X##_property<T>, const T&>()[key]; \
Chris@16:   } \
Chris@16:   template <class T, class Key> \
Chris@16:   inline typename \
Chris@16:   sgb_##KIND##_util_map< X##_property<T>, const T&>::value_type \
Chris@16:   get(X##_property<T>, const sgb_const_graph_ptr&, const Key& key) { \
Chris@16:     return sgb_##KIND##_util_map< X##_property<T>, const T&>()[key]; \
Chris@16:   } \
Chris@16:   template <class T, class Key, class Value> \
Chris@16:   inline  void \
Chris@16:   put(X##_property<T>, sgb_graph_ptr&, const Key& key, const Value& value) { \
Chris@16:     sgb_##KIND##_util_map< X##_property<T>, T&>()[key] = value; \
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   SGB_UTIL_ACCESSOR(vertex, u)
Chris@16:   SGB_UTIL_ACCESSOR(vertex, v)
Chris@16:   SGB_UTIL_ACCESSOR(vertex, w)
Chris@16:   SGB_UTIL_ACCESSOR(vertex, x)
Chris@16:   SGB_UTIL_ACCESSOR(vertex, y)
Chris@16:   SGB_UTIL_ACCESSOR(vertex, z)
Chris@16: 
Chris@16:   SGB_UTIL_ACCESSOR(edge, a)
Chris@16:   SGB_UTIL_ACCESSOR(edge, b)
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_SGB_GRAPH_HPP