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 */ empty(long n)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: sgb_edge()125 sgb_edge() : _arc(0), _src(0) { } sgb_edge(Arc * a,Vertex * s)126 sgb_edge(Arc* a, Vertex* s) : _arc(a), _src(s) { } source(self e,sgb_const_graph_ptr)127 friend Vertex* source(self e, sgb_const_graph_ptr) { return e._src; } target(self e,sgb_const_graph_ptr)128 friend Vertex* target(self e, sgb_const_graph_ptr) { return e._arc->tip; } operator ==(const self & a,const self & b)129 friend bool operator==(const self& a, const self& b) { 130 return a._arc == b._arc; } operator !=(const self & a,const self & b)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: sgb_out_edge_iterator()153 sgb_out_edge_iterator() : _src(0), _arc(0) {} sgb_out_edge_iterator(Vertex * s,Arc * d)154 sgb_out_edge_iterator(Vertex* s, Arc* d) : _src(s), _arc(d) {} operator *()155 boost::sgb_edge operator*() { return boost::sgb_edge(_arc, _src); } operator ++()156 self& operator++() { _arc = _arc->next; return *this; } operator ==(const self & x,const self & y)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: sgb_adj_iterator()170 sgb_adj_iterator() : _arc(0) {} sgb_adj_iterator(Arc * d)171 sgb_adj_iterator(Arc* d) : _arc(d) {} operator *()172 Vertex* operator*() { return _arc->tip; } operator ++()173 self& operator++() { _arc = _arc->next; return *this; } operator ==(const self & x,const self & y)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: sgb_vertex_iterator()190 sgb_vertex_iterator() : _v(0) { } sgb_vertex_iterator(Vertex * v)191 sgb_vertex_iterator(Vertex* v) : _v(v) { } operator *()192 Vertex* operator*() { return _v; } operator ++()193 self& operator++() { ++_v; return *this; } operator ==(const self & x,const self & y)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> vertices(sgb_const_graph_ptr g)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> out_edges(Vertex * u,sgb_const_graph_ptr)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 out_degree(Vertex * u,sgb_const_graph_ptr g)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> adjacent_vertices(Vertex * u,sgb_const_graph_ptr)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 num_vertices(sgb_const_graph_ptr g)233 inline long num_vertices(sgb_const_graph_ptr g) { return g->n; } num_edges(sgb_const_graph_ptr g)234 inline long num_edges(sgb_const_graph_ptr g) { return g->m; } 235 vertex(long v,sgb_const_graph_ptr g)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; sgb_vertex_id_map()250 sgb_vertex_id_map() : _g(0) { } sgb_vertex_id_map(sgb_graph_ptr g)251 sgb_vertex_id_map(sgb_graph_ptr g) : _g(g) { } operator [](Vertex * v) const252 long operator[](Vertex* v) const { return v - _g->vertices; } 253 protected: 254 sgb_graph_ptr _g; 255 }; get(vertex_index_t,sgb_graph_ptr g)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; operator [](Vertex * v) const269 char* operator[](Vertex* v) const { return v->name; } 270 }; get(vertex_name_t,sgb_graph_ptr)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 }; SGB_PROPERTY_TAG(vertex,u)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; } get_util(util & u,Arc *)296 inline Arc*& get_util(util& u, Arc*) { return u.A; } get_util(util & u,sgb_graph_ptr)297 inline sgb_graph_ptr& get_util(util& u, sgb_graph_ptr) { return u.G; } get_util(util & u,char *)298 inline char*& get_util(util& u, char*) { return u.S; } get_util(util & u,long)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: sgb_vertex_util_map(Tag tag=Tag ())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; operator [](Vertex * v) const328 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: sgb_edge_util_map(Tag tag=Tag ())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; operator [](const sgb_edge & e) const345 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&> get_property_map(Tag,const sgb_graph_ptr & g,vertex_property_tag)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&> get_property_map(Tag,sgb_graph_ptr & g,vertex_property_tag)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&> get_property_map(Tag,const sgb_graph_ptr & g,edge_property_tag)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&> get_property_map(Tag,sgb_graph_ptr & g,edge_property_tag)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; operator [](const sgb_edge & e) const384 reference operator[](const sgb_edge& e) const { 385 return e._arc->len; 386 } 387 }; 388 389 inline sgb_edge_length_map<const long&> get(edge_length_t,const sgb_graph_ptr &)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&> get(edge_length_t,const sgb_const_graph_ptr &)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&> get(edge_length_t,sgb_graph_ptr &)398 get(edge_length_t, sgb_graph_ptr&) { 399 return sgb_edge_length_map<long&>(); 400 } 401 inline long get(edge_length_t,const sgb_graph_ptr &,const sgb_edge & key)402 get(edge_length_t, const sgb_graph_ptr&, const sgb_edge& key) { 403 return key._arc->len; 404 } 405 inline long get(edge_length_t,const sgb_const_graph_ptr &,const sgb_edge & key)406 get(edge_length_t, const sgb_const_graph_ptr&, const sgb_edge& key) { 407 return key._arc->len; 408 } 409 inline void put(edge_length_t,sgb_graph_ptr &,const sgb_edge & key,long value)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 524