1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
|
//=======================================================================
// Copyright 2002 Indiana University.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#ifndef BOOST_GRAPH_ARCHETYPES_HPP
#define BOOST_GRAPH_ARCHETYPES_HPP
#include <boost/property_map/property_map.hpp>
#include <boost/concept_archetype.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
namespace boost { // should use a different namespace for this
namespace detail {
struct null_graph_archetype : public null_archetype<> {
struct traversal_category { };
};
}
//===========================================================================
template <typename Vertex, typename Directed, typename ParallelCategory,
typename Base = detail::null_graph_archetype >
struct incidence_graph_archetype : public Base
{
typedef typename Base::traversal_category base_trav_cat;
struct traversal_category
: public incidence_graph_tag, public base_trav_cat { };
#if 0
typedef immutable_graph_tag mutability_category;
#endif
typedef Vertex vertex_descriptor;
typedef unsigned int degree_size_type;
typedef unsigned int vertices_size_type;
typedef unsigned int edges_size_type;
struct edge_descriptor {
edge_descriptor() { }
edge_descriptor(const detail::dummy_constructor&) { }
bool operator==(const edge_descriptor&) const { return false; }
bool operator!=(const edge_descriptor&) const { return false; }
};
typedef input_iterator_archetype<edge_descriptor> out_edge_iterator;
typedef Directed directed_category;
typedef ParallelCategory edge_parallel_category;
typedef void adjacency_iterator;
typedef void in_edge_iterator;
typedef void vertex_iterator;
typedef void edge_iterator;
static vertex_descriptor null_vertex() {return vertex_descriptor();}
};
template <typename V, typename D, typename P, typename B>
V source(const typename incidence_graph_archetype<V,D,P,B>::edge_descriptor&,
const incidence_graph_archetype<V,D,P,B>& )
{
return V(static_object<detail::dummy_constructor>::get());
}
template <typename V, typename D, typename P, typename B>
V target(const typename incidence_graph_archetype<V,D,P,B>::edge_descriptor&,
const incidence_graph_archetype<V,D,P,B>& )
{
return V(static_object<detail::dummy_constructor>::get());
}
template <typename V, typename D, typename P, typename B>
std::pair<typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator,
typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator>
out_edges(const V&, const incidence_graph_archetype<V,D,P,B>& )
{
typedef typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator Iter;
return std::make_pair(Iter(), Iter());
}
template <typename V, typename D, typename P, typename B>
typename incidence_graph_archetype<V,D,P,B>::degree_size_type
out_degree(const V&, const incidence_graph_archetype<V,D,P,B>& )
{
return 0;
}
//===========================================================================
template <typename Vertex, typename Directed, typename ParallelCategory,
typename Base = detail::null_graph_archetype >
struct adjacency_graph_archetype : public Base
{
typedef typename Base::traversal_category base_trav_cat;
struct traversal_category
: public adjacency_graph_tag, public base_trav_cat { };
typedef Vertex vertex_descriptor;
typedef unsigned int degree_size_type;
typedef unsigned int vertices_size_type;
typedef unsigned int edges_size_type;
typedef void edge_descriptor;
typedef input_iterator_archetype<Vertex> adjacency_iterator;
typedef Directed directed_category;
typedef ParallelCategory edge_parallel_category;
typedef void in_edge_iterator;
typedef void out_edge_iterator;
typedef void vertex_iterator;
typedef void edge_iterator;
static vertex_descriptor null_vertex() {return vertex_descriptor();}
};
template <typename V, typename D, typename P, typename B>
std::pair<typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator,
typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator>
adjacent_vertices(const V&, const adjacency_graph_archetype<V,D,P,B>& )
{
typedef typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator Iter;
return std::make_pair(Iter(), Iter());
}
template <typename V, typename D, typename P, typename B>
typename adjacency_graph_archetype<V,D,P,B>::degree_size_type
out_degree(const V&, const adjacency_graph_archetype<V,D,P,B>& )
{
return 0;
}
//===========================================================================
template <typename Vertex, typename Directed, typename ParallelCategory,
typename Base = detail::null_graph_archetype >
struct vertex_list_graph_archetype : public Base
{
typedef incidence_graph_archetype<Vertex, Directed, ParallelCategory>
Incidence;
typedef adjacency_graph_archetype<Vertex, Directed, ParallelCategory>
Adjacency;
typedef typename Base::traversal_category base_trav_cat;
struct traversal_category
: public vertex_list_graph_tag, public base_trav_cat { };
#if 0
typedef immutable_graph_tag mutability_category;
#endif
typedef Vertex vertex_descriptor;
typedef unsigned int degree_size_type;
typedef typename Incidence::edge_descriptor edge_descriptor;
typedef typename Incidence::out_edge_iterator out_edge_iterator;
typedef typename Adjacency::adjacency_iterator adjacency_iterator;
typedef input_iterator_archetype<Vertex> vertex_iterator;
typedef unsigned int vertices_size_type;
typedef unsigned int edges_size_type;
typedef Directed directed_category;
typedef ParallelCategory edge_parallel_category;
typedef void in_edge_iterator;
typedef void edge_iterator;
static vertex_descriptor null_vertex() {return vertex_descriptor();}
};
template <typename V, typename D, typename P, typename B>
std::pair<typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator,
typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator>
vertices(const vertex_list_graph_archetype<V,D,P,B>& )
{
typedef typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator Iter;
return std::make_pair(Iter(), Iter());
}
template <typename V, typename D, typename P, typename B>
typename vertex_list_graph_archetype<V,D,P,B>::vertices_size_type
num_vertices(const vertex_list_graph_archetype<V,D,P,B>& )
{
return 0;
}
// ambiguously inherited from incidence graph and adjacency graph
template <typename V, typename D, typename P, typename B>
typename vertex_list_graph_archetype<V,D,P,B>::degree_size_type
out_degree(const V&, const vertex_list_graph_archetype<V,D,P,B>& )
{
return 0;
}
//===========================================================================
struct property_graph_archetype_tag { };
template <typename GraphArchetype, typename Property, typename ValueArch>
struct property_graph_archetype : public GraphArchetype
{
typedef property_graph_archetype_tag graph_tag;
typedef ValueArch vertex_property_type;
typedef ValueArch edge_property_type;
};
struct choose_edge_property_map_archetype {
template <typename Graph, typename Property, typename Tag>
struct bind_ {
typedef mutable_lvalue_property_map_archetype
<typename Graph::edge_descriptor, Property> type;
typedef lvalue_property_map_archetype
<typename Graph::edge_descriptor, Property> const_type;
};
};
template <>
struct edge_property_selector<property_graph_archetype_tag> {
typedef choose_edge_property_map_archetype type;
};
struct choose_vertex_property_map_archetype {
template <typename Graph, typename Property, typename Tag>
struct bind_ {
typedef mutable_lvalue_property_map_archetype
<typename Graph::vertex_descriptor, Property> type;
typedef lvalue_property_map_archetype
<typename Graph::vertex_descriptor, Property> const_type;
};
};
template <>
struct vertex_property_selector<property_graph_archetype_tag> {
typedef choose_vertex_property_map_archetype type;
};
template <typename G, typename P, typename V>
typename property_map<property_graph_archetype<G, P, V>, P>::type
get(P, property_graph_archetype<G, P, V>&) {
typename property_map<property_graph_archetype<G, P, V>, P>::type pmap;
return pmap;
}
template <typename G, typename P, typename V>
typename property_map<property_graph_archetype<G, P, V>, P>::const_type
get(P, const property_graph_archetype<G, P, V>&) {
typename property_map<property_graph_archetype<G, P, V>, P>::const_type pmap;
return pmap;
}
template <typename G, typename P, typename K, typename V>
typename property_traits<typename property_map<property_graph_archetype<G, P, V>, P>::const_type>::value_type
get(P p, const property_graph_archetype<G, P, V>& g, K k) {
return get( get(p, g), k);
}
template <typename G, typename P, typename V, typename Key>
void
put(P p, property_graph_archetype<G, P, V>& g,
const Key& key, const V& value)
{
typedef typename boost::property_map<property_graph_archetype<G, P, V>, P>::type Map;
Map pmap = get(p, g);
put(pmap, key, value);
}
struct color_value_archetype {
color_value_archetype() { }
color_value_archetype(detail::dummy_constructor) { }
bool operator==(const color_value_archetype& ) const { return true; }
bool operator!=(const color_value_archetype& ) const { return true; }
};
template <>
struct color_traits<color_value_archetype> {
static color_value_archetype white()
{
return color_value_archetype
(static_object<detail::dummy_constructor>::get());
}
static color_value_archetype gray()
{
return color_value_archetype
(static_object<detail::dummy_constructor>::get());
}
static color_value_archetype black()
{
return color_value_archetype
(static_object<detail::dummy_constructor>::get());
}
};
template <typename T>
class buffer_archetype {
public:
void push(const T&) {}
void pop() {}
T& top() { return static_object<T>::get(); }
const T& top() const { return static_object<T>::get(); }
bool empty() const { return true; }
};
} // namespace boost
#endif // BOOST_GRAPH_ARCHETYPES_HPP
|
