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
|
// Copyright (C) 2009 Andrew Sutton
// Use, modification and distribution is subject to 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_LABELED_GRAPH_TRAITS_HPP
#define BOOST_GRAPH_LABELED_GRAPH_TRAITS_HPP
#include <boost/graph/graph_mutability_traits.hpp>
namespace boost {
// Extend the graph mutability traits (and metafunctions) to include options
// for labeled graphs.
// NOTE: the label_vertex tag denotes the fact that you can basically assign
// arbitrary labels to vertices without modifying the actual graph.
// TODO: We might also overlay the uniqueness/multiplicity of labels in this
// hierarchy also. For now, we just assumed that labels are unique.
struct label_vertex_tag { };
struct labeled_add_vertex_tag : virtual label_vertex_tag { };
struct labeled_add_vertex_property_tag : virtual labeled_add_vertex_tag { };
struct labeled_remove_vertex_tag { };
struct labeled_add_edge_tag : virtual label_vertex_tag { };
struct labeled_add_edge_property_tag : virtual labeled_add_edge_tag{ };
struct labeled_remove_edge_tag { };
struct labeled_mutable_vertex_graph_tag
: virtual labeled_add_vertex_tag, virtual labeled_remove_vertex_tag
{ };
struct labeled_mutable_vertex_property_graph_tag
: virtual labeled_add_vertex_property_tag, virtual labeled_remove_vertex_tag
{ };
struct labeled_mutable_edge_graph_tag
: virtual labeled_add_edge_tag, virtual labeled_remove_edge_tag
{ };
struct labeled_mutable_edge_property_graph_tag
: virtual labeled_add_edge_property_tag, virtual labeled_remove_edge_tag
{ };
struct labeled_graph_tag
: virtual label_vertex_tag
{ };
struct labeled_mutable_graph_tag
: virtual labeled_mutable_vertex_graph_tag
, virtual labeled_mutable_edge_graph_tag
{ };
struct labeled_mutable_property_graph_tag
: virtual labeled_mutable_vertex_property_graph_tag
, virtual labeled_mutable_edge_property_graph_tag
{ };
struct labeled_add_only_property_graph_tag
: virtual labeled_add_vertex_property_tag
, virtual labeled_mutable_edge_property_graph_tag
{ };
// Metafunctions
template <typename Graph>
struct graph_has_add_vertex_by_label
: mpl::bool_<
is_convertible<
typename graph_mutability_traits<Graph>::category,
labeled_add_vertex_tag
>::value
>
{ };
template <typename Graph>
struct graph_has_add_vertex_by_label_with_property
: mpl::bool_<
is_convertible<
typename graph_mutability_traits<Graph>::category,
labeled_add_vertex_property_tag
>::value
>
{ };
template <typename Graph>
struct graph_has_remove_vertex_by_label
: mpl::bool_<
is_convertible<
typename graph_mutability_traits<Graph>::category,
labeled_remove_vertex_tag
>::value
>
{ };
template <typename Graph>
struct graph_has_add_edge_by_label
: mpl::bool_<
is_convertible<
typename graph_mutability_traits<Graph>::category,
labeled_add_edge_tag
>::value
>
{ };
template <typename Graph>
struct graph_has_add_edge_by_label_with_property
: mpl::bool_<
is_convertible<
typename graph_mutability_traits<Graph>::category,
labeled_add_edge_property_tag
>::value
>
{ };
template <typename Graph>
struct graph_has_remove_edge_by_label
: mpl::bool_<
is_convertible<
typename graph_mutability_traits<Graph>::category,
labeled_remove_edge_tag
>::value
>
{ };
template <typename Graph>
struct is_labeled_mutable_vertex_graph
: mpl::and_<
graph_has_add_vertex_by_label<Graph>,
graph_has_remove_vertex_by_label<Graph>
>
{ };
template <typename Graph>
struct is_labeled_mutable_vertex_property_graph
: mpl::and_<
graph_has_add_vertex_by_label<Graph>,
graph_has_remove_vertex_by_label<Graph>
>
{ };
template <typename Graph>
struct is_labeled_mutable_edge_graph
: mpl::and_<
graph_has_add_edge_by_label<Graph>,
graph_has_remove_edge_by_label<Graph>
>
{ };
template <typename Graph>
struct is_labeled_mutable_edge_property_graph
: mpl::and_<
graph_has_add_edge_by_label<Graph>,
graph_has_remove_edge_by_label<Graph>
>
{ };
template <typename Graph>
struct is_labeled_mutable_graph
: mpl::and_<
is_labeled_mutable_vertex_graph<Graph>,
is_labeled_mutable_edge_graph<Graph>
>
{ };
template <typename Graph>
struct is_labeled_mutable_property_graph
: mpl::and_<
is_labeled_mutable_vertex_property_graph<Graph>,
is_labeled_mutable_edge_property_graph<Graph>
>
{ };
template <typename Graph>
struct is_labeled_add_only_property_graph
: mpl::bool_<
is_convertible<
typename graph_mutability_traits<Graph>::category,
labeled_add_only_property_graph_tag
>::value
>
{ };
template <typename Graph>
struct is_labeled_graph
: mpl::bool_<
is_convertible<
typename graph_mutability_traits<Graph>::category,
label_vertex_tag
>::value
>
{ };
template <typename> struct graph_mutability_traits;
namespace graph_detail {
// The determine mutability metafunction computes a labeled mutability tag
// based on the mutability of the given graph type. This is used by the
// graph_mutability_traits specialization below.
template <typename Graph>
struct determine_mutability {
typedef typename mpl::if_<
is_add_only_property_graph<Graph>,
labeled_add_only_property_graph_tag,
typename mpl::if_<
is_mutable_property_graph<Graph>,
labeled_mutable_property_graph_tag,
typename mpl::if_<
is_mutable_graph<Graph>,
labeled_mutable_graph_tag,
typename mpl::if_<
is_mutable_edge_graph<Graph>,
labeled_graph_tag,
typename graph_mutability_traits<Graph>::category
>::type
>::type
>::type
>::type type;
};
} // namespace graph_detail
#define LABELED_GRAPH_PARAMS typename G, typename L, typename S
#define LABELED_GRAPH labeled_graph<G,L,S>
// Specialize mutability traits for the labeled graph.
// This specialization depends on the mutability of the underlying graph type.
// If the underlying graph is fully mutable, this is also fully mutable.
// Otherwise, it's different.
template <LABELED_GRAPH_PARAMS>
struct graph_mutability_traits< LABELED_GRAPH > {
typedef typename graph_detail::determine_mutability<
typename LABELED_GRAPH::graph_type
>::type category;
};
#undef LABELED_GRAPH_PARAMS
#undef LABELED_GRAPH
} // namespace boost
#endif
|
