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 { |
42 | edge_descriptor() { } |
43 | edge_descriptor(const detail::dummy_constructor&) { } |
44 | bool operator==(const edge_descriptor&) const { return false; } |
45 | 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 | |
57 | 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> |
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 |
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 | |
111 | 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> |
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 |
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 | |
162 | 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> |
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 |
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 |
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 |
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 |
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 |
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 |
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 { |
261 | color_value_archetype() { } |
262 | color_value_archetype(detail::dummy_constructor) { } |
263 | bool operator==(const color_value_archetype& ) const { return true; } |
264 | bool operator!=(const color_value_archetype& ) const { return true; } |
265 | }; |
266 | template <> |
267 | struct color_traits<color_value_archetype> { |
268 | static color_value_archetype white() |
269 | { |
270 | return color_value_archetype |
271 | (static_object<detail::dummy_constructor>::get()); |
272 | } |
273 | static color_value_archetype gray() |
274 | { |
275 | return color_value_archetype |
276 | (static_object<detail::dummy_constructor>::get()); |
277 | } |
278 | 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: |
288 | void push(const T&) {} |
289 | void pop() {} |
290 | T& top() { return static_object<T>::get(); } |
291 | const T& top() const { return static_object<T>::get(); } |
292 | bool empty() const { return true; } |
293 | }; |
294 | |
295 | } // namespace boost |
296 | |
297 | |
298 | #endif // BOOST_GRAPH_ARCHETYPES_HPP |
299 | |