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_LABELED_GRAPH_TRAITS_HPP 8 #define BOOST_GRAPH_LABELED_GRAPH_TRAITS_HPP 9 10 #include <boost/graph/graph_mutability_traits.hpp> 11 12 namespace boost { 13 14 // Extend the graph mutability traits (and metafunctions) to include options 15 // for labeled graphs. 16 17 // NOTE: the label_vertex tag denotes the fact that you can basically assign 18 // arbitrary labels to vertices without modifying the actual graph. 19 20 // TODO: We might also overlay the uniqueness/multiplicity of labels in this 21 // hierarchy also. For now, we just assumed that labels are unique. 22 23 struct label_vertex_tag { }; 24 struct labeled_add_vertex_tag : virtual label_vertex_tag { }; 25 struct labeled_add_vertex_property_tag : virtual labeled_add_vertex_tag { }; 26 struct labeled_remove_vertex_tag { }; 27 struct labeled_add_edge_tag : virtual label_vertex_tag { }; 28 struct labeled_add_edge_property_tag : virtual labeled_add_edge_tag{ }; 29 struct labeled_remove_edge_tag { }; 30 31 struct labeled_mutable_vertex_graph_tag 32 : virtual labeled_add_vertex_tag, virtual labeled_remove_vertex_tag 33 { }; 34 struct labeled_mutable_vertex_property_graph_tag 35 : virtual labeled_add_vertex_property_tag, virtual labeled_remove_vertex_tag 36 { }; 37 struct labeled_mutable_edge_graph_tag 38 : virtual labeled_add_edge_tag, virtual labeled_remove_edge_tag 39 { }; 40 struct labeled_mutable_edge_property_graph_tag 41 : virtual labeled_add_edge_property_tag, virtual labeled_remove_edge_tag 42 { }; 43 44 struct labeled_graph_tag 45 : virtual label_vertex_tag 46 { }; 47 struct labeled_mutable_graph_tag 48 : virtual labeled_mutable_vertex_graph_tag 49 , virtual labeled_mutable_edge_graph_tag 50 { }; 51 struct labeled_mutable_property_graph_tag 52 : virtual labeled_mutable_vertex_property_graph_tag 53 , virtual labeled_mutable_edge_property_graph_tag 54 { }; 55 struct labeled_add_only_property_graph_tag 56 : virtual labeled_add_vertex_property_tag 57 , virtual labeled_mutable_edge_property_graph_tag 58 { }; 59 60 // Metafunctions 61 62 template <typename Graph> 63 struct graph_has_add_vertex_by_label 64 : mpl::bool_< 65 is_convertible< 66 typename graph_mutability_traits<Graph>::category, 67 labeled_add_vertex_tag 68 >::value 69 > 70 { }; 71 72 template <typename Graph> 73 struct graph_has_add_vertex_by_label_with_property 74 : mpl::bool_< 75 is_convertible< 76 typename graph_mutability_traits<Graph>::category, 77 labeled_add_vertex_property_tag 78 >::value 79 > 80 { }; 81 82 template <typename Graph> 83 struct graph_has_remove_vertex_by_label 84 : mpl::bool_< 85 is_convertible< 86 typename graph_mutability_traits<Graph>::category, 87 labeled_remove_vertex_tag 88 >::value 89 > 90 { }; 91 92 template <typename Graph> 93 struct graph_has_add_edge_by_label 94 : mpl::bool_< 95 is_convertible< 96 typename graph_mutability_traits<Graph>::category, 97 labeled_add_edge_tag 98 >::value 99 > 100 { }; 101 102 template <typename Graph> 103 struct graph_has_add_edge_by_label_with_property 104 : mpl::bool_< 105 is_convertible< 106 typename graph_mutability_traits<Graph>::category, 107 labeled_add_edge_property_tag 108 >::value 109 > 110 { }; 111 112 template <typename Graph> 113 struct graph_has_remove_edge_by_label 114 : mpl::bool_< 115 is_convertible< 116 typename graph_mutability_traits<Graph>::category, 117 labeled_remove_edge_tag 118 >::value 119 > 120 { }; 121 122 template <typename Graph> 123 struct is_labeled_mutable_vertex_graph 124 : mpl::and_< 125 graph_has_add_vertex_by_label<Graph>, 126 graph_has_remove_vertex_by_label<Graph> 127 > 128 { }; 129 130 template <typename Graph> 131 struct is_labeled_mutable_vertex_property_graph 132 : mpl::and_< 133 graph_has_add_vertex_by_label<Graph>, 134 graph_has_remove_vertex_by_label<Graph> 135 > 136 { }; 137 138 template <typename Graph> 139 struct is_labeled_mutable_edge_graph 140 : mpl::and_< 141 graph_has_add_edge_by_label<Graph>, 142 graph_has_remove_edge_by_label<Graph> 143 > 144 { }; 145 146 template <typename Graph> 147 struct is_labeled_mutable_edge_property_graph 148 : mpl::and_< 149 graph_has_add_edge_by_label<Graph>, 150 graph_has_remove_edge_by_label<Graph> 151 > 152 { }; 153 154 template <typename Graph> 155 struct is_labeled_mutable_graph 156 : mpl::and_< 157 is_labeled_mutable_vertex_graph<Graph>, 158 is_labeled_mutable_edge_graph<Graph> 159 > 160 { }; 161 162 template <typename Graph> 163 struct is_labeled_mutable_property_graph 164 : mpl::and_< 165 is_labeled_mutable_vertex_property_graph<Graph>, 166 is_labeled_mutable_edge_property_graph<Graph> 167 > 168 { }; 169 170 template <typename Graph> 171 struct is_labeled_add_only_property_graph 172 : mpl::bool_< 173 is_convertible< 174 typename graph_mutability_traits<Graph>::category, 175 labeled_add_only_property_graph_tag 176 >::value 177 > 178 { }; 179 180 template <typename Graph> 181 struct is_labeled_graph 182 : mpl::bool_< 183 is_convertible< 184 typename graph_mutability_traits<Graph>::category, 185 label_vertex_tag 186 >::value 187 > 188 { }; 189 190 template <typename> struct graph_mutability_traits; 191 192 namespace graph_detail { 193 // The determine mutability metafunction computes a labeled mutability tag 194 // based on the mutability of the given graph type. This is used by the 195 // graph_mutability_traits specialization below. 196 template <typename Graph> 197 struct determine_mutability { 198 typedef typename mpl::if_< 199 is_add_only_property_graph<Graph>, 200 labeled_add_only_property_graph_tag, 201 typename mpl::if_< 202 is_mutable_property_graph<Graph>, 203 labeled_mutable_property_graph_tag, 204 typename mpl::if_< 205 is_mutable_graph<Graph>, 206 labeled_mutable_graph_tag, 207 typename mpl::if_< 208 is_mutable_edge_graph<Graph>, 209 labeled_graph_tag, 210 typename graph_mutability_traits<Graph>::category 211 >::type 212 >::type 213 >::type 214 >::type type; 215 }; 216 } // namespace graph_detail 217 218 #define LABELED_GRAPH_PARAMS typename G, typename L, typename S 219 #define LABELED_GRAPH labeled_graph<G,L,S> 220 221 // Specialize mutability traits for the labeled graph. 222 // This specialization depends on the mutability of the underlying graph type. 223 // If the underlying graph is fully mutable, this is also fully mutable. 224 // Otherwise, it's different. 225 template <LABELED_GRAPH_PARAMS> 226 struct graph_mutability_traits< LABELED_GRAPH > { 227 typedef typename graph_detail::determine_mutability< 228 typename LABELED_GRAPH::graph_type 229 >::type category; 230 }; 231 232 #undef LABELED_GRAPH_PARAMS 233 #undef LABELED_GRAPH 234 235 } // namespace boost 236 237 #endif 238