1 // Copyright 2005 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 // Indexed properties -- used for CSR and CSR-like graphs 12 13 #ifndef BOOST_GRAPH_INDEXED_PROPERTIES_HPP 14 #define BOOST_GRAPH_INDEXED_PROPERTIES_HPP 15 16 #include <vector> 17 #include <utility> 18 #include <algorithm> 19 #include <climits> 20 #include <iterator> 21 #include <boost/graph/graph_traits.hpp> 22 #include <boost/graph/properties.hpp> 23 #include <boost/iterator/counting_iterator.hpp> 24 #include <boost/integer.hpp> 25 #include <boost/iterator/iterator_facade.hpp> 26 #include <boost/property_map/property_map.hpp> 27 #include <boost/mpl/if.hpp> 28 29 namespace boost { 30 namespace detail { 31 32 template<typename Derived, typename Property, typename Descriptor, typename IndexMap> 33 class indexed_vertex_properties 34 { 35 public: 36 typedef no_property vertex_property_type; 37 typedef Property vertex_bundled; 38 typedef iterator_property_map< 39 typename std::vector<Property>::iterator, 40 IndexMap> vertex_map_type; 41 typedef iterator_property_map< 42 typename std::vector<Property>::const_iterator, 43 IndexMap> const_vertex_map_type; 44 45 // Directly access a vertex or edge bundle operator [](Descriptor v)46 Property& operator[](Descriptor v) 47 { return m_vertex_properties[get(vertex_index, derived(), v)]; } 48 operator [](Descriptor v) const49 const Property& operator[](Descriptor v) const 50 { return m_vertex_properties[get(vertex_index, derived(), v)]; } 51 get_vertex_bundle(const IndexMap & index_map=IndexMap ())52 vertex_map_type get_vertex_bundle(const IndexMap& index_map = IndexMap()) { 53 return vertex_map_type(m_vertex_properties.begin(), index_map); 54 } 55 get_vertex_bundle(const IndexMap & index_map=IndexMap ()) const56 const_vertex_map_type get_vertex_bundle(const IndexMap& index_map = IndexMap()) const { 57 return const_vertex_map_type(m_vertex_properties.begin(), index_map); 58 } 59 60 protected: 61 // Default-construct with no property values indexed_vertex_properties()62 indexed_vertex_properties() {} 63 64 // Initialize with n default-constructed property values indexed_vertex_properties(std::size_t n)65 indexed_vertex_properties(std::size_t n) : m_vertex_properties(n) { } 66 67 public: 68 // Clear the properties vector clear()69 void clear() 70 { 71 m_vertex_properties.clear(); 72 } 73 74 // Resize the properties vector resize(std::size_t n)75 void resize(std::size_t n) 76 { 77 m_vertex_properties.resize(n); 78 } 79 80 // Reserve space in the vector of properties reserve(std::size_t n)81 void reserve(std::size_t n) 82 { 83 m_vertex_properties.reserve(n); 84 } 85 86 // Add a new property value to the back push_back(const Property & prop)87 void push_back(const Property& prop) 88 { 89 m_vertex_properties.push_back(prop); 90 } 91 92 // Write an element by raw index write_by_index(std::size_t idx,const Property & prop)93 void write_by_index(std::size_t idx, const Property& prop) 94 { 95 m_vertex_properties[idx] = prop; 96 } 97 98 // Access to the derived object derived()99 Derived& derived() { return *static_cast<Derived*>(this); } 100 derived() const101 const Derived& derived() const 102 { return *static_cast<const Derived*>(this); } 103 104 public: // should be private, but friend templates not portable 105 std::vector<Property> m_vertex_properties; 106 }; 107 108 template<typename Derived, typename Descriptor, typename IndexMap> 109 class indexed_vertex_properties<Derived, void, Descriptor, IndexMap> 110 { 111 struct secret {}; 112 113 public: 114 typedef no_property vertex_property_type; 115 typedef void vertex_bundled; 116 typedef secret vertex_map_type; 117 typedef secret const_vertex_map_type; 118 operator [](secret)119 secret operator[](secret) { return secret(); } 120 get_vertex_bundle() const121 vertex_map_type get_vertex_bundle() const { 122 return vertex_map_type(); 123 } 124 125 protected: 126 // All operations do nothing. indexed_vertex_properties()127 indexed_vertex_properties() { } indexed_vertex_properties(std::size_t)128 indexed_vertex_properties(std::size_t) { } 129 130 public: clear()131 void clear() { } resize(std::size_t)132 void resize(std::size_t) { } reserve(std::size_t)133 void reserve(std::size_t) { } 134 }; 135 136 template<typename Derived, typename Property, typename Descriptor, typename IndexMap> 137 class indexed_edge_properties 138 { 139 public: 140 typedef no_property edge_property_type; 141 typedef Property edge_bundled; 142 typedef Property edge_push_back_type; 143 typedef iterator_property_map< 144 typename std::vector<Property>::iterator, 145 IndexMap> edge_map_type; 146 typedef iterator_property_map< 147 typename std::vector<Property>::const_iterator, 148 IndexMap> const_edge_map_type; 149 150 // Directly access a edge or edge bundle operator [](Descriptor v)151 Property& operator[](Descriptor v) 152 { return m_edge_properties[get(edge_index, derived(), v)]; } 153 operator [](Descriptor v) const154 const Property& operator[](Descriptor v) const 155 { return m_edge_properties[get(edge_index, derived(), v)]; } 156 get_edge_bundle(const IndexMap & index_map=IndexMap ())157 edge_map_type get_edge_bundle(const IndexMap& index_map = IndexMap()) { 158 return edge_map_type(m_edge_properties.begin(), index_map); 159 } 160 get_edge_bundle(const IndexMap & index_map=IndexMap ()) const161 const_edge_map_type get_edge_bundle(const IndexMap& index_map = IndexMap()) const { 162 return const_edge_map_type(m_edge_properties.begin(), index_map); 163 } 164 165 protected: 166 // Default-construct with no property values indexed_edge_properties()167 indexed_edge_properties() {} 168 169 // Initialize with n default-constructed property values indexed_edge_properties(std::size_t n)170 indexed_edge_properties(std::size_t n) : m_edge_properties(n) { } 171 172 // Get the size of the properties vector size() const173 std::size_t size() const 174 { 175 return m_edge_properties.size(); 176 } 177 178 // Clear the properties vector clear()179 void clear() 180 { 181 m_edge_properties.clear(); 182 } 183 184 // Resize the properties vector resize(std::size_t n)185 void resize(std::size_t n) 186 { 187 m_edge_properties.resize(n); 188 } 189 190 // Reserve space in the vector of properties reserve(std::size_t n)191 void reserve(std::size_t n) 192 { 193 m_edge_properties.reserve(n); 194 } 195 196 // Write an element by raw index write_by_index(std::size_t idx,const Property & prop)197 void write_by_index(std::size_t idx, const Property& prop) 198 { 199 m_edge_properties[idx] = prop; 200 } 201 202 public: 203 // Add a new property value to the back push_back(const Property & prop)204 void push_back(const Property& prop) 205 { 206 m_edge_properties.push_back(prop); 207 } 208 209 // Move range of properties backwards move_range(std::size_t src_begin,std::size_t src_end,std::size_t dest_begin)210 void move_range(std::size_t src_begin, std::size_t src_end, std::size_t dest_begin) { 211 std::copy_backward( 212 m_edge_properties.begin() + src_begin, 213 m_edge_properties.begin() + src_end, 214 m_edge_properties.begin() + dest_begin + (src_end - src_begin)); 215 } 216 217 typedef typename std::vector<Property>::iterator iterator; begin()218 iterator begin() {return m_edge_properties.begin();} end()219 iterator end() {return m_edge_properties.end();} 220 221 private: 222 // Access to the derived object derived()223 Derived& derived() { return *static_cast<Derived*>(this); } 224 derived() const225 const Derived& derived() const 226 { return *static_cast<const Derived*>(this); } 227 228 public: // should be private, but friend templates not portable 229 std::vector<Property> m_edge_properties; 230 }; 231 232 struct dummy_no_property_iterator 233 : public boost::iterator_facade<dummy_no_property_iterator, no_property, std::random_access_iterator_tag> { 234 mutable no_property prop; dereferenceboost::detail::dummy_no_property_iterator235 no_property& dereference() const {return prop;} equalboost::detail::dummy_no_property_iterator236 bool equal(const dummy_no_property_iterator&) const {return true;} incrementboost::detail::dummy_no_property_iterator237 void increment() {} decrementboost::detail::dummy_no_property_iterator238 void decrement() {} advanceboost::detail::dummy_no_property_iterator239 void advance(std::ptrdiff_t) {} distance_toboost::detail::dummy_no_property_iterator240 std::ptrdiff_t distance_to(const dummy_no_property_iterator) const {return 0;} 241 }; 242 243 template<typename Derived, typename Descriptor, typename IndexMap> 244 class indexed_edge_properties<Derived, void, Descriptor, IndexMap> 245 { 246 struct secret {}; 247 248 public: 249 typedef no_property edge_property_type; 250 typedef void edge_bundled; 251 typedef void* edge_push_back_type; 252 typedef secret edge_map_type; 253 typedef secret const_edge_map_type; 254 operator [](secret)255 secret operator[](secret) { return secret(); } write_by_index(std::size_t,const no_property &)256 void write_by_index(std::size_t /*idx*/, const no_property& /*prop*/) {} 257 get_edge_bundle(const IndexMap &=IndexMap ()) const258 edge_map_type get_edge_bundle(const IndexMap& = IndexMap()) const { 259 return edge_map_type(); 260 } 261 262 protected: 263 // All operations do nothing. indexed_edge_properties()264 indexed_edge_properties() { } indexed_edge_properties(std::size_t)265 indexed_edge_properties(std::size_t) { } size() const266 std::size_t size() const {return 0;} clear()267 void clear() { } resize(std::size_t)268 void resize(std::size_t) { } reserve(std::size_t)269 void reserve(std::size_t) { } 270 271 public: push_back(const edge_push_back_type &)272 void push_back(const edge_push_back_type&) { } move_range(std::size_t,std::size_t,std::size_t)273 void move_range(std::size_t /*src_begin*/, std::size_t /*src_end*/, std::size_t /*dest_begin*/) {} 274 275 typedef dummy_no_property_iterator iterator; begin()276 iterator begin() {return dummy_no_property_iterator();} end()277 iterator end() {return dummy_no_property_iterator();} 278 279 }; 280 281 } 282 } 283 284 #endif // BOOST_GRAPH_INDEXED_PROPERTIES_HPP 285