boost/graph/graph_archetypes.hpp

   1 //=======================================================================
   2 // Copyright 2002 Indiana University.
   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_ARCHETYPES_HPP
  11 #define BOOST_GRAPH_ARCHETYPES_HPP
  12
  13 #include <boost/property_map/property_map.hpp>
  14 #include <boost/concept_archetype.hpp>
  15
  16 namespace boost { // should use a different namespace for this
  17
  18   namespace detail {
  19     struct null_graph_archetype : public null_archetype<> {
  20       struct traversal_category { };
  21     };
  22   }
  23
  24   //===========================================================================
  25   template <typename Vertex, typename Directed, typename ParallelCategory,
  26     typename Base = detail::null_graph_archetype >
  27   struct incidence_graph_archetype : public Base
  28   {
  29     typedef typename Base::traversal_category base_trav_cat;
  30     struct traversal_category
  31       : public incidence_graph_tag, public base_trav_cat { };
  32 #if 0
  33     typedef immutable_graph_tag mutability_category;
  34 #endif
  35     typedef Vertex vertex_descriptor;
  36     typedef unsigned int degree_size_type;
  37     typedef unsigned int vertices_size_type;
  38     typedef unsigned int edges_size_type;
  39     struct edge_descriptor {
  40       edge_descriptor() { }
  41       edge_descriptor(const detail::dummy_constructor&) { }
  42       bool operator==(const edge_descriptor&) const { return false; }
  43       bool operator!=(const edge_descriptor&) const { return false; }
  44     };
  45     typedef input_iterator_archetype<edge_descriptor> out_edge_iterator;
  46
  47     typedef Directed directed_category;
  48     typedef ParallelCategory edge_parallel_category;
  49
  50     typedef void adjacency_iterator;
  51     typedef void in_edge_iterator;
  52     typedef void vertex_iterator;
  53     typedef void edge_iterator;
  54   };
  55   template <typename V, typename D, typename P, typename B>
  56   V source(const typename incidence_graph_archetype<V,D,P,B>::edge_descriptor&,
  57            const incidence_graph_archetype<V,D,P,B>& )
  58   {
  59     return V(static_object<detail::dummy_constructor>::get());
  60   }
  61   template <typename V, typename D, typename P, typename B>
  62   V target(const typename incidence_graph_archetype<V,D,P,B>::edge_descriptor&,
  63            const incidence_graph_archetype<V,D,P,B>& )
  64   {
  65     return V(static_object<detail::dummy_constructor>::get());
  66   }
  67
  68   template <typename V, typename D, typename P, typename B>
  69   std::pair<typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator,
  70             typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator>
  71   out_edges(const V&, const incidence_graph_archetype<V,D,P,B>& )
  72   {
  73     typedef typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator Iter;
  74     return std::make_pair(Iter(), Iter());
  75   }
  76
  77   template <typename V, typename D, typename P, typename B>
  78   typename incidence_graph_archetype<V,D,P,B>::degree_size_type
  79   out_degree(const V&, const incidence_graph_archetype<V,D,P,B>& )
  80   {
  81     return 0;
  82   }
  83
  84   //===========================================================================
  85   template <typename Vertex, typename Directed, typename ParallelCategory,
  86     typename Base = detail::null_graph_archetype >
  87   struct adjacency_graph_archetype : public Base
  88   {
  89     typedef typename Base::traversal_category base_trav_cat;
  90     struct traversal_category
  91       : public adjacency_graph_tag, public base_trav_cat { };
  92     typedef Vertex vertex_descriptor;
  93     typedef unsigned int degree_size_type;
  94     typedef unsigned int vertices_size_type;
  95     typedef unsigned int edges_size_type;
  96     typedef void edge_descriptor;
  97     typedef input_iterator_archetype<Vertex> adjacency_iterator;
  98
  99     typedef Directed directed_category;
 100     typedef ParallelCategory edge_parallel_category;
 101
 102     typedef void in_edge_iterator;
 103     typedef void out_edge_iterator;
 104     typedef void vertex_iterator;
 105     typedef void edge_iterator;
 106   };
 107
 108   template <typename V, typename D, typename P, typename B>
 109   std::pair<typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator,
 110             typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator>
 111   adjacent_vertices(const V&, const adjacency_graph_archetype<V,D,P,B>& )
 112   {
 113     typedef typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator Iter;
 114     return std::make_pair(Iter(), Iter());
 115   }
 116
 117   template <typename V, typename D, typename P, typename B>
 118   typename adjacency_graph_archetype<V,D,P,B>::degree_size_type
 119   out_degree(const V&, const adjacency_graph_archetype<V,D,P,B>& )
 120   {
 121     return 0;
 122   }
 123
 124   //===========================================================================
 125   template <typename Vertex, typename Directed, typename ParallelCategory,
 126     typename Base = detail::null_graph_archetype >
 127   struct vertex_list_graph_archetype : public Base
 128   {
 129     typedef incidence_graph_archetype<Vertex, Directed, ParallelCategory>
 130       Incidence;
 131     typedef adjacency_graph_archetype<Vertex, Directed, ParallelCategory>
 132       Adjacency;
 133
 134     typedef typename Base::traversal_category base_trav_cat;
 135     struct traversal_category
 136       : public vertex_list_graph_tag, public base_trav_cat { };
 137 #if 0
 138     typedef immutable_graph_tag mutability_category;
 139 #endif
 140     typedef Vertex vertex_descriptor;
 141     typedef unsigned int degree_size_type;
 142     typedef typename Incidence::edge_descriptor edge_descriptor;
 143     typedef typename Incidence::out_edge_iterator out_edge_iterator;
 144     typedef typename Adjacency::adjacency_iterator adjacency_iterator;
 145
 146     typedef input_iterator_archetype<Vertex> vertex_iterator;
 147     typedef unsigned int vertices_size_type;
 148     typedef unsigned int edges_size_type;
 149
 150     typedef Directed directed_category;
 151     typedef ParallelCategory edge_parallel_category;
 152
 153     typedef void in_edge_iterator;
 154     typedef void edge_iterator;
 155   };
 156
 157   template <typename V, typename D, typename P, typename B>
 158   std::pair<typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator,
 159             typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator>
 160   vertices(const vertex_list_graph_archetype<V,D,P,B>& )
 161   {
 162     typedef typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator Iter;
 163     return std::make_pair(Iter(), Iter());
 164   }
 165
 166   template <typename V, typename D, typename P, typename B>
 167   typename vertex_list_graph_archetype<V,D,P,B>::vertices_size_type
 168   num_vertices(const vertex_list_graph_archetype<V,D,P,B>& )
 169   {
 170     return 0;
 171   }
 172
 173   // ambiguously inherited from incidence graph and adjacency graph
 174   template <typename V, typename D, typename P, typename B>
 175   typename vertex_list_graph_archetype<V,D,P,B>::degree_size_type
 176   out_degree(const V&, const vertex_list_graph_archetype<V,D,P,B>& )
 177   {
 178     return 0;
 179   }
 180
 181   //===========================================================================
 182
 183   struct property_graph_archetype_tag { };
 184
 185   template <typename GraphArchetype, typename Property, typename ValueArch>
 186   struct property_graph_archetype : public GraphArchetype
 187   {
 188     typedef property_graph_archetype_tag graph_tag;
 189     typedef ValueArch vertex_property_type;
 190     typedef ValueArch edge_property_type;
 191   };
 192
 193   struct choose_edge_property_map_archetype {
 194     template <typename Graph, typename Property, typename Tag>
 195     struct bind_ {
 196       typedef mutable_lvalue_property_map_archetype
 197         <typename Graph::edge_descriptor, Property> type;
 198       typedef lvalue_property_map_archetype
 199         <typename Graph::edge_descriptor, Property> const_type;
 200     };
 201   };
 202   template <>
 203   struct edge_property_selector<property_graph_archetype_tag> {
 204     typedef choose_edge_property_map_archetype type;
 205   };
 206
 207   struct choose_vertex_property_map_archetype {
 208     template <typename Graph, typename Property, typename Tag>
 209     struct bind_ {
 210       typedef mutable_lvalue_property_map_archetype
 211         <typename Graph::vertex_descriptor, Property> type;
 212       typedef lvalue_property_map_archetype
 213         <typename Graph::vertex_descriptor, Property> const_type;
 214     };
 215   };
 216
 217   template <>
 218   struct vertex_property_selector<property_graph_archetype_tag> {
 219     typedef choose_vertex_property_map_archetype type;
 220   };
 221
 222   template <typename G, typename P, typename V>
 223   typename property_map<property_graph_archetype<G, P, V>, P>::type
 224   get(P, property_graph_archetype<G, P, V>&) {
 225     typename property_map<property_graph_archetype<G, P, V>, P>::type pmap;
 226     return pmap;
 227   }
 228
 229   template <typename G, typename P, typename V>
 230   typename property_map<property_graph_archetype<G, P, V>, P>::const_type
 231   get(P, const property_graph_archetype<G, P, V>&) {
 232     typename property_map<property_graph_archetype<G, P, V>, P>::const_type pmap;
 233     return pmap;
 234   }
 235
 236   template <typename G, typename P, typename K, typename V>
 237   typename property_traits<typename property_map<property_graph_archetype<G, P, V>, P>::const_type>::value_type
 238   get(P p, const property_graph_archetype<G, P, V>& g, K k) {
 239     return get( get(p, g), k);
 240   }
 241
 242   template <typename G, typename P, typename V, typename Key>
 243   void
 244   put(P p, property_graph_archetype<G, P, V>& g,
 245       const Key& key, const V& value)
 246   {
 247     typedef typename boost::property_map<property_graph_archetype<G, P, V>, P>::type Map;
 248     Map pmap = get(p, g);
 249     put(pmap, key, value);
 250   }
 251
 252   struct color_value_archetype {
 253     color_value_archetype() { }
 254     color_value_archetype(detail::dummy_constructor) { }
 255     bool operator==(const color_value_archetype& ) const { return true; }
 256     bool operator!=(const color_value_archetype& ) const { return true; }
 257   };
 258   template <>
 259   struct color_traits<color_value_archetype> {
 260     static color_value_archetype white()
 261     {
 262       return color_value_archetype
 263         (static_object<detail::dummy_constructor>::get());
 264     }
 265     static color_value_archetype gray()
 266     {
 267       return color_value_archetype
 268         (static_object<detail::dummy_constructor>::get());
 269     }
 270     static color_value_archetype black()
 271     {
 272       return color_value_archetype
 273         (static_object<detail::dummy_constructor>::get());
 274     }
 275   };
 276
 277   template <typename T>
 278   class buffer_archetype {
 279   public:
 280     void push(const T&) {}
 281     void pop() {}
 282     T& top() { return static_object<T>::get(); }
 283     const T& top() const { return static_object<T>::get(); }
 284     bool empty() const { return true; }
 285   };
 286
 287 } // namespace boost
 288
 289
 290 #endif // BOOST_GRAPH_ARCHETYPES_HPP