123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284 |
- // Copyright 2005 The Trustees of Indiana University.
- // Distributed under the Boost Software License, Version 1.0.
- // (See accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- // Authors: Jeremiah Willcock
- // Douglas Gregor
- // Andrew Lumsdaine
- // Indexed properties -- used for CSR and CSR-like graphs
- #ifndef BOOST_GRAPH_INDEXED_PROPERTIES_HPP
- #define BOOST_GRAPH_INDEXED_PROPERTIES_HPP
- #include <vector>
- #include <utility>
- #include <algorithm>
- #include <climits>
- #include <iterator>
- #include <boost/graph/graph_traits.hpp>
- #include <boost/graph/properties.hpp>
- #include <boost/iterator/counting_iterator.hpp>
- #include <boost/integer.hpp>
- #include <boost/iterator/iterator_facade.hpp>
- #include <boost/property_map/property_map.hpp>
- #include <boost/mpl/if.hpp>
- namespace boost {
- namespace detail {
- template<typename Derived, typename Property, typename Descriptor, typename IndexMap>
- class indexed_vertex_properties
- {
- public:
- typedef no_property vertex_property_type;
- typedef Property vertex_bundled;
- typedef iterator_property_map<
- typename std::vector<Property>::iterator,
- IndexMap> vertex_map_type;
- typedef iterator_property_map<
- typename std::vector<Property>::const_iterator,
- IndexMap> const_vertex_map_type;
- // Directly access a vertex or edge bundle
- Property& operator[](Descriptor v)
- { return m_vertex_properties[get(vertex_index, derived(), v)]; }
- const Property& operator[](Descriptor v) const
- { return m_vertex_properties[get(vertex_index, derived(), v)]; }
- vertex_map_type get_vertex_bundle(const IndexMap& index_map = IndexMap()) {
- return vertex_map_type(m_vertex_properties.begin(), index_map);
- }
- const_vertex_map_type get_vertex_bundle(const IndexMap& index_map = IndexMap()) const {
- return const_vertex_map_type(m_vertex_properties.begin(), index_map);
- }
- protected:
- // Default-construct with no property values
- indexed_vertex_properties() {}
- // Initialize with n default-constructed property values
- indexed_vertex_properties(std::size_t n) : m_vertex_properties(n) { }
- public:
- // Clear the properties vector
- void clear()
- {
- m_vertex_properties.clear();
- }
- // Resize the properties vector
- void resize(std::size_t n)
- {
- m_vertex_properties.resize(n);
- }
- // Reserve space in the vector of properties
- void reserve(std::size_t n)
- {
- m_vertex_properties.reserve(n);
- }
- // Add a new property value to the back
- void push_back(const Property& prop)
- {
- m_vertex_properties.push_back(prop);
- }
- // Write an element by raw index
- void write_by_index(std::size_t idx, const Property& prop)
- {
- m_vertex_properties[idx] = prop;
- }
- // Access to the derived object
- Derived& derived() { return *static_cast<Derived*>(this); }
- const Derived& derived() const
- { return *static_cast<const Derived*>(this); }
- public: // should be private, but friend templates not portable
- std::vector<Property> m_vertex_properties;
- };
- template<typename Derived, typename Descriptor, typename IndexMap>
- class indexed_vertex_properties<Derived, void, Descriptor, IndexMap>
- {
- struct secret {};
- public:
- typedef no_property vertex_property_type;
- typedef void vertex_bundled;
- typedef secret vertex_map_type;
- typedef secret const_vertex_map_type;
- secret operator[](secret) { return secret(); }
- vertex_map_type get_vertex_bundle() const {
- return vertex_map_type();
- }
- protected:
- // All operations do nothing.
- indexed_vertex_properties() { }
- indexed_vertex_properties(std::size_t) { }
- public:
- void clear() { }
- void resize(std::size_t) { }
- void reserve(std::size_t) { }
- };
- template<typename Derived, typename Property, typename Descriptor, typename IndexMap>
- class indexed_edge_properties
- {
- public:
- typedef no_property edge_property_type;
- typedef Property edge_bundled;
- typedef Property edge_push_back_type;
- typedef iterator_property_map<
- typename std::vector<Property>::iterator,
- IndexMap> edge_map_type;
- typedef iterator_property_map<
- typename std::vector<Property>::const_iterator,
- IndexMap> const_edge_map_type;
- // Directly access a edge or edge bundle
- Property& operator[](Descriptor v)
- { return m_edge_properties[get(edge_index, derived(), v)]; }
- const Property& operator[](Descriptor v) const
- { return m_edge_properties[get(edge_index, derived(), v)]; }
- edge_map_type get_edge_bundle(const IndexMap& index_map = IndexMap()) {
- return edge_map_type(m_edge_properties.begin(), index_map);
- }
- const_edge_map_type get_edge_bundle(const IndexMap& index_map = IndexMap()) const {
- return const_edge_map_type(m_edge_properties.begin(), index_map);
- }
- protected:
- // Default-construct with no property values
- indexed_edge_properties() {}
- // Initialize with n default-constructed property values
- indexed_edge_properties(std::size_t n) : m_edge_properties(n) { }
- // Get the size of the properties vector
- std::size_t size() const
- {
- return m_edge_properties.size();
- }
- // Clear the properties vector
- void clear()
- {
- m_edge_properties.clear();
- }
- // Resize the properties vector
- void resize(std::size_t n)
- {
- m_edge_properties.resize(n);
- }
- // Reserve space in the vector of properties
- void reserve(std::size_t n)
- {
- m_edge_properties.reserve(n);
- }
- // Write an element by raw index
- void write_by_index(std::size_t idx, const Property& prop)
- {
- m_edge_properties[idx] = prop;
- }
- public:
- // Add a new property value to the back
- void push_back(const Property& prop)
- {
- m_edge_properties.push_back(prop);
- }
- // Move range of properties backwards
- void move_range(std::size_t src_begin, std::size_t src_end, std::size_t dest_begin) {
- std::copy_backward(
- m_edge_properties.begin() + src_begin,
- m_edge_properties.begin() + src_end,
- m_edge_properties.begin() + dest_begin + (src_end - src_begin));
- }
- typedef typename std::vector<Property>::iterator iterator;
- iterator begin() {return m_edge_properties.begin();}
- iterator end() {return m_edge_properties.end();}
- private:
- // Access to the derived object
- Derived& derived() { return *static_cast<Derived*>(this); }
- const Derived& derived() const
- { return *static_cast<const Derived*>(this); }
- public: // should be private, but friend templates not portable
- std::vector<Property> m_edge_properties;
- };
- struct dummy_no_property_iterator
- : public boost::iterator_facade<dummy_no_property_iterator, no_property, std::random_access_iterator_tag> {
- mutable no_property prop;
- no_property& dereference() const {return prop;}
- bool equal(const dummy_no_property_iterator&) const {return true;}
- void increment() {}
- void decrement() {}
- void advance(std::ptrdiff_t) {}
- std::ptrdiff_t distance_to(const dummy_no_property_iterator) const {return 0;}
- };
- template<typename Derived, typename Descriptor, typename IndexMap>
- class indexed_edge_properties<Derived, void, Descriptor, IndexMap>
- {
- struct secret {};
- public:
- typedef no_property edge_property_type;
- typedef void edge_bundled;
- typedef void* edge_push_back_type;
- typedef secret edge_map_type;
- typedef secret const_edge_map_type;
- secret operator[](secret) { return secret(); }
- void write_by_index(std::size_t /*idx*/, const no_property& /*prop*/) {}
- edge_map_type get_edge_bundle(const IndexMap& = IndexMap()) const {
- return edge_map_type();
- }
- protected:
- // All operations do nothing.
- indexed_edge_properties() { }
- indexed_edge_properties(std::size_t) { }
- std::size_t size() const {return 0;}
- void clear() { }
- void resize(std::size_t) { }
- void reserve(std::size_t) { }
- public:
- void push_back(const edge_push_back_type&) { }
- void move_range(std::size_t /*src_begin*/, std::size_t /*src_end*/, std::size_t /*dest_begin*/) {}
- typedef dummy_no_property_iterator iterator;
- iterator begin() {return dummy_no_property_iterator();}
- iterator end() {return dummy_no_property_iterator();}
- };
- }
- }
- #endif // BOOST_GRAPH_INDEXED_PROPERTIES_HPP
|