Boost Graph Library: Verification of ReadWritePropertyMapConcept for std::map fails

Question

For some reason, verification of ReadWritePropertyMapConcept for std::map of vertex descriptors and colors fails:

Live on godbolt

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/property_map/property_map.hpp>
#include <map>

struct Vertex {};
using graph_type = boost::adjacency_list<boost::vecS, boost::vecS,
                                         boost::bidirectionalS, Vertex>;
using vertex_descriptor = boost::graph_traits<graph_type>::vertex_descriptor;
using map_type = std::map<vertex_descriptor, boost::default_color_type>;

BOOST_CONCEPT_ASSERT(
    (boost::ReadWritePropertyMapConcept<map_type, vertex_descriptor>));

with errors:

In file included from /opt/compiler-explorer/libs/boost_1_78_0/boost/graph/adjacency_list.hpp:27,
                 from <source>:1:
/opt/compiler-explorer/libs/boost_1_78_0/boost/property_map/property_map.hpp: In instantiation of 'struct boost::ReadWritePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int>':
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:32:62:   required by substitution of 'template<class Model> boost::concepts::detail::yes boost::concepts::detail::has_constraints_(Model*, boost::concepts::detail::wrap_constraints<Model, (& Model::constraints)>*) [with Model = boost::ReadWritePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int>]'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:42:5:   required from 'const bool boost::concepts::not_satisfied<boost::ReadWritePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int> >::value'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:45:51:   required from 'struct boost::concepts::not_satisfied<boost::ReadWritePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int> >'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/general.hpp:72:8:   required from 'struct boost::concepts::requirement_<void (*)(boost::ReadWritePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int>)>'
<source>:13:1:   required from here
/opt/compiler-explorer/libs/boost_1_78_0/boost/property_map/property_map.hpp:203:54: error: no type named 'category' in 'struct boost::property_traits<std::map<long unsigned int, boost::default_color_type> >'
  203 |     typedef typename property_traits<PMap>::category Category;
      |                                                      ^~~~~~~~
/opt/compiler-explorer/libs/boost_1_78_0/boost/property_map/property_map.hpp: In instantiation of 'struct boost::ReadablePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int>':
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:32:62:   required by substitution of 'template<class Model> boost::concepts::detail::yes boost::concepts::detail::has_constraints_(Model*, boost::concepts::detail::wrap_constraints<Model, (& Model::constraints)>*) [with Model = boost::ReadablePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int>]'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:42:5:   required from 'const bool boost::concepts::not_satisfied<boost::ReadablePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int> >::value'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:45:51:   required from 'struct boost::concepts::not_satisfied<boost::ReadablePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int> >'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/general.hpp:72:8:   required from 'struct boost::concepts::requirement_<void (*)(boost::ReadablePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int>)>'
/opt/compiler-explorer/libs/boost_1_78_0/boost/property_map/property_map.hpp:206:7:   required from 'void boost::ReadWritePropertyMapConcept<PMap, Key>::constraints() [with PMap = std::map<long unsigned int, boost::default_color_type>; Key = long unsigned int]'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:32:62:   required by substitution of 'template<class Model> boost::concepts::detail::yes boost::concepts::detail::has_constraints_(Model*, boost::concepts::detail::wrap_constraints<Model, (& Model::constraints)>*) [with Model = boost::ReadWritePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int>]'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:42:5:   required from 'const bool boost::concepts::not_satisfied<boost::ReadWritePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int> >::value'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:45:51:   required from 'struct boost::concepts::not_satisfied<boost::ReadWritePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int> >'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/general.hpp:72:8:   required from 'struct boost::concepts::requirement_<void (*)(boost::ReadWritePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int>)>'
<source>:13:1:   required from here
/opt/compiler-explorer/libs/boost_1_78_0/boost/property_map/property_map.hpp:143:54: error: no type named 'key_type' in 'struct boost::property_traits<std::map<long unsigned int, boost::default_color_type> >'
  143 |     typedef typename property_traits<PMap>::key_type key_type;
      |                                                      ^~~~~~~~
/opt/compiler-explorer/libs/boost_1_78_0/boost/property_map/property_map.hpp:144:55: error: no type named 'reference' in 'struct boost::property_traits<std::map<long unsigned int, boost::default_color_type> >'
  144 |     typedef typename property_traits<PMap>::reference reference;
      |                                                       ^~~~~~~~~
/opt/compiler-explorer/libs/boost_1_78_0/boost/property_map/property_map.hpp:145:54: error: no type named 'category' in 'struct boost::property_traits<std::map<long unsigned int, boost::default_color_type> >'
  145 |     typedef typename property_traits<PMap>::category Category;
      |                                                      ^~~~~~~~
/opt/compiler-explorer/libs/boost_1_78_0/boost/property_map/property_map.hpp:154:48: error: no type named 'value_type' in 'struct boost::property_traits<std::map<long unsigned int, boost::default_color_type> >'
  154 |     typename property_traits<PMap>::value_type val;
      |                                                ^~~
