boost/graph/graph_archetypes.hpp

0001 //=======================================================================
0002 // Copyright 2002 Indiana University.
0003 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009
0010 #ifndef BOOST_GRAPH_ARCHETYPES_HPP
0011 #define BOOST_GRAPH_ARCHETYPES_HPP
0012
0013 #include <boost/property_map/property_map.hpp>
0014 #include <boost/concept_archetype.hpp>
0015 #include <boost/graph/graph_traits.hpp>
0016 #include <boost/graph/properties.hpp>
0017
0018 namespace boost
0019 { // should use a different namespace for this
0020
0021 namespace detail
0022 {
0023     struct null_graph_archetype : public null_archetype<>
0024     {
0025         struct traversal_category
0026         {
0027         };
0028     };
0029 }
0030
0031 //===========================================================================
0032 template < typename Vertex, typename Directed, typename ParallelCategory,
0033     typename Base = detail::null_graph_archetype >
0034 struct incidence_graph_archetype : public Base
0035 {
0036     typedef typename Base::traversal_category base_trav_cat;
0037     struct traversal_category : public incidence_graph_tag, public base_trav_cat
0038     {
0039     };
0040 #if 0
0041     typedef immutable_graph_tag mutability_category;
0042 #endif
0043     typedef Vertex vertex_descriptor;
0044     typedef unsigned int degree_size_type;
0045     typedef unsigned int vertices_size_type;
0046     typedef unsigned int edges_size_type;
0047     struct edge_descriptor
0048     {
0049         edge_descriptor() {}
0050         edge_descriptor(const detail::dummy_constructor&) {}
0051         bool operator==(const edge_descriptor&) const { return false; }
0052         bool operator!=(const edge_descriptor&) const { return false; }
0053     };
0054     typedef input_iterator_archetype< edge_descriptor > out_edge_iterator;
0055
0056     typedef Directed directed_category;
0057     typedef ParallelCategory edge_parallel_category;
0058
0059     typedef void adjacency_iterator;
0060     typedef void in_edge_iterator;
0061     typedef void vertex_iterator;
0062     typedef void edge_iterator;
0063
0064     static vertex_descriptor null_vertex() { return vertex_descriptor(); }
0065 };
0066 template < typename V, typename D, typename P, typename B >
0067 V source(
0068     const typename incidence_graph_archetype< V, D, P, B >::edge_descriptor&,
0069     const incidence_graph_archetype< V, D, P, B >&)
0070 {
0071     return V(static_object< detail::dummy_constructor >::get());
0072 }
0073 template < typename V, typename D, typename P, typename B >
0074 V target(
0075     const typename incidence_graph_archetype< V, D, P, B >::edge_descriptor&,
0076     const incidence_graph_archetype< V, D, P, B >&)
0077 {
0078     return V(static_object< detail::dummy_constructor >::get());
0079 }
0080
0081 template < typename V, typename D, typename P, typename B >
0082 std::pair< typename incidence_graph_archetype< V, D, P, B >::out_edge_iterator,
0083     typename incidence_graph_archetype< V, D, P, B >::out_edge_iterator >
0084 out_edges(const V&, const incidence_graph_archetype< V, D, P, B >&)
0085 {
0086     typedef typename incidence_graph_archetype< V, D, P, B >::out_edge_iterator
0087         Iter;
0088     return std::make_pair(Iter(), Iter());
0089 }
0090
0091 template < typename V, typename D, typename P, typename B >
0092 typename incidence_graph_archetype< V, D, P, B >::degree_size_type out_degree(
0093     const V&, const incidence_graph_archetype< V, D, P, B >&)
0094 {
0095     return 0;
0096 }
0097
0098 //===========================================================================
0099 template < typename Vertex, typename Directed, typename ParallelCategory,
0100     typename Base = detail::null_graph_archetype >
0101 struct adjacency_graph_archetype : public Base
0102 {
0103     typedef typename Base::traversal_category base_trav_cat;
0104     struct traversal_category : public adjacency_graph_tag, public base_trav_cat
0105     {
0106     };
0107     typedef Vertex vertex_descriptor;
0108     typedef unsigned int degree_size_type;
0109     typedef unsigned int vertices_size_type;
0110     typedef unsigned int edges_size_type;
0111     typedef void edge_descriptor;
0112     typedef input_iterator_archetype< Vertex > adjacency_iterator;
0113
0114     typedef Directed directed_category;
0115     typedef ParallelCategory edge_parallel_category;
0116
0117     typedef void in_edge_iterator;
0118     typedef void out_edge_iterator;
0119     typedef void vertex_iterator;
0120     typedef void edge_iterator;
0121
0122     static vertex_descriptor null_vertex() { return vertex_descriptor(); }
0123 };
0124
0125 template < typename V, typename D, typename P, typename B >
0126 std::pair< typename adjacency_graph_archetype< V, D, P, B >::adjacency_iterator,
0127     typename adjacency_graph_archetype< V, D, P, B >::adjacency_iterator >
0128 adjacent_vertices(const V&, const adjacency_graph_archetype< V, D, P, B >&)
0129 {
0130     typedef typename adjacency_graph_archetype< V, D, P, B >::adjacency_iterator
0131         Iter;
0132     return std::make_pair(Iter(), Iter());
0133 }
0134
0135 template < typename V, typename D, typename P, typename B >
0136 typename adjacency_graph_archetype< V, D, P, B >::degree_size_type out_degree(
0137     const V&, const adjacency_graph_archetype< V, D, P, B >&)
0138 {
0139     return 0;
0140 }
0141
0142 //===========================================================================
0143 template < typename Vertex, typename Directed, typename ParallelCategory,
0144     typename Base = detail::null_graph_archetype >
0145 struct vertex_list_graph_archetype : public Base
0146 {
0147     typedef incidence_graph_archetype< Vertex, Directed, ParallelCategory >
0148         Incidence;
0149     typedef adjacency_graph_archetype< Vertex, Directed, ParallelCategory >
0150         Adjacency;
0151
0152     typedef typename Base::traversal_category base_trav_cat;
0153     struct traversal_category : public vertex_list_graph_tag,
0154                                 public base_trav_cat
0155     {
0156     };
0157 #if 0
0158     typedef immutable_graph_tag mutability_category;
0159 #endif
0160     typedef Vertex vertex_descriptor;
0161     typedef unsigned int degree_size_type;
0162     typedef typename Incidence::edge_descriptor edge_descriptor;
0163     typedef typename Incidence::out_edge_iterator out_edge_iterator;
0164     typedef typename Adjacency::adjacency_iterator adjacency_iterator;
0165
0166     typedef input_iterator_archetype< Vertex > vertex_iterator;
0167     typedef unsigned int vertices_size_type;
0168     typedef unsigned int edges_size_type;
0169
0170     typedef Directed directed_category;
0171     typedef ParallelCategory edge_parallel_category;
0172
0173     typedef void in_edge_iterator;
0174     typedef void edge_iterator;
0175
0176     static vertex_descriptor null_vertex() { return vertex_descriptor(); }
0177 };
0178
0179 template < typename V, typename D, typename P, typename B >
0180 std::pair< typename vertex_list_graph_archetype< V, D, P, B >::vertex_iterator,
0181     typename vertex_list_graph_archetype< V, D, P, B >::vertex_iterator >
0182 vertices(const vertex_list_graph_archetype< V, D, P, B >&)
0183 {
0184     typedef typename vertex_list_graph_archetype< V, D, P, B >::vertex_iterator
0185         Iter;
0186     return std::make_pair(Iter(), Iter());
0187 }
0188
0189 template < typename V, typename D, typename P, typename B >
0190 typename vertex_list_graph_archetype< V, D, P, B >::vertices_size_type
0191 num_vertices(const vertex_list_graph_archetype< V, D, P, B >&)
0192 {
0193     return 0;
0194 }
0195
0196 // ambiguously inherited from incidence graph and adjacency graph
0197 template < typename V, typename D, typename P, typename B >
0198 typename vertex_list_graph_archetype< V, D, P, B >::degree_size_type out_degree(
0199     const V&, const vertex_list_graph_archetype< V, D, P, B >&)
0200 {
0201     return 0;
0202 }
0203
0204 //===========================================================================
0205
0206 struct property_graph_archetype_tag
0207 {
0208 };
0209
0210 template < typename GraphArchetype, typename Property, typename ValueArch >
0211 struct property_graph_archetype : public GraphArchetype
0212 {
0213     typedef property_graph_archetype_tag graph_tag;
0214     typedef ValueArch vertex_property_type;
0215     typedef ValueArch edge_property_type;
0216 };
0217
0218 struct choose_edge_property_map_archetype
0219 {
0220     template < typename Graph, typename Property, typename Tag > struct bind_
0221     {
0222         typedef mutable_lvalue_property_map_archetype<
0223             typename Graph::edge_descriptor, Property >
0224             type;
0225         typedef lvalue_property_map_archetype< typename Graph::edge_descriptor,
0226             Property >
0227             const_type;
0228     };
0229 };
0230 template <> struct edge_property_selector< property_graph_archetype_tag >
0231 {
0232     typedef choose_edge_property_map_archetype type;
0233 };
0234
0235 struct choose_vertex_property_map_archetype
0236 {
0237     template < typename Graph, typename Property, typename Tag > struct bind_
0238     {
0239         typedef mutable_lvalue_property_map_archetype<
0240             typename Graph::vertex_descriptor, Property >
0241             type;
0242         typedef lvalue_property_map_archetype<
0243             typename Graph::vertex_descriptor, Property >
0244             const_type;
0245     };
0246 };
0247
0248 template <> struct vertex_property_selector< property_graph_archetype_tag >
0249 {
0250     typedef choose_vertex_property_map_archetype type;
0251 };
0252
0253 template < typename G, typename P, typename V >
0254 typename property_map< property_graph_archetype< G, P, V >, P >::type get(
0255     P, property_graph_archetype< G, P, V >&)
0256 {
0257     typename property_map< property_graph_archetype< G, P, V >, P >::type pmap;
0258     return pmap;
0259 }
0260
0261 template < typename G, typename P, typename V >
0262 typename property_map< property_graph_archetype< G, P, V >, P >::const_type get(
0263     P, const property_graph_archetype< G, P, V >&)
0264 {
0265     typename property_map< property_graph_archetype< G, P, V >, P >::const_type
0266         pmap;
0267     return pmap;
0268 }
0269
0270 template < typename G, typename P, typename K, typename V >
0271 typename property_traits< typename property_map<
0272     property_graph_archetype< G, P, V >, P >::const_type >::value_type
0273 get(P p, const property_graph_archetype< G, P, V >& g, K k)
0274 {
0275     return get(get(p, g), k);
0276 }
0277
0278 template < typename G, typename P, typename V, typename Key >
0279 void put(
0280     P p, property_graph_archetype< G, P, V >& g, const Key& key, const V& value)
0281 {
0282     typedef typename boost::property_map< property_graph_archetype< G, P, V >,
0283         P >::type Map;
0284     Map pmap = get(p, g);
0285     put(pmap, key, value);
0286 }
0287
0288 struct color_value_archetype
0289 {
0290     color_value_archetype() {}
0291     color_value_archetype(detail::dummy_constructor) {}
0292     bool operator==(const color_value_archetype&) const { return true; }
0293     bool operator!=(const color_value_archetype&) const { return true; }
0294 };
0295 template <> struct color_traits< color_value_archetype >
0296 {
0297     static color_value_archetype white()
0298     {
0299         return color_value_archetype(
0300             static_object< detail::dummy_constructor >::get());
0301     }
0302     static color_value_archetype gray()
0303     {
0304         return color_value_archetype(
0305             static_object< detail::dummy_constructor >::get());
0306     }
0307     static color_value_archetype black()
0308     {
0309         return color_value_archetype(
0310             static_object< detail::dummy_constructor >::get());
0311     }
0312 };
0313
0314 template < typename T > class buffer_archetype
0315 {
0316 public:
0317     void push(const T&) {}
0318     void pop() {}
0319     T& top() { return static_object< T >::get(); }
0320     const T& top() const { return static_object< T >::get(); }
0321     bool empty() const { return true; }
0322 };
0323
0324 } // namespace boost
0325
0326 #endif // BOOST_GRAPH_ARCHETYPES_HPP