boost/graph/exterior_property.hpp

   1 // (C) Copyright 2007-2009 Andrew Sutton
   2 //
   3 // Use, modification and distribution are subject to the
   4 // Boost Software License, Version 1.0 (See accompanying file
   5 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #ifndef BOOST_GRAPH_EXTERIOR_PROPERTY_HPP
   8 #define BOOST_GRAPH_EXTERIOR_PROPERTY_HPP
   9
  10 #include <vector>
  11 #include <boost/graph/property_maps/container_property_map.hpp>
  12 #include <boost/graph/property_maps/matrix_property_map.hpp>
  13
  14 namespace boost {
  15 namespace detail {
  16     // The vector matrix provides a little abstraction over vector
  17     // types that makes matrices easier to work with. Note that it's
  18     // non-copyable, meaning you should be passing it by value.
  19     template <typename Value>
  20     struct vector_matrix
  21     {
  22         typedef std::vector<Value> container_type;
  23         typedef std::vector<container_type> matrix_type;
  24
  25         typedef container_type value_type;
  26         typedef container_type& reference;
  27         typedef const container_type const_reference;
  28         typedef container_type* pointer;
  29         typedef typename matrix_type::size_type size_type;
  30
  31         // Instantiate the matrix over n elements (creates an nxn matrix).
  32         // The graph has to be passed in order to ensure the index maps
  33         // are constructed correctly when returning indexible elements.
  34         inline vector_matrix(size_type n)
  35             : m_matrix(n, container_type(n))
  36         { }
  37
  38         inline reference operator [](size_type n)
  39         { return m_matrix[n]; }
  40
  41         inline const_reference operator [](size_type n) const
  42         { return m_matrix[n]; }
  43
  44         matrix_type m_matrix;
  45     };
  46 } /* namespace detail */
  47
  48 /**
  49  * The exterior_property metafunction defines an appropriate set of types for
  50  * creating an exterior property. An exterior property is comprised of a both
  51  * a container and a property map that acts as its abstraction. An extension
  52  * of this metafunction will select an appropriate "matrix" property that
  53  * records values for pairs of vertices.
  54  *
  55  * @todo This does not currently support the ability to define exterior
  56  * properties for graph types that do not model the IndexGraph concepts. A
  57  * solution should not be especially difficult, but will require an extension
  58  * of type traits to affect the type selection.
  59  */
  60 template <typename Graph, typename Key, typename Value>
  61 struct exterior_property
  62 {
  63     typedef Key key_type;
  64     typedef Value value_type;
  65
  66     typedef std::vector<Value> container_type;
  67     typedef container_property_map<Graph, Key, container_type> map_type;
  68
  69     typedef detail::vector_matrix<Value> matrix_type;
  70     typedef matrix_property_map<Graph, Key, matrix_type> matrix_map_type;
  71
  72 private:
  73     exterior_property() { }
  74     exterior_property(const exterior_property&) { }
  75 };
  76
  77 /**
  78  * Define a the container and property map types requried to create an exterior
  79  * vertex property for the given value type. The Graph parameter is required to
  80  * model the VertexIndexGraph concept.
  81  */
  82 template <typename Graph, typename Value>
  83 struct exterior_vertex_property
  84 {
  85     typedef exterior_property<
  86             Graph, typename graph_traits<Graph>::vertex_descriptor, Value
  87         > property_type;
  88     typedef typename property_type::key_type key_type;
  89     typedef typename property_type::value_type value_type;
  90     typedef typename property_type::container_type container_type;
  91     typedef typename property_type::map_type map_type;
  92     typedef typename property_type::matrix_type matrix_type;
  93     typedef typename property_type::matrix_map_type matrix_map_type;
  94 };
  95
  96 /**
  97  * Define a the container and property map types requried to create an exterior
  98  * edge property for the given value type. The Graph parameter is required to
  99  * model the EdgeIndexGraph concept.
 100  */
 101 template <typename Graph, typename Value>
 102 struct exterior_edge_property
 103 {
 104     typedef exterior_property<
 105             Graph, typename graph_traits<Graph>::edge_descriptor, Value
 106         > property_type;
 107     typedef typename property_type::key_type key_type;
 108     typedef typename property_type::value_type value_type;
 109     typedef typename property_type::container_type container_type;
 110     typedef typename property_type::map_type map_type;
 111     typedef typename property_type::matrix_type matrix_type;
 112     typedef typename property_type::matrix_map_type matrix_map_type;
 113 };
 114
 115 } /* namespace boost */
 116
 117 #endif