graph/detail/labeled_graph_traits.hpp

0001 // Copyright (C) 2009 Andrew Sutton
0002
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 #ifndef BOOST_GRAPH_LABELED_GRAPH_TRAITS_HPP
0008 #define BOOST_GRAPH_LABELED_GRAPH_TRAITS_HPP
0009
0010 #include <boost/graph/graph_mutability_traits.hpp>
0011
0012 namespace boost
0013 {
0014
0015 // Extend the graph mutability traits (and metafunctions) to include options
0016 // for labeled graphs.
0017
0018 // NOTE: the label_vertex tag denotes the fact that you can basically assign
0019 // arbitrary labels to vertices without modifying the actual graph.
0020
0021 // TODO: We might also overlay the uniqueness/multiplicity of labels in this
0022 // hierarchy also. For now, we just assumed that labels are unique.
0023
0024 struct label_vertex_tag
0025 {
0026 };
0027 struct labeled_add_vertex_tag : virtual label_vertex_tag
0028 {
0029 };
0030 struct labeled_add_vertex_property_tag : virtual labeled_add_vertex_tag
0031 {
0032 };
0033 struct labeled_remove_vertex_tag
0034 {
0035 };
0036 struct labeled_add_edge_tag : virtual label_vertex_tag
0037 {
0038 };
0039 struct labeled_add_edge_property_tag : virtual labeled_add_edge_tag
0040 {
0041 };
0042 struct labeled_remove_edge_tag
0043 {
0044 };
0045
0046 struct labeled_mutable_vertex_graph_tag : virtual labeled_add_vertex_tag,
0047                                           virtual labeled_remove_vertex_tag
0048 {
0049 };
0050 struct labeled_mutable_vertex_property_graph_tag
0051 : virtual labeled_add_vertex_property_tag,
0052   virtual labeled_remove_vertex_tag
0053 {
0054 };
0055 struct labeled_mutable_edge_graph_tag : virtual labeled_add_edge_tag,
0056                                         virtual labeled_remove_edge_tag
0057 {
0058 };
0059 struct labeled_mutable_edge_property_graph_tag
0060 : virtual labeled_add_edge_property_tag,
0061   virtual labeled_remove_edge_tag
0062 {
0063 };
0064
0065 struct labeled_graph_tag : virtual label_vertex_tag
0066 {
0067 };
0068 struct labeled_mutable_graph_tag : virtual labeled_mutable_vertex_graph_tag,
0069                                    virtual labeled_mutable_edge_graph_tag
0070 {
0071 };
0072 struct labeled_mutable_property_graph_tag
0073 : virtual labeled_mutable_vertex_property_graph_tag,
0074   virtual labeled_mutable_edge_property_graph_tag
0075 {
0076 };
0077 struct labeled_add_only_property_graph_tag
0078 : virtual labeled_add_vertex_property_tag,
0079   virtual labeled_mutable_edge_property_graph_tag
0080 {
0081 };
0082
0083 // Metafunctions
0084
0085 template < typename Graph >
0086 struct graph_has_add_vertex_by_label
0087 : mpl::bool_<
0088       is_convertible< typename graph_mutability_traits< Graph >::category,
0089           labeled_add_vertex_tag >::value >
0090 {
0091 };
0092
0093 template < typename Graph >
0094 struct graph_has_add_vertex_by_label_with_property
0095 : mpl::bool_<
0096       is_convertible< typename graph_mutability_traits< Graph >::category,
0097           labeled_add_vertex_property_tag >::value >
0098 {
0099 };
0100
0101 template < typename Graph >
0102 struct graph_has_remove_vertex_by_label
0103 : mpl::bool_<
0104       is_convertible< typename graph_mutability_traits< Graph >::category,
0105           labeled_remove_vertex_tag >::value >
0106 {
0107 };
0108
0109 template < typename Graph >
0110 struct graph_has_add_edge_by_label
0111 : mpl::bool_<
0112       is_convertible< typename graph_mutability_traits< Graph >::category,
0113           labeled_add_edge_tag >::value >
0114 {
0115 };
0116
0117 template < typename Graph >
0118 struct graph_has_add_edge_by_label_with_property
0119 : mpl::bool_<
0120       is_convertible< typename graph_mutability_traits< Graph >::category,
0121           labeled_add_edge_property_tag >::value >
0122 {
0123 };
0124
0125 template < typename Graph >
0126 struct graph_has_remove_edge_by_label
0127 : mpl::bool_<
0128       is_convertible< typename graph_mutability_traits< Graph >::category,
0129           labeled_remove_edge_tag >::value >
0130 {
0131 };
0132
0133 template < typename Graph >
0134 struct is_labeled_mutable_vertex_graph
0135 : mpl::and_< graph_has_add_vertex_by_label< Graph >,
0136       graph_has_remove_vertex_by_label< Graph > >
0137 {
0138 };
0139
0140 template < typename Graph >
0141 struct is_labeled_mutable_vertex_property_graph
0142 : mpl::and_< graph_has_add_vertex_by_label< Graph >,
0143       graph_has_remove_vertex_by_label< Graph > >
0144 {
0145 };
0146
0147 template < typename Graph >
0148 struct is_labeled_mutable_edge_graph
0149 : mpl::and_< graph_has_add_edge_by_label< Graph >,
0150       graph_has_remove_edge_by_label< Graph > >
0151 {
0152 };
0153
0154 template < typename Graph >
0155 struct is_labeled_mutable_edge_property_graph
0156 : mpl::and_< graph_has_add_edge_by_label< Graph >,
0157       graph_has_remove_edge_by_label< Graph > >
0158 {
0159 };
0160
0161 template < typename Graph >
0162 struct is_labeled_mutable_graph
0163 : mpl::and_< is_labeled_mutable_vertex_graph< Graph >,
0164       is_labeled_mutable_edge_graph< Graph > >
0165 {
0166 };
0167
0168 template < typename Graph >
0169 struct is_labeled_mutable_property_graph
0170 : mpl::and_< is_labeled_mutable_vertex_property_graph< Graph >,
0171       is_labeled_mutable_edge_property_graph< Graph > >
0172 {
0173 };
0174
0175 template < typename Graph >
0176 struct is_labeled_add_only_property_graph
0177 : mpl::bool_<
0178       is_convertible< typename graph_mutability_traits< Graph >::category,
0179           labeled_add_only_property_graph_tag >::value >
0180 {
0181 };
0182
0183 template < typename Graph >
0184 struct is_labeled_graph
0185 : mpl::bool_<
0186       is_convertible< typename graph_mutability_traits< Graph >::category,
0187           label_vertex_tag >::value >
0188 {
0189 };
0190
0191 template < typename > struct graph_mutability_traits;
0192
0193 namespace graph_detail
0194 {
0195     // The determine mutability metafunction computes a labeled mutability tag
0196     // based on the mutability of the given graph type. This is used by the
0197     // graph_mutability_traits specialization below.
0198     template < typename Graph > struct determine_mutability
0199     {
0200         typedef typename mpl::if_< is_add_only_property_graph< Graph >,
0201             labeled_add_only_property_graph_tag,
0202             typename mpl::if_< is_mutable_property_graph< Graph >,
0203                 labeled_mutable_property_graph_tag,
0204                 typename mpl::if_< is_mutable_graph< Graph >,
0205                     labeled_mutable_graph_tag,
0206                     typename mpl::if_< is_mutable_edge_graph< Graph >,
0207                         labeled_graph_tag,
0208                         typename graph_mutability_traits< Graph >::category >::
0209                         type >::type >::type >::type type;
0210     };
0211 } // namespace graph_detail
0212
0213 #define LABELED_GRAPH_PARAMS typename G, typename L, typename S
0214 #define LABELED_GRAPH labeled_graph< G, L, S >
0215
0216 // Specialize mutability traits for the labeled graph.
0217 // This specialization depends on the mutability of the underlying graph type.
0218 // If the underlying graph is fully mutable, this is also fully mutable.
0219 // Otherwise, it's different.
0220 template < LABELED_GRAPH_PARAMS >
0221 struct graph_mutability_traits< LABELED_GRAPH >
0222 {
0223     typedef typename graph_detail::determine_mutability<
0224         typename LABELED_GRAPH::graph_type >::type category;
0225 };
0226
0227 #undef LABELED_GRAPH_PARAMS
0228 #undef LABELED_GRAPH
0229
0230 } // namespace boost
0231
0232 #endif