1 | // Copyright (C) 2009 Andrew Sutton |
2 | // |
3 | // Use, modification and distribution is subject to the Boost Software |
4 | // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
5 | // http://www.boost.org/LICENSE_1_0.txt) |
6 | |
7 | #ifndef BOOST_GRAPH_MUTABILITY_TRAITS_HPP |
8 | #define BOOST_GRAPH_MUTABILITY_TRAITS_HPP |
9 | |
10 | #include <boost/config.hpp> |
11 | #include <boost/mpl/if.hpp> |
12 | #include <boost/mpl/and.hpp> |
13 | #include <boost/mpl/bool.hpp> |
14 | #include <boost/type_traits/is_same.hpp> |
15 | |
16 | namespace boost { |
17 | |
18 | // The mutabiltiy categories classify graphs by their mutating operations |
19 | // on the edge and vertex sets. This is a substantially more refined |
20 | // categorization than the MutableGraph and MutablePropertyGraph denote. |
21 | // Currently, this framework is only used in the graph tests to help |
22 | // dispatch test to the correct places. However, there are probably some |
23 | // constructive or destructive algorithms (i.e., graph generators) that |
24 | // may use these to describe requirements on graph inputs. |
25 | |
26 | struct add_vertex_tag { }; |
27 | struct add_vertex_property_tag : virtual add_vertex_tag { }; |
28 | struct add_edge_tag { }; |
29 | struct add_edge_property_tag : virtual add_edge_tag { }; |
30 | struct remove_vertex_tag { }; |
31 | struct remove_edge_tag { }; |
32 | |
33 | struct mutable_vertex_graph_tag |
34 | : virtual add_vertex_tag, virtual remove_vertex_tag |
35 | { }; |
36 | struct mutable_vertex_property_graph_tag |
37 | : virtual add_vertex_property_tag, virtual remove_vertex_tag |
38 | { }; |
39 | |
40 | struct mutable_edge_graph_tag |
41 | : virtual add_edge_tag, virtual remove_edge_tag |
42 | { }; |
43 | struct mutable_edge_property_graph_tag |
44 | : virtual add_edge_property_tag, virtual remove_edge_tag |
45 | { }; |
46 | |
47 | struct mutable_graph_tag |
48 | : virtual mutable_vertex_graph_tag |
49 | , virtual mutable_edge_graph_tag |
50 | { }; |
51 | struct mutable_property_graph_tag |
52 | : virtual mutable_vertex_property_graph_tag |
53 | , virtual mutable_edge_property_graph_tag |
54 | { }; |
55 | |
56 | // Some graphs just don't like to be torn down. Note this only restricts |
57 | // teardown to the set of vertices, not the vertex set. |
58 | // TODO: Find a better name for this tag. |
59 | struct add_only_property_graph_tag |
60 | : virtual add_vertex_property_tag |
61 | , virtual mutable_edge_property_graph_tag |
62 | { }; |
63 | |
64 | /** |
65 | * The graph_mutability_traits provide methods for determining the |
66 | * interfaces supported by graph classes for adding and removing vertices |
67 | * and edges. |
68 | */ |
69 | template <typename Graph> |
70 | struct graph_mutability_traits { |
71 | typedef typename Graph::mutability_category category; |
72 | }; |
73 | |
74 | template <typename Graph> |
75 | struct graph_has_add_vertex |
76 | : mpl::bool_< |
77 | is_convertible< |
78 | typename graph_mutability_traits<Graph>::category, |
79 | add_vertex_tag |
80 | >::value |
81 | > |
82 | { }; |
83 | |
84 | template <typename Graph> |
85 | struct graph_has_add_vertex_with_property |
86 | : mpl::bool_< |
87 | is_convertible< |
88 | typename graph_mutability_traits<Graph>::category, |
89 | add_vertex_property_tag |
90 | >::value |
91 | > |
92 | { }; |
93 | |
94 | |
95 | template <typename Graph> |
96 | struct graph_has_remove_vertex |
97 | : mpl::bool_< |
98 | is_convertible< |
99 | typename graph_mutability_traits<Graph>::category, |
100 | remove_vertex_tag |
101 | >::value |
102 | > |
103 | { }; |
104 | |
105 | template <typename Graph> |
106 | struct graph_has_add_edge |
107 | : mpl::bool_< |
108 | is_convertible< |
109 | typename graph_mutability_traits<Graph>::category, |
110 | add_edge_tag |
111 | >::value |
112 | > |
113 | { }; |
114 | |
115 | template <typename Graph> |
116 | struct graph_has_add_edge_with_property |
117 | : mpl::bool_< |
118 | is_convertible< |
119 | typename graph_mutability_traits<Graph>::category, |
120 | add_edge_property_tag |
121 | >::value |
122 | > |
123 | { }; |
124 | |
125 | |
126 | template <typename Graph> |
127 | struct graph_has_remove_edge |
128 | : mpl::bool_< |
129 | is_convertible< |
130 | typename graph_mutability_traits<Graph>::category, |
131 | remove_edge_tag |
132 | >::value |
133 | > |
134 | { }; |
135 | |
136 | |
137 | template <typename Graph> |
138 | struct is_mutable_vertex_graph |
139 | : mpl::and_< |
140 | graph_has_add_vertex<Graph>, |
141 | graph_has_remove_vertex<Graph> |
142 | > |
143 | { }; |
144 | |
145 | template <typename Graph> |
146 | struct is_mutable_vertex_property_graph |
147 | : mpl::and_< |
148 | graph_has_add_vertex_with_property<Graph>, |
149 | graph_has_remove_vertex<Graph> |
150 | > |
151 | { }; |
152 | |
153 | |
154 | template <typename Graph> |
155 | struct is_mutable_edge_graph |
156 | : mpl::and_< |
157 | graph_has_add_edge<Graph>, |
158 | graph_has_remove_edge<Graph> |
159 | > |
160 | { }; |
161 | |
162 | template <typename Graph> |
163 | struct is_mutable_edge_property_graph |
164 | : mpl::and_< |
165 | graph_has_add_edge_with_property<Graph>, |
166 | graph_has_remove_edge<Graph> |
167 | > |
168 | { }; |
169 | |
170 | |
171 | template <typename Graph> |
172 | struct is_mutable_graph |
173 | : mpl::and_< |
174 | is_mutable_vertex_graph<Graph>, |
175 | is_mutable_edge_graph<Graph> |
176 | > |
177 | { }; |
178 | |
179 | template <typename Graph> |
180 | struct is_mutable_property_graph |
181 | : mpl::and_< |
182 | is_mutable_vertex_property_graph<Graph>, |
183 | is_mutable_edge_property_graph<Graph> |
184 | > |
185 | { }; |
186 | |
187 | template <typename Graph> |
188 | struct is_add_only_property_graph |
189 | : mpl::bool_< |
190 | is_convertible< |
191 | typename graph_mutability_traits<Graph>::category, |
192 | add_only_property_graph_tag |
193 | >::value |
194 | > |
195 | { }; |
196 | |
197 | /** @name Mutability Traits Specializations */ |
198 | //@{ |
199 | |
200 | //@} |
201 | |
202 | } // namespace boost |
203 | |
204 | #endif |
205 | |