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