/opt/compiler-explorer/libs/boost_1_78_0/boost/property_map/property_map.hpp: In instantiation of 'struct boost::WritablePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int>':
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:32:62:   required by substitution of 'template<class Model> boost::concepts::detail::yes boost::concepts::detail::has_constraints_(Model*, boost::concepts::detail::wrap_constraints<Model, (& Model::constraints)>*) [with Model = boost::WritablePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int>]'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:42:5:   required from 'const bool boost::concepts::not_satisfied<boost::WritablePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int> >::value'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:45:51:   required from 'struct boost::concepts::not_satisfied<boost::WritablePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int> >'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/general.hpp:72:8:   required from 'struct boost::concepts::requirement_<void (*)(boost::WritablePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int>)>'
/opt/compiler-explorer/libs/boost_1_78_0/boost/property_map/property_map.hpp:207:7:   required from 'void boost::ReadWritePropertyMapConcept<PMap, Key>::constraints() [with PMap = std::map<long unsigned int, boost::default_color_type>; Key = long unsigned int]'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:32:62:   required by substitution of 'template<class Model> boost::concepts::detail::yes boost::concepts::detail::has_constraints_(Model*, boost::concepts::detail::wrap_constraints<Model, (& Model::constraints)>*) [with Model = boost::ReadWritePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int>]'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:42:5:   required from 'const bool boost::concepts::not_satisfied<boost::ReadWritePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int> >::value'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:45:51:   required from 'struct boost::concepts::not_satisfied<boost::ReadWritePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int> >'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/general.hpp:72:8:   required from 'struct boost::concepts::requirement_<void (*)(boost::ReadWritePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int>)>'
<source>:13:1:   required from here
/opt/compiler-explorer/libs/boost_1_78_0/boost/property_map/property_map.hpp:176:54: error: no type named 'key_type' in 'struct boost::property_traits<std::map<long unsigned int, boost::default_color_type> >'
  176 |     typedef typename property_traits<PMap>::key_type key_type;
      |                                                      ^~~~~~~~
/opt/compiler-explorer/libs/boost_1_78_0/boost/property_map/property_map.hpp:177:54: error: no type named 'category' in 'struct boost::property_traits<std::map<long unsigned int, boost::default_color_type> >'
  177 |     typedef typename property_traits<PMap>::category Category;
      |                                                      ^~~~~~~~
/opt/compiler-explorer/libs/boost_1_78_0/boost/property_map/property_map.hpp:185:48: error: no type named 'value_type' in 'struct boost::property_traits<std::map<long unsigned int, boost::default_color_type> >'
  185 |     typename property_traits<PMap>::value_type val;
      |                                                ^~~
In file included from /opt/compiler-explorer/libs/boost_1_78_0/boost/concept/assert.hpp:35,
                 from /opt/compiler-explorer/libs/boost_1_78_0/boost/property_map/property_map.hpp:19,
                 from /opt/compiler-explorer/libs/boost_1_78_0/boost/graph/adjacency_list.hpp:27,
                 from <source>:1:
/opt/compiler-explorer/libs/boost_1_78_0/boost/property_map/property_map.hpp: In instantiation of 'void boost::ReadWritePropertyMapConcept<PMap, Key>::constraints() [with PMap = std::map<long unsigned int, boost::default_color_type>; Key = long unsigned int]':
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:32:62:   required by substitution of 'template<class Model> boost::concepts::detail::yes boost::concepts::detail::has_constraints_(Model*, boost::concepts::detail::wrap_constraints<Model, (& Model::constraints)>*) [with Model = boost::ReadWritePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int>]'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:42:5:   required from 'const bool boost::concepts::not_satisfied<boost::ReadWritePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int> >::value'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/has_constraints.hpp:45:51:   required from 'struct boost::concepts::not_satisfied<boost::ReadWritePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int> >'
/opt/compiler-explorer/libs/boost_1_78_0/boost/concept/detail/general.hpp:72:8:   required from 'struct boost::concepts::requirement_<void (*)(boost::ReadWritePropertyMapConcept<std::map<long unsigned int, boost::default_color_type>, long unsigned int>)>'
<source>:13:1:   required from here
/opt/compiler-explorer/libs/boost_1_78_0/boost/property_map/property_map.hpp:208:7: error: no type named 'category' in 'struct boost::property_traits<std::map<long unsigned int, boost::default_color_type> >'
  208 |       BOOST_CONCEPT_ASSERT((ConvertibleConcept<Category, ReadWriteTag>));
      |       ^~~~~~~~~~~~~~~~~~~~
Compiler returned: 1

However, std::map surely has key_type, value_type etc. I have also used it in boost::depth_first_search() as color_map as in this question, and it seemed to work.

On the contrary, when the property map is constructed from adapter, the check passes:

int main() {
    graph_type g;
    std::vector<boost::default_color_type> colors(num_vertices(g));
    auto color_map = boost::make_iterator_property_map(
        colors.begin(), get(boost::vertex_index, g));
    BOOST_CONCEPT_ASSERT(
        (boost::ReadWritePropertyMapConcept<decltype(color_map),
                                            boost::default_color_type>));
}

Why is the concept check failing?

Answer 1

A container doesn't usually satisfy the concept requirements for property maps. Put simply: the map is not a property map. At all.

In principle you need to adapt it. Certainly in the case of this associative property map:

std::map<V, C> colors;
auto color_map = make_assoc_property_map(colors);

Live On Compiler Explorer

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>

#include <fmt/ranges.h>
using C = boost::default_color_type;
template <> struct fmt::formatter<C> {
    auto format(C c, auto& ctx) const { return format_to(ctx.out(), "{}", std::array{"white", "gray", "green", "red", "black"}.at(c)); }
};

struct Vertex {};
using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS,
                                Vertex>;

int main() {
    using V = G::vertex_descriptor;

    std::map<V, C> colors;
    auto color_map = make_assoc_property_map(colors);

    G g(10);
    add_edge(0, 1, g);
    add_edge(1, 3, g);
    add_edge(1, 4, g);
    add_edge(3, 2, g);
    add_edge(2, 7, g);

    breadth_first_search(g, vertex(0, g), boost::color_map(color_map));

    fmt::print("{}\n", fmt::join(colors, "\n"));
}

Prints

(0, black)
(1, black)
(2, black)
(3, black)
(4, black)
(5, white)
(6, white)
(7, black)
(8, white)
(9, white)