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