1 // Copyright (C) 2005-2010 The Trustees of Indiana University.
2
3 // Distributed under the Boost Software License, Version 1.0.
4 // (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6
7 // Authors: Jeremiah Willcock
8 // Douglas Gregor
9 // Andrew Lumsdaine
10
11 // One bit per color property map (gray and black are the same, green is not
12 // supported)
13
14 #ifndef BOOST_ONE_BIT_COLOR_MAP_HPP
15 #define BOOST_ONE_BIT_COLOR_MAP_HPP
16
17 #include <boost/property_map/property_map.hpp>
18 #include <boost/graph/properties.hpp>
19 #include <boost/graph/detail/mpi_include.hpp>
20 #include <boost/shared_array.hpp>
21 #include <boost/config.hpp>
22 #include <boost/assert.hpp>
23 #include <algorithm>
24 #include <limits>
25
26 namespace boost {
27
28 enum one_bit_color_type {
29 one_bit_white = 0,
30 one_bit_not_white = 1
31 };
32
33 template <>
34 struct color_traits<one_bit_color_type>
35 {
whiteboost::color_traits36 static one_bit_color_type white() { return one_bit_white; }
grayboost::color_traits37 static one_bit_color_type gray() { return one_bit_not_white; }
blackboost::color_traits38 static one_bit_color_type black() { return one_bit_not_white; }
39 };
40
41
42 template<typename IndexMap = identity_property_map>
43 struct one_bit_color_map
44 {
45 BOOST_STATIC_CONSTANT(int, bits_per_char = std::numeric_limits<unsigned char>::digits);
46 std::size_t n;
47 IndexMap index;
48 shared_array<unsigned char> data;
49
50 typedef typename property_traits<IndexMap>::key_type key_type;
51 typedef one_bit_color_type value_type;
52 typedef void reference;
53 typedef read_write_property_map_tag category;
54
one_bit_color_mapboost::one_bit_color_map55 explicit one_bit_color_map(std::size_t n, const IndexMap& index = IndexMap())
56 : n(n), index(index), data(new unsigned char[(n + bits_per_char - 1) / bits_per_char])
57 {
58 // Fill to white
59 std::fill(data.get(), data.get() + (n + bits_per_char - 1) / bits_per_char, 0);
60 }
61 };
62
63 template<typename IndexMap>
64 inline one_bit_color_type
get(const one_bit_color_map<IndexMap> & pm,typename property_traits<IndexMap>::key_type key)65 get(const one_bit_color_map<IndexMap>& pm,
66 typename property_traits<IndexMap>::key_type key)
67 {
68 BOOST_STATIC_CONSTANT(int, bits_per_char = one_bit_color_map<IndexMap>::bits_per_char);
69 typename property_traits<IndexMap>::value_type i = get(pm.index, key);
70 BOOST_ASSERT ((std::size_t)i < pm.n);
71 return one_bit_color_type((pm.data.get()[i / bits_per_char] >> (i % bits_per_char)) & 1);
72 }
73
74 template<typename IndexMap>
75 inline void
put(const one_bit_color_map<IndexMap> & pm,typename property_traits<IndexMap>::key_type key,one_bit_color_type value)76 put(const one_bit_color_map<IndexMap>& pm,
77 typename property_traits<IndexMap>::key_type key,
78 one_bit_color_type value)
79 {
80 BOOST_STATIC_CONSTANT(int, bits_per_char = one_bit_color_map<IndexMap>::bits_per_char);
81 typename property_traits<IndexMap>::value_type i = get(pm.index, key);
82 BOOST_ASSERT ((std::size_t)i < pm.n);
83 BOOST_ASSERT (value >= 0 && value < 2);
84 std::size_t byte_num = i / bits_per_char;
85 std::size_t bit_position = (i % bits_per_char);
86 pm.data.get()[byte_num] =
87 (unsigned char)
88 ((pm.data.get()[byte_num] & ~(1 << bit_position))
89 | (value << bit_position));
90 }
91
92 template<typename IndexMap>
93 inline one_bit_color_map<IndexMap>
make_one_bit_color_map(std::size_t n,const IndexMap & index_map)94 make_one_bit_color_map(std::size_t n, const IndexMap& index_map)
95 {
96 return one_bit_color_map<IndexMap>(n, index_map);
97 }
98
99 } // end namespace boost
100
101 #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/one_bit_color_map.hpp>)
102
103 #endif // BOOST_ONE_BIT_COLOR_MAP_HPP
104