ceph/src/boost/boost/graph/stanford_graph.hpp

   1 //=======================================================================
   2 // Copyright 1997-2001 University of Notre Dame.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9 #ifndef BOOST_GRAPH_SGB_GRAPH_HPP
  10 #define BOOST_GRAPH_SGB_GRAPH_HPP
  11
  12 #include <boost/config.hpp>
  13 #include <boost/iterator.hpp>
  14 #include <boost/operators.hpp>
  15 #include <boost/property_map/property_map.hpp>
  16 #include <boost/graph/graph_traits.hpp>
  17 #include <boost/graph/properties.hpp>
  18
  19 // Thanks to Andreas Scherer for numerous suggestions and fixes!
  20
  21 // This file adapts a Stanford GraphBase (SGB) Graph pointer into a
  22 // VertexListGraph. Note that a graph adaptor class is not needed,
  23 // SGB's Graph* is used as is. The VertexListGraph concept is fulfilled by
  24 // defining the appropriate non-member functions for Graph*.
  25 //
  26 // The PROTOTYPES change file extensions to SGB must be applied so
  27 // that the SGB functions have real prototypes which are necessary for
  28 // the C++ compiler. To apply the PROTOTYPES extensions, before you do
  29 // "make tests install" for SGB do "ln -s PROTOTYPES/* ." to the SGB
  30 // root directory (or just copy all the files from the PROTOTYPES
  31 // directory to the SGB root directory).
  32 //
  33 extern "C" {
  34         // We include all global definitions for the general stuff
  35         // of The Stanford GraphBase and its various graph generator
  36         // functions by reading all SGB headerfiles as in section 2 of
  37         // the "test_sample" program.
  38 #include <gb_graph.h> /* SGB data structures */
  39 #include <gb_io.h> /* SGB input/output routines */
  40 #include <gb_flip.h> /* random number generator */
  41 #include <gb_dijk.h> /* routines for shortest paths */
  42 #include <gb_basic.h> /* the basic graph operations */
  43 #undef empty /* avoid name clash with C++ standard library */
  44         inline Graph* empty( long n ) /* and provide workaround */
  45         { return board(n,0L,0L,0L,2L,0L,0L); }
  46 #include <gb_books.h> /* graphs based on literature */
  47 #include <gb_econ.h> /* graphs based on economic data */
  48 #include <gb_games.h> /* graphs based on football scores */
  49 #include <gb_gates.h> /* graphs based on logic circuits */
  50 #undef val /* avoid name clash with g++ headerfile stl_tempbuf.h */
  51         // val ==> Vertex::x.I
  52 #include <gb_lisa.h> /* graphs based on Mona Lisa */
  53 #include <gb_miles.h> /* graphs based on mileage data */
  54 #include <gb_plane.h> /* planar graphs */
  55 #include <gb_raman.h> /* Ramanujan graphs */
  56 #include <gb_rand.h> /* random graphs */
  57 #include <gb_roget.h> /* graphs based on Roget's Thesaurus */
  58 #include <gb_save.h> /* we save results in ASCII format */
  59 #include <gb_words.h> /* five-letter-word graphs */
  60 #undef weight /* avoid name clash with BGL parameter */
  61         // weight ==> Vertex::u.I
  62 }
  63
  64 namespace boost {
  65   class sgb_edge;
  66 }
  67
  68 class sgb_out_edge_iterator;
  69 class sgb_adj_iterator;
  70 class sgb_vertex_iterator;
  71
  72 namespace boost {
  73   typedef Graph* sgb_graph_ptr;
  74   typedef const Graph* sgb_const_graph_ptr;
  75
  76   struct sgb_traversal_tag :
  77     public virtual vertex_list_graph_tag,
  78     public virtual incidence_graph_tag,
  79     public virtual adjacency_graph_tag { };
  80
  81   template <> struct graph_traits<sgb_graph_ptr> {
  82     typedef Vertex* vertex_descriptor;
  83     typedef boost::sgb_edge edge_descriptor;
  84     typedef sgb_out_edge_iterator out_edge_iterator;
  85     typedef void in_edge_iterator;
  86     typedef sgb_adj_iterator adjacency_iterator;
  87     typedef sgb_vertex_iterator vertex_iterator;
  88     typedef void edge_iterator;
  89     typedef long vertices_size_type;
  90     typedef long edge_size_type;
  91     typedef long degree_size_type;
  92     typedef directed_tag directed_category;
  93     typedef sgb_traversal_tag traversal_category;
  94     typedef allow_parallel_edge_tag edge_parallel_category;
  95   };
  96   template <> struct graph_traits<sgb_const_graph_ptr> {
  97     typedef Vertex* vertex_descriptor;
  98     typedef boost::sgb_edge edge_descriptor;
  99     typedef sgb_out_edge_iterator out_edge_iterator;
 100     typedef void in_edge_iterator;
 101     typedef sgb_adj_iterator adjacency_iterator;
 102     typedef sgb_vertex_iterator vertex_iterator;
 103     typedef void edge_iterator;
 104     typedef long vertices_size_type;
 105     typedef long edge_size_type;
 106     typedef long degree_size_type;
 107     typedef directed_tag directed_category;
 108     typedef sgb_traversal_tag traversal_category;
 109     typedef allow_parallel_edge_tag edge_parallel_category;
 110   };
 111 }
 112
 113 namespace boost {
 114
 115   struct edge_length_t {
 116     typedef edge_property_tag kind;
 117   };
 118
 119   // We could just use Arc* as the edge descriptor type, but
 120   // we want to add the source(e,g) function which requires
 121   // that we carry along a pointer to the source vertex.
 122   class sgb_edge {
 123     typedef sgb_edge self;
 124   public:
 125     sgb_edge() : _arc(0), _src(0) { }
 126     sgb_edge(Arc* a, Vertex* s) : _arc(a), _src(s) { }
 127     friend Vertex* source(self e, sgb_const_graph_ptr) { return e._src; }
 128     friend Vertex* target(self e, sgb_const_graph_ptr) { return e._arc->tip; }
 129     friend bool operator==(const self& a, const self& b) {
 130       return a._arc == b._arc; }
 131     friend bool operator!=(const self& a, const self& b) {
 132       return a._arc != b._arc; }
 133 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
 134     template <class Ref> friend class sgb_edge_length_map;
 135     template <class Tag, class Ref> friend class sgb_edge_util_map;
 136     friend long get(edge_length_t, const sgb_graph_ptr&, const sgb_edge& key);
 137     friend long get(edge_length_t, const sgb_const_graph_ptr&, const sgb_edge& key);
 138     friend void put(edge_length_t, sgb_graph_ptr&, const sgb_edge& key, long value);
 139   protected:
 140 #endif
 141     Arc* _arc;
 142     Vertex* _src;
 143   };
 144 } // namespace boost
 145
 146   class sgb_out_edge_iterator
 147     : public boost::forward_iterator_helper<
 148         sgb_out_edge_iterator, boost::sgb_edge,
 149         std::ptrdiff_t, boost::sgb_edge*, boost::sgb_edge>
 150   {
 151     typedef sgb_out_edge_iterator self;
 152   public:
 153     sgb_out_edge_iterator() : _src(0), _arc(0) {}
 154     sgb_out_edge_iterator(Vertex* s, Arc* d) : _src(s), _arc(d) {}
 155     boost::sgb_edge operator*() { return boost::sgb_edge(_arc, _src); }
 156     self& operator++() { _arc = _arc->next; return *this; }
 157     friend bool operator==(const self& x, const self& y) {
 158       return x._arc == y._arc; }
 159   protected:
 160     Vertex* _src;
 161     Arc* _arc;
 162   };
 163
 164   class sgb_adj_iterator
 165     : public boost::forward_iterator_helper<
 166         sgb_adj_iterator, Vertex*, std::ptrdiff_t, Vertex**,Vertex*>
 167   {
 168     typedef sgb_adj_iterator self;
 169   public:
 170     sgb_adj_iterator() : _arc(0) {}
 171     sgb_adj_iterator(Arc* d) : _arc(d) {}
 172     Vertex* operator*() { return _arc->tip; }
 173     self& operator++() { _arc = _arc->next; return *this; }
 174     friend bool operator==(const self& x, const self& y) {
 175       return x._arc == y._arc; }
 176   protected:
 177     Arc* _arc;
 178   };
 179
 180   // The reason we have this instead of just using Vertex* is that we
 181   // want to use Vertex* as the vertex_descriptor instead of just
 182   // Vertex, which avoids problems with boost passing vertex descriptors
 183   // by value and how that interacts with the sgb_vertex_id_map.
 184   class sgb_vertex_iterator
 185     : public boost::forward_iterator_helper<
 186         sgb_vertex_iterator, Vertex*, std::ptrdiff_t, Vertex**, Vertex*>
 187   {
 188     typedef sgb_vertex_iterator self;
 189   public:
 190     sgb_vertex_iterator() : _v(0) { }
 191     sgb_vertex_iterator(Vertex* v) : _v(v) { }
 192     Vertex* operator*() { return _v; }
 193     self& operator++() { ++_v; return *this; }
 194     friend bool operator==(const self& x, const self& y) {
 195       return x._v == y._v; }
 196   protected:
 197     Vertex* _v;
 198   };
 199
 200 namespace boost {
 201
 202   inline std::pair<sgb_vertex_iterator,sgb_vertex_iterator>
 203   vertices(sgb_const_graph_ptr g)
 204   {
 205     return std::make_pair(sgb_vertex_iterator(g->vertices),
 206                           sgb_vertex_iterator(g->vertices + g->n));
 207   }
 208
 209   inline std::pair<sgb_out_edge_iterator,sgb_out_edge_iterator>
 210   out_edges(Vertex* u, sgb_const_graph_ptr)
 211   {
 212     return std::make_pair( sgb_out_edge_iterator(u, u->arcs),
 213                            sgb_out_edge_iterator(u, 0) );
 214   }
 215
 216   inline boost::graph_traits<sgb_graph_ptr>::degree_size_type
 217   out_degree(Vertex* u, sgb_const_graph_ptr g)
 218   {
 219     boost::graph_traits<sgb_graph_ptr>::out_edge_iterator i, i_end;
 220     boost::tie(i, i_end) = out_edges(u, g);
 221     return std::distance(i, i_end);
 222   }
 223
 224   // in_edges?
 225
 226   inline std::pair<sgb_adj_iterator,sgb_adj_iterator>
 227   adjacent_vertices(Vertex* u, sgb_const_graph_ptr)
 228   {
 229     return std::make_pair( sgb_adj_iterator(u->arcs),
 230                            sgb_adj_iterator(0) );
 231   }
 232
 233   inline long num_vertices(sgb_const_graph_ptr g) { return g->n; }
 234   inline long num_edges(sgb_const_graph_ptr g) { return g->m; }
 235
 236   inline Vertex* vertex(long v, sgb_const_graph_ptr g)
 237     { return g->vertices + v; }
 238
 239   // Various Property Maps
 240
 241   // Vertex ID
 242   class sgb_vertex_id_map
 243     : public boost::put_get_helper<long, sgb_vertex_id_map>
 244   {
 245   public:
 246     typedef boost::readable_property_map_tag category;
 247     typedef long value_type;
 248     typedef long reference;
 249     typedef Vertex* key_type;
 250     sgb_vertex_id_map() : _g(0) { }
 251     sgb_vertex_id_map(sgb_graph_ptr g) : _g(g) { }
 252     long operator[](Vertex* v) const { return v - _g->vertices; }
 253   protected:
 254     sgb_graph_ptr _g;
 255   };
 256   inline sgb_vertex_id_map get(vertex_index_t, sgb_graph_ptr g) {
 257     return sgb_vertex_id_map(g);
 258   }
 259
 260   // Vertex Name
 261   class sgb_vertex_name_map
 262     : public boost::put_get_helper<char*, sgb_vertex_name_map>
 263   {
 264   public:
 265     typedef boost::readable_property_map_tag category;
 266     typedef char* value_type;
 267     typedef char* reference;
 268     typedef Vertex* key_type;
 269     char* operator[](Vertex* v) const { return v->name; }
 270   };
 271   inline sgb_vertex_name_map get(vertex_name_t, sgb_graph_ptr) {
 272     return sgb_vertex_name_map();
 273   }
 274
 275   // Vertex Property Tags
 276 #define SGB_PROPERTY_TAG(KIND,TAG) \
 277   template <class T> struct TAG##_property { \
 278     typedef KIND##_property_tag kind; \
 279     typedef T type; \
 280   };
 281   SGB_PROPERTY_TAG(vertex, u)
 282   SGB_PROPERTY_TAG(vertex, v)
 283   SGB_PROPERTY_TAG(vertex, w)
 284   SGB_PROPERTY_TAG(vertex, x)
 285   SGB_PROPERTY_TAG(vertex, y)
 286   SGB_PROPERTY_TAG(vertex, z)
 287
 288   // Edge Property Tags
 289   SGB_PROPERTY_TAG(edge, a)
 290   SGB_PROPERTY_TAG(edge, b)
 291
 292   // Various Utility Maps
 293
 294   // helpers
 295   inline Vertex*& get_util(util& u, Vertex*) { return u.V; }
 296   inline Arc*& get_util(util& u, Arc*) { return u.A; }
 297   inline sgb_graph_ptr& get_util(util& u, sgb_graph_ptr) { return u.G; }
 298   inline char*& get_util(util& u, char*) { return u.S; }
 299   inline long& get_util(util& u, long) { return u.I; }
 300
 301 #define SGB_GET_UTIL_FIELD(KIND,X) \
 302   template <class T> \
 303   inline T& get_util_field(KIND* k, X##_property<T>) { \
 304     return get_util(k->X, T());  }
 305
 306   SGB_GET_UTIL_FIELD(Vertex, u)
 307   SGB_GET_UTIL_FIELD(Vertex, v)
 308   SGB_GET_UTIL_FIELD(Vertex, w)
 309   SGB_GET_UTIL_FIELD(Vertex, x)
 310   SGB_GET_UTIL_FIELD(Vertex, y)
 311   SGB_GET_UTIL_FIELD(Vertex, z)
 312
 313   SGB_GET_UTIL_FIELD(Arc, a)
 314   SGB_GET_UTIL_FIELD(Arc, b)
 315
 316   // Vertex Utility Map
 317   template <class Tag, class Ref>
 318   class sgb_vertex_util_map
 319     : public boost::put_get_helper<Ref, sgb_vertex_util_map<Tag, Ref> >
 320   {
 321     Tag tag;
 322   public:
 323     explicit sgb_vertex_util_map(Tag tag = Tag()): tag(tag) {}
 324     typedef boost::lvalue_property_map_tag category;
 325     typedef typename Tag::type value_type;
 326     typedef Vertex* key_type;
 327     typedef Ref reference;
 328     reference operator[](Vertex* v) const {
 329       return get_util_field(v, tag);
 330     }
 331   };
 332
 333   // Edge Utility Map
 334   template <class Tag, class Ref>
 335   class sgb_edge_util_map
 336     : public boost::put_get_helper<Ref, sgb_edge_util_map<Tag, Ref> >
 337   {
 338     Tag tag;
 339   public:
 340     explicit sgb_edge_util_map(Tag tag = Tag()): tag(tag) {}
 341     typedef boost::lvalue_property_map_tag category;
 342     typedef typename Tag::type value_type;
 343     typedef Vertex* key_type;
 344     typedef Ref reference;
 345     reference operator[](const sgb_edge& e) const {
 346       return get_util_field(e._arc, tag);
 347     }
 348   };
 349
 350
 351   template <class Tag>
 352   inline sgb_vertex_util_map<Tag, const typename Tag::type&>
 353   get_property_map(Tag, const sgb_graph_ptr& g, vertex_property_tag) {
 354     return sgb_vertex_util_map<Tag, const typename Tag::type&>();
 355   }
 356   template <class Tag>
 357   inline sgb_vertex_util_map<Tag, typename Tag::type&>
 358   get_property_map(Tag, sgb_graph_ptr& g, vertex_property_tag) {
 359     return sgb_vertex_util_map<Tag, typename Tag::type&>();
 360   }
 361
 362   template <class Tag>
 363   inline sgb_edge_util_map<Tag, const typename Tag::type&>
 364   get_property_map(Tag, const sgb_graph_ptr& g, edge_property_tag) {
 365     return sgb_edge_util_map<Tag, const typename Tag::type&>();
 366   }
 367   template <class Tag>
 368   inline sgb_edge_util_map<Tag, typename Tag::type&>
 369   get_property_map(Tag, sgb_graph_ptr& g, edge_property_tag) {
 370     return sgb_edge_util_map<Tag, typename Tag::type&>();
 371   }
 372
 373
 374   // Edge Length Access
 375   template <class Ref>
 376   class sgb_edge_length_map
 377     : public boost::put_get_helper<Ref, sgb_edge_length_map<Ref> >
 378   {
 379   public:
 380     typedef boost::lvalue_property_map_tag category;
 381     typedef long value_type;
 382     typedef sgb_edge key_type;
 383     typedef Ref reference;
 384     reference operator[](const sgb_edge& e) const {
 385       return e._arc->len;
 386     }
 387   };
 388
 389   inline sgb_edge_length_map<const long&>
 390   get(edge_length_t, const sgb_graph_ptr&) {
 391     return sgb_edge_length_map<const long&>();
 392   }
 393   inline sgb_edge_length_map<const long&>
 394   get(edge_length_t, const sgb_const_graph_ptr&) {
 395     return sgb_edge_length_map<const long&>();
 396   }
 397   inline sgb_edge_length_map<long&>
 398   get(edge_length_t, sgb_graph_ptr&) {
 399     return sgb_edge_length_map<long&>();
 400   }
 401   inline long
 402   get(edge_length_t, const sgb_graph_ptr&, const sgb_edge& key) {
 403     return key._arc->len;
 404   }
 405   inline long
 406   get(edge_length_t, const sgb_const_graph_ptr&, const sgb_edge& key) {
 407     return key._arc->len;
 408   }
 409   inline void
 410   put(edge_length_t, sgb_graph_ptr&, const sgb_edge& key, long value)
 411   {
 412     key._arc->len = value;
 413   }
 414
 415   // Property Map Traits Classes
 416   template <>
 417   struct property_map<sgb_graph_ptr, edge_length_t> {
 418     typedef sgb_edge_length_map<long&> type;
 419     typedef sgb_edge_length_map<const long&> const_type;
 420   };
 421   template <>
 422   struct property_map<sgb_graph_ptr, vertex_index_t> {
 423     typedef sgb_vertex_id_map type;
 424     typedef sgb_vertex_id_map const_type;
 425   };
 426   template <>
 427   struct property_map<sgb_graph_ptr, vertex_name_t> {
 428     typedef sgb_vertex_name_map type;
 429     typedef sgb_vertex_name_map const_type;
 430   };
 431
 432   template <>
 433   struct property_map<sgb_const_graph_ptr, edge_length_t> {
 434     typedef sgb_edge_length_map<const long&> const_type;
 435   };
 436   template <>
 437   struct property_map<sgb_const_graph_ptr, vertex_index_t> {
 438     typedef sgb_vertex_id_map const_type;
 439   };
 440   template <>
 441   struct property_map<sgb_const_graph_ptr, vertex_name_t> {
 442     typedef sgb_vertex_name_map const_type;
 443   };
 444
 445
 446   namespace detail {
 447     template <class Kind, class PropertyTag>
 448     struct sgb_choose_property_map { };
 449     template <class PropertyTag>
 450     struct sgb_choose_property_map<vertex_property_tag, PropertyTag> {
 451       typedef typename PropertyTag::type value_type;
 452       typedef sgb_vertex_util_map<PropertyTag, value_type&> type;
 453       typedef sgb_vertex_util_map<PropertyTag, const value_type&> const_type;
 454     };
 455     template <class PropertyTag>
 456     struct sgb_choose_property_map<edge_property_tag, PropertyTag> {
 457       typedef typename PropertyTag::type value_type;
 458       typedef sgb_edge_util_map<PropertyTag, value_type&> type;
 459       typedef sgb_edge_util_map<PropertyTag, const value_type&> const_type;
 460     };
 461   } // namespace detail
 462   template <class PropertyTag>
 463   struct property_map<sgb_graph_ptr, PropertyTag> {
 464     typedef typename property_kind<PropertyTag>::type Kind;
 465     typedef detail::sgb_choose_property_map<Kind, PropertyTag> Choice;
 466     typedef typename Choice::type type;
 467     typedef typename Choice::const_type const_type;
 468   };
 469   template <class PropertyTag>
 470   struct property_map<sgb_const_graph_ptr, PropertyTag> {
 471     typedef typename property_kind<PropertyTag>::type Kind;
 472     typedef detail::sgb_choose_property_map<Kind, PropertyTag> Choice;
 473     typedef typename Choice::const_type const_type;
 474   };
 475
 476 #define SGB_UTIL_ACCESSOR(KIND,X) \
 477   template <class T> \
 478   inline sgb_##KIND##_util_map< X##_property<T>, T&> \
 479   get(X##_property<T>, sgb_graph_ptr&) { \
 480     return sgb_##KIND##_util_map< X##_property<T>, T&>(); \
 481   } \
 482   template <class T> \
 483   inline sgb_##KIND##_util_map< X##_property<T>, const T&> \
 484   get(X##_property<T>, const sgb_graph_ptr&) { \
 485     return sgb_##KIND##_util_map< X##_property<T>, const T&>(); \
 486   } \
 487   template <class T> \
 488   inline sgb_##KIND##_util_map< X##_property<T>, const T&> \
 489   get(X##_property<T>, const sgb_const_graph_ptr&) { \
 490     return sgb_##KIND##_util_map< X##_property<T>, const T&>(); \
 491   } \
 492   template <class T, class Key> \
 493   inline typename \
 494   sgb_##KIND##_util_map< X##_property<T>, const T&>::value_type \
 495   get(X##_property<T>, const sgb_graph_ptr&, const Key& key) { \
 496     return sgb_##KIND##_util_map< X##_property<T>, const T&>()[key]; \
 497   } \
 498   template <class T, class Key> \
 499   inline typename \
 500   sgb_##KIND##_util_map< X##_property<T>, const T&>::value_type \
 501   get(X##_property<T>, const sgb_const_graph_ptr&, const Key& key) { \
 502     return sgb_##KIND##_util_map< X##_property<T>, const T&>()[key]; \
 503   } \
 504   template <class T, class Key, class Value> \
 505   inline  void \
 506   put(X##_property<T>, sgb_graph_ptr&, const Key& key, const Value& value) { \
 507     sgb_##KIND##_util_map< X##_property<T>, T&>()[key] = value; \
 508   }
 509
 510
 511   SGB_UTIL_ACCESSOR(vertex, u)
 512   SGB_UTIL_ACCESSOR(vertex, v)
 513   SGB_UTIL_ACCESSOR(vertex, w)
 514   SGB_UTIL_ACCESSOR(vertex, x)
 515   SGB_UTIL_ACCESSOR(vertex, y)
 516   SGB_UTIL_ACCESSOR(vertex, z)
 517
 518   SGB_UTIL_ACCESSOR(edge, a)
 519   SGB_UTIL_ACCESSOR(edge, b)
 520
 521 } // namespace boost
 522
 523 #endif // BOOST_GRAPH_SGB_GRAPH_HPP