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
18namespace 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

source code of boost/boost/graph/graph_archetypes.hpp