]>
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 | ||
f67539c2 TL |
18 | namespace boost |
19 | { // should use a different namespace for this | |
7c673cae | 20 | |
f67539c2 TL |
21 | namespace detail |
22 | { | |
23 | struct null_graph_archetype : public null_archetype<> | |
24 | { | |
25 | struct traversal_category | |
26 | { | |
27 | }; | |
7c673cae | 28 | }; |
f67539c2 TL |
29 | } |
30 | ||
31 | //=========================================================================== | |
32 | template < typename Vertex, typename Directed, typename ParallelCategory, | |
7c673cae | 33 | typename Base = detail::null_graph_archetype > |
f67539c2 TL |
34 | struct incidence_graph_archetype : public Base |
35 | { | |
7c673cae | 36 | typedef typename Base::traversal_category base_trav_cat; |
f67539c2 TL |
37 | struct traversal_category : public incidence_graph_tag, public base_trav_cat |
38 | { | |
39 | }; | |
7c673cae FG |
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; | |
f67539c2 TL |
47 | struct edge_descriptor |
48 | { | |
49 | edge_descriptor() {} | |
50 | edge_descriptor(const detail::dummy_constructor&) {} | |
51 | bool operator==(const edge_descriptor&) const { return false; } | |
52 | bool operator!=(const edge_descriptor&) const { return false; } | |
7c673cae | 53 | }; |
f67539c2 | 54 | typedef input_iterator_archetype< edge_descriptor > out_edge_iterator; |
7c673cae FG |
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 | ||
f67539c2 TL |
64 | 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 > | |
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; | |
7c673cae | 88 | return std::make_pair(Iter(), Iter()); |
f67539c2 TL |
89 | } |
90 | ||
91 | template < typename V, typename D, typename P, typename 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 | { | |
7c673cae | 95 | return 0; |
f67539c2 | 96 | } |
7c673cae | 97 | |
f67539c2 TL |
98 | //=========================================================================== |
99 | template < typename Vertex, typename Directed, typename ParallelCategory, | |
7c673cae | 100 | typename Base = detail::null_graph_archetype > |
f67539c2 TL |
101 | struct adjacency_graph_archetype : public Base |
102 | { | |
7c673cae | 103 | typedef typename Base::traversal_category base_trav_cat; |
f67539c2 TL |
104 | struct traversal_category : public adjacency_graph_tag, public base_trav_cat |
105 | { | |
106 | }; | |
7c673cae FG |
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; | |
f67539c2 | 112 | typedef input_iterator_archetype< Vertex > adjacency_iterator; |
7c673cae FG |
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 | ||
f67539c2 TL |
122 | 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 > | |
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; | |
7c673cae | 132 | return std::make_pair(Iter(), Iter()); |
f67539c2 | 133 | } |
7c673cae | 134 | |
f67539c2 TL |
135 | template < typename V, typename D, typename P, typename 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 | { | |
7c673cae | 139 | return 0; |
f67539c2 | 140 | } |
7c673cae | 141 | |
f67539c2 TL |
142 | //=========================================================================== |
143 | template < typename Vertex, typename Directed, typename ParallelCategory, | |
7c673cae | 144 | typename Base = detail::null_graph_archetype > |
f67539c2 TL |
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; | |
7c673cae FG |
151 | |
152 | typedef typename Base::traversal_category base_trav_cat; | |
f67539c2 TL |
153 | struct traversal_category : public vertex_list_graph_tag, |
154 | public base_trav_cat | |
155 | { | |
156 | }; | |
7c673cae FG |
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 | ||
f67539c2 | 166 | typedef input_iterator_archetype< Vertex > vertex_iterator; |
7c673cae FG |
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 | ||
f67539c2 TL |
176 | 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 > | |
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; | |
7c673cae | 186 | return std::make_pair(Iter(), Iter()); |
f67539c2 | 187 | } |
7c673cae | 188 | |
f67539c2 TL |
189 | template < typename V, typename D, typename P, typename B > |
190 | typename vertex_list_graph_archetype< V, D, P, B >::vertices_size_type | |
191 | num_vertices(const vertex_list_graph_archetype< V, D, P, B >&) | |
192 | { | |
7c673cae | 193 | return 0; |
f67539c2 | 194 | } |
7c673cae | 195 | |
f67539c2 TL |
196 | // ambiguously inherited from incidence graph and adjacency graph |
197 | template < typename V, typename D, typename P, typename 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 | { | |
7c673cae | 201 | return 0; |
f67539c2 | 202 | } |
7c673cae | 203 | |
f67539c2 | 204 | //=========================================================================== |
7c673cae | 205 | |
f67539c2 TL |
206 | struct property_graph_archetype_tag |
207 | { | |
208 | }; | |
7c673cae | 209 | |
f67539c2 TL |
210 | template < typename GraphArchetype, typename Property, typename ValueArch > |
211 | struct property_graph_archetype : public GraphArchetype | |
212 | { | |
7c673cae FG |
213 | typedef property_graph_archetype_tag graph_tag; |
214 | typedef ValueArch vertex_property_type; | |
215 | typedef ValueArch edge_property_type; | |
f67539c2 TL |
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; | |
7c673cae | 228 | }; |
f67539c2 TL |
229 | }; |
230 | template <> struct edge_property_selector< property_graph_archetype_tag > | |
231 | { | |
7c673cae | 232 | typedef choose_edge_property_map_archetype type; |
f67539c2 TL |
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; | |
7c673cae | 245 | }; |
f67539c2 | 246 | }; |
7c673cae | 247 | |
f67539c2 TL |
248 | template <> struct vertex_property_selector< property_graph_archetype_tag > |
249 | { | |
7c673cae | 250 | typedef choose_vertex_property_map_archetype type; |
f67539c2 | 251 | }; |
7c673cae | 252 | |
f67539c2 TL |
253 | template < typename G, typename P, typename 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 > | |
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; | |
7c673cae | 267 | return pmap; |
f67539c2 TL |
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 | |
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 > | |
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; | |
7c673cae FG |
284 | Map pmap = get(p, g); |
285 | put(pmap, key, value); | |
f67539c2 TL |
286 | } |
287 | ||
288 | struct color_value_archetype | |
289 | { | |
290 | color_value_archetype() {} | |
291 | color_value_archetype(detail::dummy_constructor) {} | |
292 | bool operator==(const color_value_archetype&) const { return true; } | |
293 | bool operator!=(const color_value_archetype&) const { return true; } | |
294 | }; | |
295 | template <> struct color_traits< color_value_archetype > | |
296 | { | |
7c673cae | 297 | static color_value_archetype white() |
f67539c2 TL |
298 | { |
299 | return color_value_archetype( | |
300 | static_object< detail::dummy_constructor >::get()); | |
7c673cae FG |
301 | } |
302 | static color_value_archetype gray() | |
303 | { | |
f67539c2 TL |
304 | return color_value_archetype( |
305 | static_object< detail::dummy_constructor >::get()); | |
7c673cae FG |
306 | } |
307 | static color_value_archetype black() | |
308 | { | |
f67539c2 TL |
309 | return color_value_archetype( |
310 | static_object< detail::dummy_constructor >::get()); | |
7c673cae | 311 | } |
f67539c2 | 312 | }; |
7c673cae | 313 | |
f67539c2 TL |
314 | template < typename T > class buffer_archetype |
315 | { | |
316 | public: | |
7c673cae FG |
317 | void push(const T&) {} |
318 | void pop() {} | |
f67539c2 TL |
319 | T& top() { return static_object< T >::get(); } |
320 | const T& top() const { return static_object< T >::get(); } | |
7c673cae | 321 | bool empty() const { return true; } |
f67539c2 | 322 | }; |
7c673cae | 323 | |
f67539c2 | 324 | } // namespace boost |
7c673cae FG |
325 | |
326 | #endif // BOOST_GRAPH_ARCHETYPES_HPP |