1 //======================================================================= 2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. 3 // Copyright 2010 Thomas Claveirole 4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Thomas Claveirole 5 // 6 // Distributed under the Boost Software License, Version 1.0. (See 7 // accompanying file LICENSE_1_0.txt or copy at 8 // http://www.boost.org/LICENSE_1_0.txt) 9 //======================================================================= 10 11 #ifndef BOOST_GRAPH_ADJACENCY_LIST_HPP 12 #define BOOST_GRAPH_ADJACENCY_LIST_HPP 13 14 15 #include <boost/config.hpp> 16 17 #include <vector> 18 #include <list> 19 #include <set> 20 21 #include <boost/unordered_set.hpp> 22 23 #if !defined BOOST_NO_SLIST 24 # ifdef BOOST_SLIST_HEADER 25 # include BOOST_SLIST_HEADER 26 # else 27 # include <slist> 28 # endif 29 #endif 30 31 #include <boost/scoped_ptr.hpp> 32 33 #include <boost/graph/graph_traits.hpp> 34 #include <boost/graph/graph_mutability_traits.hpp> 35 #include <boost/graph/graph_selectors.hpp> 36 #include <boost/property_map/property_map.hpp> 37 #include <boost/mpl/if.hpp> 38 #include <boost/mpl/and.hpp> 39 #include <boost/mpl/not.hpp> 40 #include <boost/mpl/bool.hpp> 41 #include <boost/graph/detail/edge.hpp> 42 #include <boost/type_traits/is_same.hpp> 43 #include <boost/detail/workaround.hpp> 44 #include <boost/graph/properties.hpp> 45 #include <boost/graph/named_graph.hpp> 46 47 namespace boost { 48 49 //=========================================================================== 50 // Selectors for the VertexList and EdgeList template parameters of 51 // adjacency_list, and the container_gen traits class which is used 52 // to map the selectors to the container type used to implement the 53 // graph. 54 55 #if !defined BOOST_NO_SLIST 56 struct slistS {}; 57 #endif 58 59 struct vecS { }; 60 struct listS { }; 61 struct setS { }; 62 struct mapS { }; 63 struct multisetS { }; 64 struct multimapS { }; 65 struct hash_setS { }; 66 struct hash_mapS { }; 67 struct hash_multisetS { }; 68 struct hash_multimapS { }; 69 70 template <class Selector, class ValueType> 71 struct container_gen { }; 72 73 template <class ValueType> 74 struct container_gen<listS, ValueType> { 75 typedef std::list<ValueType> type; 76 }; 77 #if !defined BOOST_NO_SLIST 78 template <class ValueType> 79 struct container_gen<slistS, ValueType> { 80 typedef BOOST_STD_EXTENSION_NAMESPACE::slist<ValueType> type; 81 }; 82 #endif 83 template <class ValueType> 84 struct container_gen<vecS, ValueType> { 85 typedef std::vector<ValueType> type; 86 }; 87 88 template <class ValueType> 89 struct container_gen<mapS, ValueType> { 90 typedef std::set<ValueType> type; 91 }; 92 93 template <class ValueType> 94 struct container_gen<setS, ValueType> { 95 typedef std::set<ValueType> type; 96 }; 97 98 template <class ValueType> 99 struct container_gen<multisetS, ValueType> { 100 typedef std::multiset<ValueType> type; 101 }; 102 103 template <class ValueType> 104 struct container_gen<multimapS, ValueType> { 105 typedef std::multiset<ValueType> type; 106 }; 107 108 template <class ValueType> 109 struct container_gen<hash_setS, ValueType> { 110 typedef boost::unordered_set<ValueType> type; 111 }; 112 113 template <class ValueType> 114 struct container_gen<hash_mapS, ValueType> { 115 typedef boost::unordered_set<ValueType> type; 116 }; 117 118 template <class ValueType> 119 struct container_gen<hash_multisetS, ValueType> { 120 typedef boost::unordered_multiset<ValueType> type; 121 }; 122 123 template <class ValueType> 124 struct container_gen<hash_multimapS, ValueType> { 125 typedef boost::unordered_multiset<ValueType> type; 126 }; 127 128 template <class StorageSelector> 129 struct parallel_edge_traits { }; 130 131 template <> 132 struct parallel_edge_traits<vecS> { 133 typedef allow_parallel_edge_tag type; }; 134 135 template <> 136 struct parallel_edge_traits<listS> { 137 typedef allow_parallel_edge_tag type; }; 138 139 #if !defined BOOST_NO_SLIST 140 template <> 141 struct parallel_edge_traits<slistS> { 142 typedef allow_parallel_edge_tag type; }; 143 #endif 144 145 template <> 146 struct parallel_edge_traits<setS> { 147 typedef disallow_parallel_edge_tag type; }; 148 149 template <> 150 struct parallel_edge_traits<multisetS> { 151 typedef allow_parallel_edge_tag type; }; 152 153 template <> 154 struct parallel_edge_traits<hash_setS> { 155 typedef disallow_parallel_edge_tag type; 156 }; 157 158 // mapS is obsolete, replaced with setS 159 template <> 160 struct parallel_edge_traits<mapS> { 161 typedef disallow_parallel_edge_tag type; }; 162 163 template <> 164 struct parallel_edge_traits<hash_mapS> { 165 typedef disallow_parallel_edge_tag type; 166 }; 167 168 template <> 169 struct parallel_edge_traits<hash_multisetS> { 170 typedef allow_parallel_edge_tag type; 171 }; 172 173 template <> 174 struct parallel_edge_traits<hash_multimapS> { 175 typedef allow_parallel_edge_tag type; 176 }; 177 178 namespace detail { 179 template <class Directed> struct is_random_access { 180 enum { value = false}; 181 typedef mpl::false_ type; 182 }; 183 template <> 184 struct is_random_access<vecS> { 185 enum { value = true }; 186 typedef mpl::true_ type; 187 }; 188 189 } // namespace detail 190 191 template <typename Selector> struct is_distributed_selector: mpl::false_ {}; 192 193 194 //=========================================================================== 195 // The adjacency_list_traits class, which provides a way to access 196 // some of the associated types of an adjacency_list type without 197 // having to first create the adjacency_list type. This is useful 198 // when trying to create interior vertex or edge properties who's 199 // value type is a vertex or edge descriptor. 200 201 template <class OutEdgeListS = vecS, 202 class VertexListS = vecS, 203 class DirectedS = directedS, 204 class EdgeListS = listS> 205 struct adjacency_list_traits 206 { 207 typedef typename detail::is_random_access<VertexListS>::type 208 is_rand_access; 209 typedef typename DirectedS::is_bidir_t is_bidir; 210 typedef typename DirectedS::is_directed_t is_directed; 211 212 typedef typename mpl::if_<is_bidir, 213 bidirectional_tag, 214 typename mpl::if_<is_directed, 215 directed_tag, undirected_tag 216 >::type 217 >::type directed_category; 218 219 typedef typename parallel_edge_traits<OutEdgeListS>::type 220 edge_parallel_category; 221 222 typedef std::size_t vertices_size_type; 223 typedef void* vertex_ptr; 224 typedef typename mpl::if_<is_rand_access, 225 vertices_size_type, vertex_ptr>::type vertex_descriptor; 226 typedef detail::edge_desc_impl<directed_category, vertex_descriptor> 227 edge_descriptor; 228 229 private: 230 // Logic to figure out the edges_size_type 231 struct dummy {}; 232 typedef typename container_gen<EdgeListS, dummy>::type EdgeContainer; 233 typedef typename DirectedS::is_bidir_t BidirectionalT; 234 typedef typename DirectedS::is_directed_t DirectedT; 235 typedef typename mpl::and_<DirectedT, 236 typename mpl::not_<BidirectionalT>::type >::type on_edge_storage; 237 public: 238 typedef typename mpl::if_<on_edge_storage, 239 std::size_t, typename EdgeContainer::size_type 240 >::type edges_size_type; 241 242 }; 243 244 } // namespace boost 245 246 #include <boost/graph/detail/adjacency_list.hpp> 247 248 namespace boost { 249 250 //=========================================================================== 251 // The adjacency_list class. 252 // 253 254 template <class OutEdgeListS = vecS, // a Sequence or an AssociativeContainer 255 class VertexListS = vecS, // a Sequence or a RandomAccessContainer 256 class DirectedS = directedS, 257 class VertexProperty = no_property, 258 class EdgeProperty = no_property, 259 class GraphProperty = no_property, 260 class EdgeListS = listS> 261 class adjacency_list 262 : public detail::adj_list_gen< 263 adjacency_list<OutEdgeListS,VertexListS,DirectedS, 264 VertexProperty,EdgeProperty,GraphProperty,EdgeListS>, 265 VertexListS, OutEdgeListS, DirectedS, 266 VertexProperty, EdgeProperty, 267 GraphProperty, EdgeListS>::type, 268 // Support for named vertices 269 public graph::maybe_named_graph< 270 adjacency_list<OutEdgeListS,VertexListS,DirectedS, 271 VertexProperty,EdgeProperty,GraphProperty,EdgeListS>, 272 typename adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS, 273 EdgeListS>::vertex_descriptor, 274 VertexProperty> 275 { 276 public: 277 typedef GraphProperty graph_property_type; 278 typedef typename lookup_one_property<GraphProperty, graph_bundle_t>::type graph_bundled; 279 280 typedef VertexProperty vertex_property_type; 281 typedef typename lookup_one_property<VertexProperty, vertex_bundle_t>::type vertex_bundled; 282 283 typedef EdgeProperty edge_property_type; 284 typedef typename lookup_one_property<EdgeProperty, edge_bundle_t>::type edge_bundled; 285 286 private: 287 typedef adjacency_list self; 288 typedef typename detail::adj_list_gen< 289 self, VertexListS, OutEdgeListS, DirectedS, 290 vertex_property_type, edge_property_type, GraphProperty, EdgeListS 291 >::type Base; 292 293 public: 294 typedef typename Base::stored_vertex stored_vertex; 295 typedef typename Base::vertices_size_type vertices_size_type; 296 typedef typename Base::edges_size_type edges_size_type; 297 typedef typename Base::degree_size_type degree_size_type; 298 typedef typename Base::vertex_descriptor vertex_descriptor; 299 typedef typename Base::edge_descriptor edge_descriptor; 300 typedef OutEdgeListS out_edge_list_selector; 301 typedef VertexListS vertex_list_selector; 302 typedef DirectedS directed_selector; 303 typedef EdgeListS edge_list_selector; 304 305 adjacency_list(const GraphProperty & p=GraphProperty ())306 adjacency_list(const GraphProperty& p = GraphProperty()) 307 : m_property(new graph_property_type(p)) 308 { } 309 adjacency_list(const adjacency_list & x)310 adjacency_list(const adjacency_list& x) 311 : Base(x), m_property(new graph_property_type(*x.m_property)) 312 { } 313 operator =(const adjacency_list & x)314 adjacency_list& operator=(const adjacency_list& x) { 315 // TBD: probably should give the strong guarantee 316 if (&x != this) { 317 Base::operator=(x); 318 319 // Copy/swap the ptr since we can't just assign it... 320 property_ptr p(new graph_property_type(*x.m_property)); 321 m_property.swap(p); 322 } 323 return *this; 324 } 325 326 // Required by Mutable Graph adjacency_list(vertices_size_type num_vertices,const GraphProperty & p=GraphProperty ())327 adjacency_list(vertices_size_type num_vertices, 328 const GraphProperty& p = GraphProperty()) 329 : Base(num_vertices), m_property(new graph_property_type(p)) 330 { } 331 332 // Required by Iterator Constructible Graph 333 template <class EdgeIterator> adjacency_list(EdgeIterator first,EdgeIterator last,vertices_size_type n,edges_size_type=0,const GraphProperty & p=GraphProperty ())334 adjacency_list(EdgeIterator first, EdgeIterator last, 335 vertices_size_type n, 336 edges_size_type = 0, 337 const GraphProperty& p = GraphProperty()) 338 : Base(n, first, last), m_property(new graph_property_type(p)) 339 { } 340 341 template <class EdgeIterator, class EdgePropertyIterator> adjacency_list(EdgeIterator first,EdgeIterator last,EdgePropertyIterator ep_iter,vertices_size_type n,edges_size_type=0,const GraphProperty & p=GraphProperty ())342 adjacency_list(EdgeIterator first, EdgeIterator last, 343 EdgePropertyIterator ep_iter, 344 vertices_size_type n, 345 edges_size_type = 0, 346 const GraphProperty& p = GraphProperty()) 347 : Base(n, first, last, ep_iter), m_property(new graph_property_type(p)) 348 { } 349 swap(adjacency_list & x)350 void swap(adjacency_list& x) { 351 // Is there a more efficient way to do this? 352 adjacency_list tmp(x); 353 x = *this; 354 *this = tmp; 355 } 356 clear()357 void clear() 358 { 359 this->clearing_graph(); 360 Base::clear(); 361 } 362 363 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES 364 // Directly access a vertex or edge bundle operator [](vertex_descriptor v)365 vertex_bundled& operator[](vertex_descriptor v) 366 { return get(vertex_bundle, *this)[v]; } 367 operator [](vertex_descriptor v) const368 const vertex_bundled& operator[](vertex_descriptor v) const 369 { return get(vertex_bundle, *this)[v]; } 370 operator [](edge_descriptor e)371 edge_bundled& operator[](edge_descriptor e) 372 { return get(edge_bundle, *this)[e]; } 373 operator [](edge_descriptor e) const374 const edge_bundled& operator[](edge_descriptor e) const 375 { return get(edge_bundle, *this)[e]; } 376 operator [](graph_bundle_t)377 graph_bundled& operator[](graph_bundle_t) 378 { return get_property(*this); } 379 operator [](graph_bundle_t) const380 graph_bundled const& operator[](graph_bundle_t) const 381 { return get_property(*this); } 382 #endif 383 384 // protected: (would be protected if friends were more portable) 385 typedef scoped_ptr<graph_property_type> property_ptr; 386 property_ptr m_property; 387 }; 388 389 #define ADJLIST_PARAMS \ 390 typename OEL, typename VL, typename D, typename VP, typename EP, \ 391 typename GP, typename EL 392 #define ADJLIST adjacency_list<OEL,VL,D,VP,EP,GP,EL> 393 394 template<ADJLIST_PARAMS, typename Tag, typename Value> set_property(ADJLIST & g,Tag tag,Value const & value)395 inline void set_property(ADJLIST& g, Tag tag, Value const& value) { 396 get_property_value(*g.m_property, tag) = value; 397 } 398 399 template<ADJLIST_PARAMS, typename Tag> 400 inline typename graph_property<ADJLIST, Tag>::type& get_property(ADJLIST & g,Tag tag)401 get_property(ADJLIST& g, Tag tag) { 402 return get_property_value(*g.m_property, tag); 403 } 404 405 template<ADJLIST_PARAMS, typename Tag> 406 inline typename graph_property<ADJLIST, Tag>::type const& get_property(ADJLIST const & g,Tag tag)407 get_property(ADJLIST const& g, Tag tag) { 408 return get_property_value(*g.m_property, tag); 409 } 410 411 // dwa 09/25/00 - needed to be more explicit so reverse_graph would work. 412 template <class Directed, class Vertex, 413 class OutEdgeListS, 414 class VertexListS, 415 class DirectedS, 416 class VertexProperty, 417 class EdgeProperty, 418 class GraphProperty, class EdgeListS> 419 inline Vertex source(const detail::edge_base<Directed,Vertex> & e,const adjacency_list<OutEdgeListS,VertexListS,DirectedS,VertexProperty,EdgeProperty,GraphProperty,EdgeListS> &)420 source(const detail::edge_base<Directed,Vertex>& e, 421 const adjacency_list<OutEdgeListS, VertexListS, DirectedS, 422 VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&) 423 { 424 return e.m_source; 425 } 426 427 template <class Directed, class Vertex, class OutEdgeListS, 428 class VertexListS, class DirectedS, class VertexProperty, 429 class EdgeProperty, class GraphProperty, class EdgeListS> 430 inline Vertex target(const detail::edge_base<Directed,Vertex> & e,const adjacency_list<OutEdgeListS,VertexListS,DirectedS,VertexProperty,EdgeProperty,GraphProperty,EdgeListS> &)431 target(const detail::edge_base<Directed,Vertex>& e, 432 const adjacency_list<OutEdgeListS, VertexListS, DirectedS, 433 VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&) 434 { 435 return e.m_target; 436 } 437 438 // Mutability Traits 439 template <ADJLIST_PARAMS> 440 struct graph_mutability_traits<ADJLIST> { 441 typedef mutable_property_graph_tag category; 442 }; 443 444 // Can't remove vertices from adjacency lists with VL==vecS 445 template <typename OEL, typename D, typename VP, typename EP, typename GP, typename EL> 446 struct graph_mutability_traits< adjacency_list<OEL,vecS,D,VP,EP,GP,EL> > { 447 typedef add_only_property_graph_tag category; 448 }; 449 #undef ADJLIST_PARAMS 450 #undef ADJLIST 451 452 453 } // namespace boost 454 455 456 #endif // BOOST_GRAPH_ADJACENCY_LIST_HPP 457