boost/graph/stanford_graph.hpp

0001 //=======================================================================
0002 // Copyright 1997-2001 University of Notre Dame.
0003 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009 #ifndef BOOST_GRAPH_SGB_GRAPH_HPP
0010 #define BOOST_GRAPH_SGB_GRAPH_HPP
0011
0012 #include <boost/config.hpp>
0013 #include <boost/operators.hpp>
0014 #include <boost/property_map/property_map.hpp>
0015 #include <boost/graph/graph_traits.hpp>
0016 #include <boost/graph/properties.hpp>
0017
0018 // Thanks to Andreas Scherer for numerous suggestions and fixes!
0019
0020 // This file adapts a Stanford GraphBase (SGB) Graph pointer into a
0021 // VertexListGraph. Note that a graph adaptor class is not needed,
0022 // SGB's Graph* is used as is. The VertexListGraph concept is fulfilled by
0023 // defining the appropriate non-member functions for Graph*.
0024 //
0025 // The PROTOTYPES change file extensions to SGB must be applied so
0026 // that the SGB functions have real prototypes which are necessary for
0027 // the C++ compiler. To apply the PROTOTYPES extensions, before you do
0028 // "make tests install" for SGB do "ln -s PROTOTYPES/* ." to the SGB
0029 // root directory (or just copy all the files from the PROTOTYPES
0030 // directory to the SGB root directory).
0031 //
0032 extern "C"
0033 {
0034     // We include all global definitions for the general stuff
0035     // of The Stanford GraphBase and its various graph generator
0036     // functions by reading all SGB headerfiles as in section 2 of
0037     // the "test_sample" program.
0038 #include <gb_graph.h> /* SGB data structures */
0039 #include <gb_io.h> /* SGB input/output routines */
0040 #include <gb_flip.h> /* random number generator */
0041 #include <gb_dijk.h> /* routines for shortest paths */
0042 #include <gb_basic.h> /* the basic graph operations */
0043 #undef empty /* avoid name clash with C++ standard library */
0044     inline Graph* empty(long n) /* and provide workaround */
0045     {
0046         return board(n, 0L, 0L, 0L, 2L, 0L, 0L);
0047     }
0048 #include <gb_books.h> /* graphs based on literature */
0049 #include <gb_econ.h> /* graphs based on economic data */
0050 #include <gb_games.h> /* graphs based on football scores */
0051 #undef ap /* avoid name clash with BGL parameter */
0052     // ap ==> Vertex::u.I
0053 #include <gb_gates.h> /* graphs based on logic circuits */
0054 #undef val /* avoid name clash with g++ headerfile stl_tempbuf.h */
0055     // val ==> Vertex::x.I
0056 #include <gb_lisa.h> /* graphs based on Mona Lisa */
0057 #include <gb_miles.h> /* graphs based on mileage data */
0058 #include <gb_plane.h> /* planar graphs */
0059 #include <gb_raman.h> /* Ramanujan graphs */
0060 #include <gb_rand.h> /* random graphs */
0061 #include <gb_roget.h> /* graphs based on Roget's Thesaurus */
0062 #include <gb_save.h> /* we save results in ASCII format */
0063 #include <gb_words.h> /* five-letter-word graphs */
0064 #undef weight /* avoid name clash with BGL parameter */
0065     // weight ==> Vertex::u.I
0066 }
0067
0068 namespace boost
0069 {
0070 class sgb_edge;
0071 }
0072
0073 class sgb_out_edge_iterator;
0074 class sgb_adj_iterator;
0075 class sgb_vertex_iterator;
0076
0077 namespace boost
0078 {
0079 typedef Graph* sgb_graph_ptr;
0080 typedef const Graph* sgb_const_graph_ptr;
0081
0082 struct sgb_traversal_tag : public virtual vertex_list_graph_tag,
0083                            public virtual incidence_graph_tag,
0084                            public virtual adjacency_graph_tag
0085 {
0086 };
0087
0088 template <> struct graph_traits< sgb_graph_ptr >
0089 {
0090     typedef Vertex* vertex_descriptor;
0091     typedef boost::sgb_edge edge_descriptor;
0092     typedef sgb_out_edge_iterator out_edge_iterator;
0093     typedef void in_edge_iterator;
0094     typedef sgb_adj_iterator adjacency_iterator;
0095     typedef sgb_vertex_iterator vertex_iterator;
0096     typedef void edge_iterator;
0097     typedef long vertices_size_type;
0098     typedef long edge_size_type;
0099     typedef long degree_size_type;
0100     typedef directed_tag directed_category;
0101     typedef sgb_traversal_tag traversal_category;
0102     typedef allow_parallel_edge_tag edge_parallel_category;
0103     /** Return a null descriptor */
0104     static vertex_descriptor null_vertex() { return NULL; }
0105 };
0106 template <> struct graph_traits< sgb_const_graph_ptr >
0107 {
0108     typedef Vertex* vertex_descriptor;
0109     typedef boost::sgb_edge edge_descriptor;
0110     typedef sgb_out_edge_iterator out_edge_iterator;
0111     typedef void in_edge_iterator;
0112     typedef sgb_adj_iterator adjacency_iterator;
0113     typedef sgb_vertex_iterator vertex_iterator;
0114     typedef void edge_iterator;
0115     typedef long vertices_size_type;
0116     typedef long edge_size_type;
0117     typedef long degree_size_type;
0118     typedef directed_tag directed_category;
0119     typedef sgb_traversal_tag traversal_category;
0120     typedef allow_parallel_edge_tag edge_parallel_category;
0121     /** Return a null descriptor */
0122     static vertex_descriptor null_vertex() { return NULL; }
0123 };
0124 }
0125
0126 namespace boost
0127 {
0128
0129 struct edge_length_t
0130 {
0131     typedef edge_property_tag kind;
0132 };
0133
0134 // We could just use Arc* as the edge descriptor type, but
0135 // we want to add the source(e,g) function which requires
0136 // that we carry along a pointer to the source vertex.
0137 class sgb_edge
0138 {
0139     typedef sgb_edge self;
0140
0141 public:
0142     sgb_edge() : _arc(0), _src(0) {}
0143     sgb_edge(Arc* a, Vertex* s) : _arc(a), _src(s) {}
0144     friend Vertex* source(self e, sgb_const_graph_ptr) { return e._src; }
0145     friend Vertex* target(self e, sgb_const_graph_ptr) { return e._arc->tip; }
0146     friend bool operator==(const self& a, const self& b)
0147     {
0148         return a._arc == b._arc;
0149     }
0150     friend bool operator!=(const self& a, const self& b)
0151     {
0152         return a._arc != b._arc;
0153     }
0154 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
0155     template < class Ref > friend class sgb_edge_length_map;
0156     template < class Tag, class Ref > friend class sgb_edge_util_map;
0157     friend long get(edge_length_t, const sgb_graph_ptr&, const sgb_edge& key);
0158     friend long get(
0159         edge_length_t, const sgb_const_graph_ptr&, const sgb_edge& key);
0160     friend void put(
0161         edge_length_t, sgb_graph_ptr&, const sgb_edge& key, long value);
0162
0163 protected:
0164 #endif
0165     Arc* _arc;
0166     Vertex* _src;
0167 };
0168 } // namespace boost
0169
0170 class sgb_out_edge_iterator
0171 : public boost::forward_iterator_helper< sgb_out_edge_iterator, boost::sgb_edge,
0172       std::ptrdiff_t, boost::sgb_edge*, boost::sgb_edge >
0173 {
0174     typedef sgb_out_edge_iterator self;
0175
0176 public:
0177     sgb_out_edge_iterator() : _src(0), _arc(0) {}
0178     sgb_out_edge_iterator(Vertex* s, Arc* d) : _src(s), _arc(d) {}
0179     boost::sgb_edge operator*() { return boost::sgb_edge(_arc, _src); }
0180     self& operator++()
0181     {
0182         _arc = _arc->next;
0183         return *this;
0184     }
0185     friend bool operator==(const self& x, const self& y)
0186     {
0187         return x._arc == y._arc;
0188     }
0189
0190 protected:
0191     Vertex* _src;
0192     Arc* _arc;
0193 };
0194
0195 class sgb_adj_iterator
0196 : public boost::forward_iterator_helper< sgb_adj_iterator, Vertex*,
0197       std::ptrdiff_t, Vertex**, Vertex* >
0198 {
0199     typedef sgb_adj_iterator self;
0200
0201 public:
0202     sgb_adj_iterator() : _arc(0) {}
0203     sgb_adj_iterator(Arc* d) : _arc(d) {}
0204     Vertex* operator*() { return _arc->tip; }
0205     self& operator++()
0206     {
0207         _arc = _arc->next;
0208         return *this;
0209     }
0210     friend bool operator==(const self& x, const self& y)
0211     {
0212         return x._arc == y._arc;
0213     }
0214
0215 protected:
0216     Arc* _arc;
0217 };
0218
0219 // The reason we have this instead of just using Vertex* is that we
0220 // want to use Vertex* as the vertex_descriptor instead of just
0221 // Vertex, which avoids problems with boost passing vertex descriptors
0222 // by value and how that interacts with the sgb_vertex_id_map.
0223 class sgb_vertex_iterator
0224 : public boost::forward_iterator_helper< sgb_vertex_iterator, Vertex*,
0225       std::ptrdiff_t, Vertex**, Vertex* >
0226 {
0227     typedef sgb_vertex_iterator self;
0228
0229 public:
0230     sgb_vertex_iterator() : _v(0) {}
0231     sgb_vertex_iterator(Vertex* v) : _v(v) {}
0232     Vertex* operator*() { return _v; }
0233     self& operator++()
0234     {
0235         ++_v;
0236         return *this;
0237     }
0238     friend bool operator==(const self& x, const self& y)
0239     {
0240         return x._v == y._v;
0241     }
0242
0243 protected:
0244     Vertex* _v;
0245 };
0246
0247 namespace boost
0248 {
0249
0250 inline std::pair< sgb_vertex_iterator, sgb_vertex_iterator > vertices(
0251     sgb_const_graph_ptr g)
0252 {
0253     return std::make_pair(sgb_vertex_iterator(g->vertices),
0254         sgb_vertex_iterator(g->vertices + g->n));
0255 }
0256
0257 inline std::pair< sgb_out_edge_iterator, sgb_out_edge_iterator > out_edges(
0258     Vertex* u, sgb_const_graph_ptr)
0259 {
0260     return std::make_pair(
0261         sgb_out_edge_iterator(u, u->arcs), sgb_out_edge_iterator(u, 0));
0262 }
0263
0264 inline boost::graph_traits< sgb_graph_ptr >::degree_size_type out_degree(
0265     Vertex* u, sgb_const_graph_ptr g)
0266 {
0267     boost::graph_traits< sgb_graph_ptr >::out_edge_iterator i, i_end;
0268     boost::tie(i, i_end) = out_edges(u, g);
0269     return std::distance(i, i_end);
0270 }
0271
0272 // in_edges?
0273
0274 inline std::pair< sgb_adj_iterator, sgb_adj_iterator > adjacent_vertices(
0275     Vertex* u, sgb_const_graph_ptr)
0276 {
0277     return std::make_pair(sgb_adj_iterator(u->arcs), sgb_adj_iterator(0));
0278 }
0279
0280 inline long num_vertices(sgb_const_graph_ptr g) { return g->n; }
0281 inline long num_edges(sgb_const_graph_ptr g) { return g->m; }
0282
0283 inline Vertex* vertex(long v, sgb_const_graph_ptr g) { return g->vertices + v; }
0284
0285 // Various Property Maps
0286
0287 // Vertex ID
0288 class sgb_vertex_id_map
0289 : public boost::put_get_helper< long, sgb_vertex_id_map >
0290 {
0291 public:
0292     typedef boost::readable_property_map_tag category;
0293     typedef long value_type;
0294     typedef long reference;
0295     typedef Vertex* key_type;
0296     sgb_vertex_id_map() : _g(0) {}
0297     sgb_vertex_id_map(sgb_graph_ptr g) : _g(g) {}
0298     long operator[](Vertex* v) const { return v - _g->vertices; }
0299
0300 protected:
0301     sgb_graph_ptr _g;
0302 };
0303 inline sgb_vertex_id_map get(vertex_index_t, sgb_graph_ptr g)
0304 {
0305     return sgb_vertex_id_map(g);
0306 }
0307
0308 // Vertex Name
0309 class sgb_vertex_name_map
0310 : public boost::put_get_helper< char*, sgb_vertex_name_map >
0311 {
0312 public:
0313     typedef boost::readable_property_map_tag category;
0314     typedef char* value_type;
0315     typedef char* reference;
0316     typedef Vertex* key_type;
0317     char* operator[](Vertex* v) const { return v->name; }
0318 };
0319 inline sgb_vertex_name_map get(vertex_name_t, sgb_graph_ptr)
0320 {
0321     return sgb_vertex_name_map();
0322 }
0323
0324 // Vertex Property Tags
0325 #define SGB_PROPERTY_TAG(KIND, TAG)            \
0326     template < class T > struct TAG##_property \
0327     {                                          \
0328         typedef KIND##_property_tag kind;      \
0329         typedef T type;                        \
0330     };
0331 SGB_PROPERTY_TAG(vertex, u)
0332 SGB_PROPERTY_TAG(vertex, v)
0333 SGB_PROPERTY_TAG(vertex, w)
0334 SGB_PROPERTY_TAG(vertex, x)
0335 SGB_PROPERTY_TAG(vertex, y)
0336 SGB_PROPERTY_TAG(vertex, z)
0337
0338 // Edge Property Tags
0339 SGB_PROPERTY_TAG(edge, a)
0340 SGB_PROPERTY_TAG(edge, b)
0341
0342 // Various Utility Maps
0343
0344 // helpers
0345 inline Vertex*& get_util(util& u, Vertex*) { return u.V; }
0346 inline Arc*& get_util(util& u, Arc*) { return u.A; }
0347 inline sgb_graph_ptr& get_util(util& u, sgb_graph_ptr) { return u.G; }
0348 inline char*& get_util(util& u, char*) { return u.S; }
0349 inline long& get_util(util& u, long) { return u.I; }
0350
0351 #define SGB_GET_UTIL_FIELD(KIND, X)                                           \
0352     template < class T > inline T& get_util_field(KIND* k, X##_property< T >) \
0353     {                                                                         \
0354         return get_util(k->X, T());                                           \
0355     }
0356
0357 SGB_GET_UTIL_FIELD(Vertex, u)
0358 SGB_GET_UTIL_FIELD(Vertex, v)
0359 SGB_GET_UTIL_FIELD(Vertex, w)
0360 SGB_GET_UTIL_FIELD(Vertex, x)
0361 SGB_GET_UTIL_FIELD(Vertex, y)
0362 SGB_GET_UTIL_FIELD(Vertex, z)
0363
0364 SGB_GET_UTIL_FIELD(Arc, a)
0365 SGB_GET_UTIL_FIELD(Arc, b)
0366
0367 // Vertex Utility Map
0368 template < class Tag, class Ref >
0369 class sgb_vertex_util_map
0370 : public boost::put_get_helper< Ref, sgb_vertex_util_map< Tag, Ref > >
0371 {
0372     Tag tag;
0373
0374 public:
0375     explicit sgb_vertex_util_map(Tag tag = Tag()) : tag(tag) {}
0376     typedef boost::lvalue_property_map_tag category;
0377     typedef typename Tag::type value_type;
0378     typedef Vertex* key_type;
0379     typedef Ref reference;
0380     reference operator[](Vertex* v) const { return get_util_field(v, tag); }
0381 };
0382
0383 // Edge Utility Map
0384 template < class Tag, class Ref >
0385 class sgb_edge_util_map
0386 : public boost::put_get_helper< Ref, sgb_edge_util_map< Tag, Ref > >
0387 {
0388     Tag tag;
0389
0390 public:
0391     explicit sgb_edge_util_map(Tag tag = Tag()) : tag(tag) {}
0392     typedef boost::lvalue_property_map_tag category;
0393     typedef typename Tag::type value_type;
0394     typedef Vertex* key_type;
0395     typedef Ref reference;
0396     reference operator[](const sgb_edge& e) const
0397     {
0398         return get_util_field(e._arc, tag);
0399     }
0400 };
0401
0402 template < class Tag >
0403 inline sgb_vertex_util_map< Tag, const typename Tag::type& > get_property_map(
0404     Tag, const sgb_graph_ptr& g, vertex_property_tag)
0405 {
0406     return sgb_vertex_util_map< Tag, const typename Tag::type& >();
0407 }
0408 template < class Tag >
0409 inline sgb_vertex_util_map< Tag, typename Tag::type& > get_property_map(
0410     Tag, sgb_graph_ptr& g, vertex_property_tag)
0411 {
0412     return sgb_vertex_util_map< Tag, typename Tag::type& >();
0413 }
0414
0415 template < class Tag >
0416 inline sgb_edge_util_map< Tag, const typename Tag::type& > get_property_map(
0417     Tag, const sgb_graph_ptr& g, edge_property_tag)
0418 {
0419     return sgb_edge_util_map< Tag, const typename Tag::type& >();
0420 }
0421 template < class Tag >
0422 inline sgb_edge_util_map< Tag, typename Tag::type& > get_property_map(
0423     Tag, sgb_graph_ptr& g, edge_property_tag)
0424 {
0425     return sgb_edge_util_map< Tag, typename Tag::type& >();
0426 }
0427
0428 // Edge Length Access
0429 template < class Ref >
0430 class sgb_edge_length_map
0431 : public boost::put_get_helper< Ref, sgb_edge_length_map< Ref > >
0432 {
0433 public:
0434     typedef boost::lvalue_property_map_tag category;
0435     typedef long value_type;
0436     typedef sgb_edge key_type;
0437     typedef Ref reference;
0438     reference operator[](const sgb_edge& e) const { return e._arc->len; }
0439 };
0440
0441 inline sgb_edge_length_map< const long& > get(
0442     edge_length_t, const sgb_graph_ptr&)
0443 {
0444     return sgb_edge_length_map< const long& >();
0445 }
0446 inline sgb_edge_length_map< const long& > get(
0447     edge_length_t, const sgb_const_graph_ptr&)
0448 {
0449     return sgb_edge_length_map< const long& >();
0450 }
0451 inline sgb_edge_length_map< long& > get(edge_length_t, sgb_graph_ptr&)
0452 {
0453     return sgb_edge_length_map< long& >();
0454 }
0455 inline long get(edge_length_t, const sgb_graph_ptr&, const sgb_edge& key)
0456 {
0457     return key._arc->len;
0458 }
0459 inline long get(edge_length_t, const sgb_const_graph_ptr&, const sgb_edge& key)
0460 {
0461     return key._arc->len;
0462 }
0463 inline void put(edge_length_t, sgb_graph_ptr&, const sgb_edge& key, long value)
0464 {
0465     key._arc->len = value;
0466 }
0467
0468 // Property Map Traits Classes
0469 template <> struct property_map< sgb_graph_ptr, edge_length_t >
0470 {
0471     typedef sgb_edge_length_map< long& > type;
0472     typedef sgb_edge_length_map< const long& > const_type;
0473 };
0474 template <> struct property_map< sgb_graph_ptr, vertex_index_t >
0475 {
0476     typedef sgb_vertex_id_map type;
0477     typedef sgb_vertex_id_map const_type;
0478 };
0479 template <> struct property_map< sgb_graph_ptr, vertex_name_t >
0480 {
0481     typedef sgb_vertex_name_map type;
0482     typedef sgb_vertex_name_map const_type;
0483 };
0484
0485 template <> struct property_map< sgb_const_graph_ptr, edge_length_t >
0486 {
0487     typedef sgb_edge_length_map< const long& > const_type;
0488 };
0489 template <> struct property_map< sgb_const_graph_ptr, vertex_index_t >
0490 {
0491     typedef sgb_vertex_id_map const_type;
0492 };
0493 template <> struct property_map< sgb_const_graph_ptr, vertex_name_t >
0494 {
0495     typedef sgb_vertex_name_map const_type;
0496 };
0497
0498 namespace detail
0499 {
0500     template < class Kind, class PropertyTag > struct sgb_choose_property_map
0501     {
0502     };
0503     template < class PropertyTag >
0504     struct sgb_choose_property_map< vertex_property_tag, PropertyTag >
0505     {
0506         typedef typename PropertyTag::type value_type;
0507         typedef sgb_vertex_util_map< PropertyTag, value_type& > type;
0508         typedef sgb_vertex_util_map< PropertyTag, const value_type& >
0509             const_type;
0510     };
0511     template < class PropertyTag >
0512     struct sgb_choose_property_map< edge_property_tag, PropertyTag >
0513     {
0514         typedef typename PropertyTag::type value_type;
0515         typedef sgb_edge_util_map< PropertyTag, value_type& > type;
0516         typedef sgb_edge_util_map< PropertyTag, const value_type& > const_type;
0517     };
0518 } // namespace detail
0519 template < class PropertyTag > struct property_map< sgb_graph_ptr, PropertyTag >
0520 {
0521     typedef typename property_kind< PropertyTag >::type Kind;
0522     typedef detail::sgb_choose_property_map< Kind, PropertyTag > Choice;
0523     typedef typename Choice::type type;
0524     typedef typename Choice::const_type const_type;
0525 };
0526 template < class PropertyTag >
0527 struct property_map< sgb_const_graph_ptr, PropertyTag >
0528 {
0529     typedef typename property_kind< PropertyTag >::type Kind;
0530     typedef detail::sgb_choose_property_map< Kind, PropertyTag > Choice;
0531     typedef typename Choice::const_type const_type;
0532 };
0533
0534 #define SGB_UTIL_ACCESSOR(KIND, X)                                             \
0535     template < class T >                                                       \
0536     inline sgb_##KIND##_util_map< X##_property< T >, T& > get(                 \
0537         X##_property< T >, sgb_graph_ptr&)                                     \
0538     {                                                                          \
0539         return sgb_##KIND##_util_map< X##_property< T >, T& >();               \
0540     }                                                                          \
0541     template < class T >                                                       \
0542     inline sgb_##KIND##_util_map< X##_property< T >, const T& > get(           \
0543         X##_property< T >, const sgb_graph_ptr&)                               \
0544     {                                                                          \
0545         return sgb_##KIND##_util_map< X##_property< T >, const T& >();         \
0546     }                                                                          \
0547     template < class T >                                                       \
0548     inline sgb_##KIND##_util_map< X##_property< T >, const T& > get(           \
0549         X##_property< T >, const sgb_const_graph_ptr&)                         \
0550     {                                                                          \
0551         return sgb_##KIND##_util_map< X##_property< T >, const T& >();         \
0552     }                                                                          \
0553     template < class T, class Key >                                            \
0554     inline typename sgb_##KIND##_util_map< X##_property< T >,                  \
0555         const T& >::value_type                                                 \
0556     get(X##_property< T >, const sgb_graph_ptr&, const Key& key)               \
0557     {                                                                          \
0558         return sgb_##KIND##_util_map< X##_property< T >, const T& >()[key];    \
0559     }                                                                          \
0560     template < class T, class Key >                                            \
0561     inline typename sgb_##KIND##_util_map< X##_property< T >,                  \
0562         const T& >::value_type                                                 \
0563     get(X##_property< T >, const sgb_const_graph_ptr&, const Key& key)         \
0564     {                                                                          \
0565         return sgb_##KIND##_util_map< X##_property< T >, const T& >()[key];    \
0566     }                                                                          \
0567     template < class T, class Key, class Value >                               \
0568     inline void put(                                                           \
0569         X##_property< T >, sgb_graph_ptr&, const Key& key, const Value& value) \
0570     {                                                                          \
0571         sgb_##KIND##_util_map< X##_property< T >, T& >()[key] = value;         \
0572     }
0573
0574 SGB_UTIL_ACCESSOR(vertex, u)
0575 SGB_UTIL_ACCESSOR(vertex, v)
0576 SGB_UTIL_ACCESSOR(vertex, w)
0577 SGB_UTIL_ACCESSOR(vertex, x)
0578 SGB_UTIL_ACCESSOR(vertex, y)
0579 SGB_UTIL_ACCESSOR(vertex, z)
0580
0581 SGB_UTIL_ACCESSOR(edge, a)
0582 SGB_UTIL_ACCESSOR(edge, b)
0583
0584 } // namespace boost
0585
0586 #endif // BOOST_GRAPH_SGB_GRAPH_HPP