]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |