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