williamr@2: //======================================================================= williamr@2: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. williamr@2: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek williamr@2: // williamr@2: // Distributed under the Boost Software License, Version 1.0. (See williamr@2: // accompanying file LICENSE_1_0.txt or copy at williamr@2: // http://www.boost.org/LICENSE_1_0.txt) williamr@2: //======================================================================= williamr@2: williamr@4: #ifndef BOOST_GRAPH_ADJACENCY_LIST_HPP williamr@4: #define BOOST_GRAPH_ADJACENCY_LIST_HPP williamr@2: williamr@4: williamr@2: #include williamr@4: williamr@4: #include williamr@4: #include williamr@4: #include williamr@4: williamr@4: #if !defined BOOST_NO_HASH williamr@4: # ifdef BOOST_HASH_SET_HEADER williamr@4: # include BOOST_HASH_SET_HEADER williamr@4: # else williamr@4: # include williamr@4: # endif williamr@4: #endif williamr@4: williamr@4: #if !defined BOOST_NO_SLIST williamr@4: # ifdef BOOST_SLIST_HEADER williamr@4: # include BOOST_SLIST_HEADER williamr@4: # else williamr@4: # include williamr@4: # endif williamr@4: #endif williamr@4: williamr@4: #include williamr@4: #include williamr@4: #include williamr@4: #include williamr@4: #include williamr@4: #include williamr@2: #include williamr@2: #include williamr@2: williamr@2: namespace boost { williamr@2: williamr@4: //=========================================================================== williamr@4: // Selectors for the VertexList and EdgeList template parameters of williamr@4: // adjacency_list, and the container_gen traits class which is used williamr@4: // to map the selectors to the container type used to implement the williamr@4: // graph. williamr@4: // williamr@4: // The main container_gen traits class uses partial specialization, williamr@4: // so we also include a workaround. williamr@4: williamr@4: #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION williamr@4: williamr@4: #if !defined BOOST_NO_SLIST williamr@4: struct slistS {}; williamr@4: #endif williamr@4: williamr@4: struct vecS { }; williamr@4: struct listS { }; williamr@4: struct setS { }; williamr@4: struct multisetS { }; williamr@4: struct mapS { }; williamr@4: #if !defined BOOST_NO_HASH williamr@4: struct hash_mapS { }; williamr@4: struct hash_setS { }; williamr@4: #endif williamr@4: williamr@4: template williamr@4: struct container_gen { }; williamr@4: williamr@4: template williamr@4: struct container_gen { williamr@4: typedef std::list type; williamr@4: }; williamr@4: #if !defined BOOST_NO_SLIST williamr@4: template williamr@4: struct container_gen { williamr@4: typedef BOOST_STD_EXTENSION_NAMESPACE::slist type; williamr@4: }; williamr@4: #endif williamr@4: template williamr@4: struct container_gen { williamr@4: typedef std::vector type; williamr@4: }; williamr@4: williamr@4: template williamr@4: struct container_gen { williamr@4: typedef std::set type; williamr@4: }; williamr@4: williamr@4: template williamr@4: struct container_gen { williamr@4: typedef std::set type; williamr@4: }; williamr@4: williamr@4: template williamr@4: struct container_gen { williamr@4: typedef std::multiset type; williamr@4: }; williamr@4: williamr@4: #if !defined BOOST_NO_HASH williamr@4: template williamr@4: struct container_gen { williamr@4: typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set type; williamr@4: }; williamr@4: williamr@4: template williamr@4: struct container_gen { williamr@4: typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set type; williamr@4: }; williamr@4: #endif williamr@4: williamr@4: #else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION williamr@4: williamr@4: #if !defined BOOST_NO_SLIST williamr@4: struct slistS { williamr@4: template williamr@4: struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::slist type; }; williamr@4: }; williamr@4: #endif williamr@4: williamr@4: struct vecS { williamr@4: template williamr@4: struct bind_ { typedef std::vector type; }; williamr@4: }; williamr@4: williamr@4: struct listS { williamr@4: template williamr@4: struct bind_ { typedef std::list type; }; williamr@4: }; williamr@4: williamr@4: struct setS { williamr@4: template williamr@4: struct bind_ { typedef std::set > type; }; williamr@4: }; williamr@4: williamr@4: struct multisetS { williamr@4: template williamr@4: struct bind_ { typedef std::multiset > type; }; williamr@4: }; williamr@4: williamr@4: #if !defined BOOST_NO_HASH williamr@4: struct hash_setS { williamr@4: template williamr@4: struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set > type; }; williamr@4: }; williamr@4: #endif williamr@4: williamr@4: struct mapS { williamr@4: template williamr@4: struct bind_ { typedef std::set > type; }; williamr@4: }; williamr@4: williamr@4: #if !defined BOOST_NO_HASH williamr@4: struct hash_mapS { williamr@4: template williamr@4: struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set > type; }; williamr@4: }; williamr@4: #endif williamr@4: williamr@4: template struct container_selector { williamr@4: typedef vecS type; williamr@4: }; williamr@4: williamr@4: #define BOOST_CONTAINER_SELECTOR(NAME) \ williamr@4: template <> struct container_selector { \ williamr@4: typedef NAME type; \ williamr@4: } williamr@4: williamr@4: BOOST_CONTAINER_SELECTOR(vecS); williamr@4: BOOST_CONTAINER_SELECTOR(listS); williamr@4: BOOST_CONTAINER_SELECTOR(mapS); williamr@4: BOOST_CONTAINER_SELECTOR(setS); williamr@4: BOOST_CONTAINER_SELECTOR(multisetS); williamr@4: #if !defined BOOST_NO_HASH williamr@4: BOOST_CONTAINER_SELECTOR(hash_mapS); williamr@4: #endif williamr@4: #if !defined BOOST_NO_SLIST williamr@4: BOOST_CONTAINER_SELECTOR(slistS); williamr@4: #endif williamr@4: williamr@4: template williamr@4: struct container_gen { williamr@4: typedef typename container_selector::type Select; williamr@4: typedef typename Select:: template bind_::type type; williamr@4: }; williamr@4: williamr@4: #endif // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION williamr@4: williamr@4: template williamr@4: struct parallel_edge_traits { }; williamr@4: williamr@4: template <> williamr@4: struct parallel_edge_traits { williamr@4: typedef allow_parallel_edge_tag type; }; williamr@4: williamr@4: template <> williamr@4: struct parallel_edge_traits { williamr@4: typedef allow_parallel_edge_tag type; }; williamr@4: williamr@4: #if !defined BOOST_NO_SLIST williamr@4: template <> williamr@4: struct parallel_edge_traits { williamr@4: typedef allow_parallel_edge_tag type; }; williamr@4: #endif williamr@4: williamr@4: template <> williamr@4: struct parallel_edge_traits { williamr@4: typedef disallow_parallel_edge_tag type; }; williamr@4: williamr@4: template <> williamr@4: struct parallel_edge_traits { williamr@4: typedef allow_parallel_edge_tag type; }; williamr@4: williamr@4: #if !defined BOOST_NO_HASH williamr@4: template <> williamr@4: struct parallel_edge_traits { williamr@4: typedef disallow_parallel_edge_tag type; williamr@4: }; williamr@4: #endif williamr@4: williamr@4: // mapS is obsolete, replaced with setS williamr@4: template <> williamr@4: struct parallel_edge_traits { williamr@4: typedef disallow_parallel_edge_tag type; }; williamr@4: williamr@4: #if !defined BOOST_NO_HASH williamr@4: template <> williamr@4: struct parallel_edge_traits { williamr@4: typedef disallow_parallel_edge_tag type; williamr@4: }; williamr@4: #endif williamr@4: williamr@2: namespace detail { williamr@4: template struct is_random_access { williamr@4: enum { value = false}; williamr@4: typedef false_type type; williamr@2: }; williamr@2: template <> williamr@4: struct is_random_access { williamr@4: enum { value = true }; williamr@4: typedef true_type type; williamr@2: }; williamr@2: williamr@2: } // namespace detail williamr@2: williamr@2: williamr@2: williamr@4: //=========================================================================== williamr@4: // The adjacency_list_traits class, which provides a way to access williamr@4: // some of the associated types of an adjacency_list type without williamr@4: // having to first create the adjacency_list type. This is useful williamr@4: // when trying to create interior vertex or edge properties who's williamr@4: // value type is a vertex or edge descriptor. williamr@2: williamr@4: template williamr@4: struct adjacency_list_traits williamr@4: { williamr@4: typedef typename detail::is_random_access::type williamr@4: is_rand_access; williamr@4: typedef typename DirectedS::is_bidir_t is_bidir; williamr@4: typedef typename DirectedS::is_directed_t is_directed; williamr@2: williamr@4: typedef typename boost::ct_if_t::type williamr@4: >::type directed_category; williamr@2: williamr@4: typedef typename parallel_edge_traits::type williamr@4: edge_parallel_category; williamr@2: williamr@4: typedef void* vertex_ptr; williamr@4: typedef typename boost::ct_if_t::type vertex_descriptor; williamr@4: typedef detail::edge_desc_impl williamr@4: edge_descriptor; williamr@2: }; williamr@2: williamr@2: } // namespace boost williamr@2: williamr@4: #include williamr@2: williamr@4: namespace boost { williamr@4: williamr@4: //=========================================================================== williamr@4: // The adjacency_list class. williamr@4: // williamr@4: williamr@4: template williamr@4: class adjacency_list williamr@4: : public detail::adj_list_gen< williamr@4: adjacency_list, williamr@4: VertexListS, OutEdgeListS, DirectedS, williamr@4: #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES) williamr@4: typename detail::retag_property_list::type, williamr@4: typename detail::retag_property_list::type, williamr@4: #else williamr@4: VertexProperty, EdgeProperty, williamr@4: #endif williamr@4: GraphProperty, EdgeListS>::type williamr@2: { williamr@4: #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES) williamr@4: typedef typename detail::retag_property_list::retagged williamr@4: maybe_vertex_bundled; williamr@2: williamr@4: typedef typename detail::retag_property_list::retagged williamr@4: maybe_edge_bundled; williamr@4: #endif williamr@4: williamr@4: public: williamr@4: #if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES) williamr@4: typedef typename detail::retag_property_list::type williamr@4: vertex_property_type; williamr@4: typedef typename detail::retag_property_list::type williamr@4: edge_property_type; williamr@4: williamr@4: // The types that are actually bundled williamr@4: typedef typename ct_if<(is_same::value), williamr@4: no_vertex_bundle, williamr@4: maybe_vertex_bundled>::type vertex_bundled; williamr@4: typedef typename ct_if<(is_same::value), williamr@4: no_edge_bundle, williamr@4: maybe_edge_bundled>::type edge_bundled; williamr@4: #else williamr@4: typedef VertexProperty vertex_property_type; williamr@4: typedef EdgeProperty edge_property_type; williamr@4: typedef no_vertex_bundle vertex_bundled; williamr@4: typedef no_edge_bundle edge_bundled; williamr@4: #endif williamr@4: williamr@4: private: williamr@4: typedef adjacency_list self; williamr@4: typedef typename detail::adj_list_gen< williamr@4: self, VertexListS, OutEdgeListS, DirectedS, williamr@4: vertex_property_type, edge_property_type, GraphProperty, EdgeListS williamr@4: >::type Base; williamr@4: williamr@4: public: williamr@4: typedef typename Base::stored_vertex stored_vertex; williamr@4: typedef typename Base::vertices_size_type vertices_size_type; williamr@4: typedef typename Base::edges_size_type edges_size_type; williamr@4: typedef typename Base::degree_size_type degree_size_type; williamr@4: typedef typename Base::vertex_descriptor vertex_descriptor; williamr@4: typedef typename Base::edge_descriptor edge_descriptor; williamr@4: typedef OutEdgeListS out_edge_list_selector; williamr@4: typedef VertexListS vertex_list_selector; williamr@4: typedef DirectedS directed_selector; williamr@4: typedef EdgeListS edge_list_selector; williamr@4: williamr@4: typedef GraphProperty graph_property_type; williamr@4: williamr@4: inline adjacency_list(const GraphProperty& p = GraphProperty()) williamr@4: : m_property(p) { } williamr@4: williamr@4: inline adjacency_list(const adjacency_list& x) williamr@4: : Base(x), m_property(x.m_property) { } williamr@4: williamr@4: inline adjacency_list& operator=(const adjacency_list& x) { williamr@4: // TBD: probably should give the strong guarantee williamr@4: if (&x != this) { williamr@4: Base::operator=(x); williamr@4: m_property = x.m_property; williamr@4: } williamr@4: return *this; williamr@2: } williamr@4: williamr@4: // Required by Mutable Graph williamr@4: inline adjacency_list(vertices_size_type num_vertices, williamr@4: const GraphProperty& p = GraphProperty()) williamr@4: : Base(num_vertices), m_property(p) { } williamr@4: williamr@4: #if !defined(BOOST_MSVC) || BOOST_MSVC >= 1300 williamr@4: // Required by Iterator Constructible Graph williamr@4: template williamr@4: inline adjacency_list(EdgeIterator first, EdgeIterator last, williamr@4: vertices_size_type n, williamr@4: edges_size_type = 0, williamr@4: const GraphProperty& p = GraphProperty()) williamr@4: : Base(n, first, last), m_property(p) { } williamr@4: williamr@4: template williamr@4: inline adjacency_list(EdgeIterator first, EdgeIterator last, williamr@4: EdgePropertyIterator ep_iter, williamr@4: vertices_size_type n, williamr@4: edges_size_type = 0, williamr@4: const GraphProperty& p = GraphProperty()) williamr@4: : Base(n, first, last, ep_iter), m_property(p) { } williamr@4: #endif williamr@4: williamr@4: void swap(adjacency_list& x) { williamr@4: // Is there a more efficient way to do this? williamr@4: adjacency_list tmp(x); williamr@4: x = *this; williamr@4: *this = tmp; williamr@4: } williamr@4: williamr@4: #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES williamr@4: // Directly access a vertex or edge bundle williamr@4: vertex_bundled& operator[](vertex_descriptor v) williamr@4: { return get(vertex_bundle, *this)[v]; } williamr@4: williamr@4: const vertex_bundled& operator[](vertex_descriptor v) const williamr@4: { return get(vertex_bundle, *this)[v]; } williamr@4: williamr@4: edge_bundled& operator[](edge_descriptor e) williamr@4: { return get(edge_bundle, *this)[e]; } williamr@4: williamr@4: const edge_bundled& operator[](edge_descriptor e) const williamr@4: { return get(edge_bundle, *this)[e]; } williamr@4: #endif williamr@4: williamr@4: // protected: (would be protected if friends were more portable) williamr@4: GraphProperty m_property; williamr@2: }; williamr@2: williamr@4: template williamr@4: inline void williamr@4: set_property(adjacency_list& g, Tag, williamr@4: const Value& value) { williamr@4: get_property_value(g.m_property, Tag()) = value;; williamr@4: } williamr@4: williamr@4: template williamr@4: inline williamr@4: typename graph_property, Tag>::type& williamr@4: get_property(adjacency_list& g, Tag) { williamr@4: return get_property_value(g.m_property, Tag()); williamr@4: } williamr@4: williamr@4: template williamr@4: inline williamr@4: const williamr@4: typename graph_property, Tag>::type& williamr@4: get_property(const adjacency_list& g, Tag) { williamr@4: return get_property_value(g.m_property, Tag()); williamr@4: } williamr@4: williamr@4: // dwa 09/25/00 - needed to be more explicit so reverse_graph would work. williamr@4: template williamr@4: inline Vertex williamr@4: source(const detail::edge_base& e, williamr@4: const adjacency_list&) williamr@2: { williamr@4: return e.m_source; williamr@4: } williamr@2: williamr@4: template williamr@4: inline Vertex williamr@4: target(const detail::edge_base& e, williamr@4: const adjacency_list&) williamr@2: { williamr@4: return e.m_target; williamr@4: } williamr@2: williamr@4: // Support for bundled properties williamr@4: #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES williamr@4: template williamr@4: inline williamr@4: typename property_map, T Bundle::*>::type williamr@4: get(T Bundle::* p, adjacency_list& g) williamr@4: { williamr@4: typedef typename property_map, T Bundle::*>::type williamr@4: result_type; williamr@4: return result_type(&g, p); williamr@4: } williamr@4: williamr@4: template williamr@4: inline williamr@4: typename property_map, T Bundle::*>::const_type williamr@4: get(T Bundle::* p, adjacency_list const & g) williamr@4: { williamr@4: typedef typename property_map, T Bundle::*>::const_type williamr@4: result_type; williamr@4: return result_type(&g, p); williamr@4: } williamr@4: williamr@4: template williamr@4: inline T williamr@4: get(T Bundle::* p, adjacency_list const & g, const Key& key) williamr@4: { williamr@4: return get(get(p, g), key); williamr@4: } williamr@4: williamr@4: template williamr@4: inline void williamr@4: put(T Bundle::* p, adjacency_list& g, const Key& key, const T& value) williamr@4: { williamr@4: put(get(p, g), key, value); williamr@4: } williamr@4: williamr@2: #endif williamr@2: williamr@2: williamr@4: } // namespace boost williamr@2: williamr@2: williamr@4: #endif // BOOST_GRAPH_ADJACENCY_LIST_HPP