[857] | 1 | //=======================================================================
|
---|
| 2 | // Copyright 1997, 1998, 1999, 2000 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 |
|
---|
| 10 | #ifndef BOOST_GRAPH_ADJACENCY_LIST_HPP
|
---|
| 11 | #define BOOST_GRAPH_ADJACENCY_LIST_HPP
|
---|
| 12 |
|
---|
| 13 |
|
---|
| 14 | #include <boost/config.hpp>
|
---|
| 15 |
|
---|
| 16 | #include <vector>
|
---|
| 17 | #include <list>
|
---|
| 18 | #include <set>
|
---|
| 19 |
|
---|
| 20 | #if !defined BOOST_NO_HASH
|
---|
| 21 | #include <hash_set>
|
---|
| 22 | #endif
|
---|
| 23 |
|
---|
| 24 | #if !defined BOOST_NO_SLIST
|
---|
| 25 | #include <slist>
|
---|
| 26 | #endif
|
---|
| 27 |
|
---|
| 28 | #include <boost/graph/graph_traits.hpp>
|
---|
| 29 | #include <boost/graph/graph_selectors.hpp>
|
---|
| 30 | #include <boost/property_map.hpp>
|
---|
| 31 | #include <boost/pending/ct_if.hpp>
|
---|
| 32 | #include <boost/graph/detail/edge.hpp>
|
---|
| 33 | #include <boost/type_traits/is_same.hpp>
|
---|
| 34 | #include <boost/detail/workaround.hpp>
|
---|
| 35 | #include <boost/graph/properties.hpp>
|
---|
| 36 |
|
---|
| 37 | namespace boost {
|
---|
| 38 |
|
---|
| 39 | //===========================================================================
|
---|
| 40 | // Selectors for the VertexList and EdgeList template parameters of
|
---|
| 41 | // adjacency_list, and the container_gen traits class which is used
|
---|
| 42 | // to map the selectors to the container type used to implement the
|
---|
| 43 | // graph.
|
---|
| 44 | //
|
---|
| 45 | // The main container_gen traits class uses partial specialization,
|
---|
| 46 | // so we also include a workaround.
|
---|
| 47 |
|
---|
| 48 | #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
|
---|
| 49 |
|
---|
| 50 | #if !defined BOOST_NO_SLIST
|
---|
| 51 | struct slistS {};
|
---|
| 52 | #endif
|
---|
| 53 |
|
---|
| 54 | struct vecS { };
|
---|
| 55 | struct listS { };
|
---|
| 56 | struct setS { };
|
---|
| 57 | struct multisetS { };
|
---|
| 58 | struct mapS { };
|
---|
| 59 | #if !defined BOOST_NO_HASH
|
---|
| 60 | struct hash_mapS { };
|
---|
| 61 | struct hash_setS { };
|
---|
| 62 | #endif
|
---|
| 63 |
|
---|
| 64 | template <class Selector, class ValueType>
|
---|
| 65 | struct container_gen { };
|
---|
| 66 |
|
---|
| 67 | template <class ValueType>
|
---|
| 68 | struct container_gen<listS, ValueType> {
|
---|
| 69 | typedef std::list<ValueType> type;
|
---|
| 70 | };
|
---|
| 71 | #if !defined BOOST_NO_SLIST
|
---|
| 72 | template <class ValueType>
|
---|
| 73 | struct container_gen<slistS, ValueType> {
|
---|
| 74 | typedef BOOST_STD_EXTENSION_NAMESPACE::slist<ValueType> type;
|
---|
| 75 | };
|
---|
| 76 | #endif
|
---|
| 77 | template <class ValueType>
|
---|
| 78 | struct container_gen<vecS, ValueType> {
|
---|
| 79 | typedef std::vector<ValueType> type;
|
---|
| 80 | };
|
---|
| 81 |
|
---|
| 82 | template <class ValueType>
|
---|
| 83 | struct container_gen<mapS, ValueType> {
|
---|
| 84 | typedef std::set<ValueType> type;
|
---|
| 85 | };
|
---|
| 86 |
|
---|
| 87 | template <class ValueType>
|
---|
| 88 | struct container_gen<setS, ValueType> {
|
---|
| 89 | typedef std::set<ValueType> type;
|
---|
| 90 | };
|
---|
| 91 |
|
---|
| 92 | template <class ValueType>
|
---|
| 93 | struct container_gen<multisetS, ValueType> {
|
---|
| 94 | typedef std::multiset<ValueType> type;
|
---|
| 95 | };
|
---|
| 96 |
|
---|
| 97 | #if !defined BOOST_NO_HASH
|
---|
| 98 | template <class ValueType>
|
---|
| 99 | struct container_gen<hash_mapS, ValueType> {
|
---|
| 100 | typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<ValueType> type;
|
---|
| 101 | };
|
---|
| 102 |
|
---|
| 103 | template <class ValueType>
|
---|
| 104 | struct container_gen<hash_setS, ValueType> {
|
---|
| 105 | typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<ValueType> type;
|
---|
| 106 | };
|
---|
| 107 | #endif
|
---|
| 108 |
|
---|
| 109 | #else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
|
---|
| 110 |
|
---|
| 111 | #if !defined BOOST_NO_SLIST
|
---|
| 112 | struct slistS {
|
---|
| 113 | template <class T>
|
---|
| 114 | struct bind_ { typedef std::slist<T> type; };
|
---|
| 115 | };
|
---|
| 116 | #endif
|
---|
| 117 |
|
---|
| 118 | struct vecS {
|
---|
| 119 | template <class T>
|
---|
| 120 | struct bind_ { typedef std::vector<T> type; };
|
---|
| 121 | };
|
---|
| 122 |
|
---|
| 123 | struct listS {
|
---|
| 124 | template <class T>
|
---|
| 125 | struct bind_ { typedef std::list<T> type; };
|
---|
| 126 | };
|
---|
| 127 |
|
---|
| 128 | struct setS {
|
---|
| 129 | template <class T>
|
---|
| 130 | struct bind_ { typedef std::set<T, std::less<T> > type; };
|
---|
| 131 | };
|
---|
| 132 |
|
---|
| 133 | struct multisetS {
|
---|
| 134 | template <class T>
|
---|
| 135 | struct bind_ { typedef std::multiset<T, std::less<T> > type; };
|
---|
| 136 | };
|
---|
| 137 |
|
---|
| 138 | #if !defined BOOST_NO_HASH
|
---|
| 139 | struct hash_setS {
|
---|
| 140 | template <class T>
|
---|
| 141 | struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<T, std::less<T> > type; };
|
---|
| 142 | };
|
---|
| 143 | #endif
|
---|
| 144 |
|
---|
| 145 | struct mapS {
|
---|
| 146 | template <class T>
|
---|
| 147 | struct bind_ { typedef std::set<T, std::less<T> > type; };
|
---|
| 148 | };
|
---|
| 149 |
|
---|
| 150 | #if !defined BOOST_NO_HASH
|
---|
| 151 | struct hash_mapS {
|
---|
| 152 | template <class T>
|
---|
| 153 | struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<T, std::less<T> > type; };
|
---|
| 154 | };
|
---|
| 155 | #endif
|
---|
| 156 |
|
---|
| 157 | template <class Selector> struct container_selector {
|
---|
| 158 | typedef vecS type;
|
---|
| 159 | };
|
---|
| 160 |
|
---|
| 161 | #define BOOST_CONTAINER_SELECTOR(NAME) \
|
---|
| 162 | template <> struct container_selector<NAME> { \
|
---|
| 163 | typedef NAME type; \
|
---|
| 164 | }
|
---|
| 165 |
|
---|
| 166 | BOOST_CONTAINER_SELECTOR(vecS);
|
---|
| 167 | BOOST_CONTAINER_SELECTOR(listS);
|
---|
| 168 | BOOST_CONTAINER_SELECTOR(mapS);
|
---|
| 169 | BOOST_CONTAINER_SELECTOR(setS);
|
---|
| 170 | BOOST_CONTAINER_SELECTOR(multisetS);
|
---|
| 171 | #if !defined BOOST_NO_HASH
|
---|
| 172 | BOOST_CONTAINER_SELECTOR(hash_mapS);
|
---|
| 173 | #endif
|
---|
| 174 | #if !defined BOOST_NO_SLIST
|
---|
| 175 | BOOST_CONTAINER_SELECTOR(slistS);
|
---|
| 176 | #endif
|
---|
| 177 |
|
---|
| 178 | template <class Selector, class ValueType>
|
---|
| 179 | struct container_gen {
|
---|
| 180 | typedef typename container_selector<Selector>::type Select;
|
---|
| 181 | typedef typename Select:: template bind_<ValueType>::type type;
|
---|
| 182 | };
|
---|
| 183 |
|
---|
| 184 | #endif // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
|
---|
| 185 |
|
---|
| 186 | template <class StorageSelector>
|
---|
| 187 | struct parallel_edge_traits { };
|
---|
| 188 |
|
---|
| 189 | template <>
|
---|
| 190 | struct parallel_edge_traits<vecS> {
|
---|
| 191 | typedef allow_parallel_edge_tag type; };
|
---|
| 192 |
|
---|
| 193 | template <>
|
---|
| 194 | struct parallel_edge_traits<listS> {
|
---|
| 195 | typedef allow_parallel_edge_tag type; };
|
---|
| 196 |
|
---|
| 197 | #if !defined BOOST_NO_SLIST
|
---|
| 198 | template <>
|
---|
| 199 | struct parallel_edge_traits<slistS> {
|
---|
| 200 | typedef allow_parallel_edge_tag type; };
|
---|
| 201 | #endif
|
---|
| 202 |
|
---|
| 203 | template <>
|
---|
| 204 | struct parallel_edge_traits<setS> {
|
---|
| 205 | typedef disallow_parallel_edge_tag type; };
|
---|
| 206 |
|
---|
| 207 | template <>
|
---|
| 208 | struct parallel_edge_traits<multisetS> {
|
---|
| 209 | typedef allow_parallel_edge_tag type; };
|
---|
| 210 |
|
---|
| 211 | #if !defined BOOST_NO_HASH
|
---|
| 212 | template <>
|
---|
| 213 | struct parallel_edge_traits<hash_setS> {
|
---|
| 214 | typedef disallow_parallel_edge_tag type;
|
---|
| 215 | };
|
---|
| 216 | #endif
|
---|
| 217 |
|
---|
| 218 | // mapS is obsolete, replaced with setS
|
---|
| 219 | template <>
|
---|
| 220 | struct parallel_edge_traits<mapS> {
|
---|
| 221 | typedef disallow_parallel_edge_tag type; };
|
---|
| 222 |
|
---|
| 223 | #if !defined BOOST_NO_HASH
|
---|
| 224 | template <>
|
---|
| 225 | struct parallel_edge_traits<hash_mapS> {
|
---|
| 226 | typedef disallow_parallel_edge_tag type;
|
---|
| 227 | };
|
---|
| 228 | #endif
|
---|
| 229 |
|
---|
| 230 | namespace detail {
|
---|
| 231 | template <class Directed> struct is_random_access {
|
---|
| 232 | enum { value = false};
|
---|
| 233 | typedef false_type type;
|
---|
| 234 | };
|
---|
| 235 | template <>
|
---|
| 236 | struct is_random_access<vecS> {
|
---|
| 237 | enum { value = true };
|
---|
| 238 | typedef true_type type;
|
---|
| 239 | };
|
---|
| 240 |
|
---|
| 241 | } // namespace detail
|
---|
| 242 |
|
---|
| 243 |
|
---|
| 244 |
|
---|
| 245 | //===========================================================================
|
---|
| 246 | // The adjacency_list_traits class, which provides a way to access
|
---|
| 247 | // some of the associated types of an adjacency_list type without
|
---|
| 248 | // having to first create the adjacency_list type. This is useful
|
---|
| 249 | // when trying to create interior vertex or edge properties who's
|
---|
| 250 | // value type is a vertex or edge descriptor.
|
---|
| 251 |
|
---|
| 252 | template <class OutEdgeListS = vecS,
|
---|
| 253 | class VertexListS = vecS,
|
---|
| 254 | class DirectedS = directedS>
|
---|
| 255 | struct adjacency_list_traits
|
---|
| 256 | {
|
---|
| 257 | typedef typename detail::is_random_access<VertexListS>::type
|
---|
| 258 | is_rand_access;
|
---|
| 259 | typedef typename DirectedS::is_bidir_t is_bidir;
|
---|
| 260 | typedef typename DirectedS::is_directed_t is_directed;
|
---|
| 261 |
|
---|
| 262 | typedef typename boost::ct_if_t<is_bidir,
|
---|
| 263 | bidirectional_tag,
|
---|
| 264 | typename boost::ct_if_t<is_directed,
|
---|
| 265 | directed_tag, undirected_tag
|
---|
| 266 | >::type
|
---|
| 267 | >::type directed_category;
|
---|
| 268 |
|
---|
| 269 | typedef typename parallel_edge_traits<OutEdgeListS>::type
|
---|
| 270 | edge_parallel_category;
|
---|
| 271 |
|
---|
| 272 | typedef void* vertex_ptr;
|
---|
| 273 | typedef typename boost::ct_if_t<is_rand_access,
|
---|
| 274 | std::size_t, vertex_ptr>::type vertex_descriptor;
|
---|
| 275 | typedef detail::edge_desc_impl<directed_category, vertex_descriptor>
|
---|
| 276 | edge_descriptor;
|
---|
| 277 | };
|
---|
| 278 |
|
---|
| 279 | } // namespace boost
|
---|
| 280 |
|
---|
| 281 | #include <boost/graph/detail/adjacency_list.hpp>
|
---|
| 282 |
|
---|
| 283 | namespace boost {
|
---|
| 284 |
|
---|
| 285 | //===========================================================================
|
---|
| 286 | // The adjacency_list class.
|
---|
| 287 | //
|
---|
| 288 |
|
---|
| 289 | template <class OutEdgeListS = vecS, // a Sequence or an AssociativeContainer
|
---|
| 290 | class VertexListS = vecS, // a Sequence or a RandomAccessContainer
|
---|
| 291 | class DirectedS = directedS,
|
---|
| 292 | class VertexProperty = no_property,
|
---|
| 293 | class EdgeProperty = no_property,
|
---|
| 294 | class GraphProperty = no_property,
|
---|
| 295 | class EdgeListS = listS>
|
---|
| 296 | class adjacency_list
|
---|
| 297 | : public detail::adj_list_gen<
|
---|
| 298 | adjacency_list<OutEdgeListS,VertexListS,DirectedS,
|
---|
| 299 | VertexProperty,EdgeProperty,GraphProperty,EdgeListS>,
|
---|
| 300 | VertexListS, OutEdgeListS, DirectedS,
|
---|
| 301 | #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
|
---|
| 302 | typename detail::retag_property_list<vertex_bundle_t,
|
---|
| 303 | VertexProperty>::type,
|
---|
| 304 | typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::type,
|
---|
| 305 | #else
|
---|
| 306 | VertexProperty, EdgeProperty,
|
---|
| 307 | #endif
|
---|
| 308 | GraphProperty, EdgeListS>::type
|
---|
| 309 | {
|
---|
| 310 | #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
|
---|
| 311 | typedef typename detail::retag_property_list<vertex_bundle_t,
|
---|
| 312 | VertexProperty>::retagged
|
---|
| 313 | maybe_vertex_bundled;
|
---|
| 314 |
|
---|
| 315 | typedef typename detail::retag_property_list<edge_bundle_t,
|
---|
| 316 | EdgeProperty>::retagged
|
---|
| 317 | maybe_edge_bundled;
|
---|
| 318 | #endif
|
---|
| 319 |
|
---|
| 320 | public:
|
---|
| 321 | #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
|
---|
| 322 | typedef typename detail::retag_property_list<vertex_bundle_t,
|
---|
| 323 | VertexProperty>::type
|
---|
| 324 | vertex_property_type;
|
---|
| 325 | typedef typename detail::retag_property_list<edge_bundle_t,
|
---|
| 326 | EdgeProperty>::type
|
---|
| 327 | edge_property_type;
|
---|
| 328 |
|
---|
| 329 | // The types that are actually bundled
|
---|
| 330 | typedef typename ct_if<(is_same<maybe_vertex_bundled, no_property>::value),
|
---|
| 331 | no_vertex_bundle,
|
---|
| 332 | maybe_vertex_bundled>::type vertex_bundled;
|
---|
| 333 | typedef typename ct_if<(is_same<maybe_edge_bundled, no_property>::value),
|
---|
| 334 | no_edge_bundle,
|
---|
| 335 | maybe_edge_bundled>::type edge_bundled;
|
---|
| 336 | #else
|
---|
| 337 | typedef VertexProperty vertex_property_type;
|
---|
| 338 | typedef EdgeProperty edge_property_type;
|
---|
| 339 | typedef no_vertex_bundle vertex_bundled;
|
---|
| 340 | typedef no_edge_bundle edge_bundled;
|
---|
| 341 | #endif
|
---|
| 342 |
|
---|
| 343 | private:
|
---|
| 344 | typedef adjacency_list self;
|
---|
| 345 | typedef typename detail::adj_list_gen<
|
---|
| 346 | self, VertexListS, OutEdgeListS, DirectedS,
|
---|
| 347 | vertex_property_type, edge_property_type, GraphProperty, EdgeListS
|
---|
| 348 | >::type Base;
|
---|
| 349 |
|
---|
| 350 | public:
|
---|
| 351 | typedef typename Base::stored_vertex stored_vertex;
|
---|
| 352 | typedef typename Base::vertices_size_type vertices_size_type;
|
---|
| 353 | typedef typename Base::edges_size_type edges_size_type;
|
---|
| 354 | typedef typename Base::degree_size_type degree_size_type;
|
---|
| 355 | typedef typename Base::vertex_descriptor vertex_descriptor;
|
---|
| 356 | typedef typename Base::edge_descriptor edge_descriptor;
|
---|
| 357 | typedef OutEdgeListS out_edge_list_selector;
|
---|
| 358 | typedef VertexListS vertex_list_selector;
|
---|
| 359 | typedef DirectedS directed_selector;
|
---|
| 360 | typedef EdgeListS edge_list_selector;
|
---|
| 361 |
|
---|
| 362 | typedef GraphProperty graph_property_type;
|
---|
| 363 |
|
---|
| 364 | inline adjacency_list(const GraphProperty& p = GraphProperty())
|
---|
| 365 | : m_property(p) { }
|
---|
| 366 |
|
---|
| 367 | inline adjacency_list(const adjacency_list& x)
|
---|
| 368 | : Base(x), m_property(x.m_property) { }
|
---|
| 369 |
|
---|
| 370 | inline adjacency_list& operator=(const adjacency_list& x) {
|
---|
| 371 | // TBD: probably should give the strong guarantee
|
---|
| 372 | if (&x != this) {
|
---|
| 373 | Base::operator=(x);
|
---|
| 374 | m_property = x.m_property;
|
---|
| 375 | }
|
---|
| 376 | return *this;
|
---|
| 377 | }
|
---|
| 378 |
|
---|
| 379 | // Required by Mutable Graph
|
---|
| 380 | inline adjacency_list(vertices_size_type num_vertices,
|
---|
| 381 | const GraphProperty& p = GraphProperty())
|
---|
| 382 | : Base(num_vertices), m_property(p) { }
|
---|
| 383 |
|
---|
| 384 | #if !defined(BOOST_MSVC) || BOOST_MSVC >= 1300
|
---|
| 385 | // Required by Iterator Constructible Graph
|
---|
| 386 | template <class EdgeIterator>
|
---|
| 387 | inline adjacency_list(EdgeIterator first, EdgeIterator last,
|
---|
| 388 | vertices_size_type n,
|
---|
| 389 | edges_size_type = 0,
|
---|
| 390 | const GraphProperty& p = GraphProperty())
|
---|
| 391 | : Base(n, first, last), m_property(p) { }
|
---|
| 392 |
|
---|
| 393 | template <class EdgeIterator, class EdgePropertyIterator>
|
---|
| 394 | inline adjacency_list(EdgeIterator first, EdgeIterator last,
|
---|
| 395 | EdgePropertyIterator ep_iter,
|
---|
| 396 | vertices_size_type n,
|
---|
| 397 | edges_size_type = 0,
|
---|
| 398 | const GraphProperty& p = GraphProperty())
|
---|
| 399 | : Base(n, first, last, ep_iter), m_property(p) { }
|
---|
| 400 | #endif
|
---|
| 401 |
|
---|
| 402 | void swap(adjacency_list& x) {
|
---|
| 403 | // Is there a more efficient way to do this?
|
---|
| 404 | adjacency_list tmp(x);
|
---|
| 405 | x = *this;
|
---|
| 406 | *this = tmp;
|
---|
| 407 | }
|
---|
| 408 |
|
---|
| 409 | #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
|
---|
| 410 | // Directly access a vertex or edge bundle
|
---|
| 411 | vertex_bundled& operator[](vertex_descriptor v)
|
---|
| 412 | { return get(vertex_bundle, *this)[v]; }
|
---|
| 413 |
|
---|
| 414 | const vertex_bundled& operator[](vertex_descriptor v) const
|
---|
| 415 | { return get(vertex_bundle, *this)[v]; }
|
---|
| 416 |
|
---|
| 417 | edge_bundled& operator[](edge_descriptor e)
|
---|
| 418 | { return get(edge_bundle, *this)[e]; }
|
---|
| 419 |
|
---|
| 420 | const edge_bundled& operator[](edge_descriptor e) const
|
---|
| 421 | { return get(edge_bundle, *this)[e]; }
|
---|
| 422 | #endif
|
---|
| 423 |
|
---|
| 424 | // protected: (would be protected if friends were more portable)
|
---|
| 425 | GraphProperty m_property;
|
---|
| 426 | };
|
---|
| 427 |
|
---|
| 428 | template <class OEL, class VL, class DirS, class VP,class EP, class GP,
|
---|
| 429 | class EL, class Tag, class Value>
|
---|
| 430 | inline void
|
---|
| 431 | set_property(adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>& g, Tag,
|
---|
| 432 | const Value& value) {
|
---|
| 433 | get_property_value(g.m_property, Tag()) = value;;
|
---|
| 434 | }
|
---|
| 435 |
|
---|
| 436 | template <class OEL, class VL, class DirS, class VP, class EP, class GP,
|
---|
| 437 | class Tag, class EL>
|
---|
| 438 | inline
|
---|
| 439 | typename graph_property<adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>, Tag>::type&
|
---|
| 440 | get_property(adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>& g, Tag) {
|
---|
| 441 | return get_property_value(g.m_property, Tag());
|
---|
| 442 | }
|
---|
| 443 |
|
---|
| 444 | template <class OEL, class VL, class DirS, class VP, class EP, class GP,
|
---|
| 445 | class Tag, class EL>
|
---|
| 446 | inline
|
---|
| 447 | const
|
---|
| 448 | typename graph_property<adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>, Tag>::type&
|
---|
| 449 | get_property(const adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>& g, Tag) {
|
---|
| 450 | return get_property_value(g.m_property, Tag());
|
---|
| 451 | }
|
---|
| 452 |
|
---|
| 453 | // dwa 09/25/00 - needed to be more explicit so reverse_graph would work.
|
---|
| 454 | template <class Directed, class Vertex,
|
---|
| 455 | class OutEdgeListS,
|
---|
| 456 | class VertexListS,
|
---|
| 457 | class DirectedS,
|
---|
| 458 | class VertexProperty,
|
---|
| 459 | class EdgeProperty,
|
---|
| 460 | class GraphProperty, class EdgeListS>
|
---|
| 461 | inline Vertex
|
---|
| 462 | source(const detail::edge_base<Directed,Vertex>& e,
|
---|
| 463 | const adjacency_list<OutEdgeListS, VertexListS, DirectedS,
|
---|
| 464 | VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&)
|
---|
| 465 | {
|
---|
| 466 | return e.m_source;
|
---|
| 467 | }
|
---|
| 468 |
|
---|
| 469 | template <class Directed, class Vertex, class OutEdgeListS,
|
---|
| 470 | class VertexListS, class DirectedS, class VertexProperty,
|
---|
| 471 | class EdgeProperty, class GraphProperty, class EdgeListS>
|
---|
| 472 | inline Vertex
|
---|
| 473 | target(const detail::edge_base<Directed,Vertex>& e,
|
---|
| 474 | const adjacency_list<OutEdgeListS, VertexListS, DirectedS,
|
---|
| 475 | VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&)
|
---|
| 476 | {
|
---|
| 477 | return e.m_target;
|
---|
| 478 | }
|
---|
| 479 |
|
---|
| 480 | // Support for bundled properties
|
---|
| 481 | #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
|
---|
| 482 | template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,
|
---|
| 483 | typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle>
|
---|
| 484 | inline
|
---|
| 485 | typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
|
---|
| 486 | GraphProperty, EdgeListS>, T Bundle::*>::type
|
---|
| 487 | get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
|
---|
| 488 | GraphProperty, EdgeListS>& g)
|
---|
| 489 | {
|
---|
| 490 | typedef typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty,
|
---|
| 491 | EdgeProperty, GraphProperty, EdgeListS>, T Bundle::*>::type
|
---|
| 492 | result_type;
|
---|
| 493 | return result_type(&g, p);
|
---|
| 494 | }
|
---|
| 495 |
|
---|
| 496 | template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,
|
---|
| 497 | typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle>
|
---|
| 498 | inline
|
---|
| 499 | typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
|
---|
| 500 | GraphProperty, EdgeListS>, T Bundle::*>::const_type
|
---|
| 501 | get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
|
---|
| 502 | GraphProperty, EdgeListS> const & g)
|
---|
| 503 | {
|
---|
| 504 | typedef typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty,
|
---|
| 505 | EdgeProperty, GraphProperty, EdgeListS>, T Bundle::*>::const_type
|
---|
| 506 | result_type;
|
---|
| 507 | return result_type(&g, p);
|
---|
| 508 | }
|
---|
| 509 |
|
---|
| 510 | template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,
|
---|
| 511 | typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle,
|
---|
| 512 | typename Key>
|
---|
| 513 | inline T
|
---|
| 514 | get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
|
---|
| 515 | GraphProperty, EdgeListS> const & g, const Key& key)
|
---|
| 516 | {
|
---|
| 517 | return get(get(p, g), key);
|
---|
| 518 | }
|
---|
| 519 |
|
---|
| 520 | template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,
|
---|
| 521 | typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle,
|
---|
| 522 | typename Key>
|
---|
| 523 | inline void
|
---|
| 524 | put(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
|
---|
| 525 | GraphProperty, EdgeListS>& g, const Key& key, const T& value)
|
---|
| 526 | {
|
---|
| 527 | put(get(p, g), key, value);
|
---|
| 528 | }
|
---|
| 529 |
|
---|
| 530 | #endif
|
---|
| 531 |
|
---|
| 532 |
|
---|
| 533 | } // namespace boost
|
---|
| 534 |
|
---|
| 535 |
|
---|
| 536 | #endif // BOOST_GRAPH_ADJACENCY_LIST_HPP
|
---|