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