boost/graph/exterior_property.hpp

0001 // (C) Copyright 2007-2009 Andrew Sutton
0002 //
0003 // Use, modification and distribution are subject to the
0004 // Boost Software License, Version 1.0 (See accompanying file
0005 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
0006
0007 #ifndef BOOST_GRAPH_EXTERIOR_PROPERTY_HPP
0008 #define BOOST_GRAPH_EXTERIOR_PROPERTY_HPP
0009
0010 #include <vector>
0011 #include <boost/graph/property_maps/container_property_map.hpp>
0012 #include <boost/graph/property_maps/matrix_property_map.hpp>
0013
0014 namespace boost
0015 {
0016 namespace detail
0017 {
0018     // The vector matrix provides a little abstraction over vector
0019     // types that makes matrices easier to work with.
0020     template < typename Value > struct vector_matrix
0021     {
0022         typedef std::vector< Value > container_type;
0023         typedef std::vector< container_type > matrix_type;
0024
0025         typedef container_type value_type;
0026         typedef container_type& reference;
0027         typedef const container_type const_reference;
0028         typedef container_type* pointer;
0029         typedef typename matrix_type::size_type size_type;
0030
0031         // Instantiate the matrix over n elements (creates an n by n matrix).
0032         // The graph has to be passed in order to ensure the index maps
0033         // are constructed correctly when returning indexible elements.
0034         inline vector_matrix(size_type n) : m_matrix(n, container_type(n)) {}
0035
0036         inline reference operator[](size_type n) { return m_matrix[n]; }
0037
0038         inline const_reference operator[](size_type n) const
0039         {
0040             return m_matrix[n];
0041         }
0042
0043         matrix_type m_matrix;
0044     };
0045 } /* namespace detail */
0046
0047 /**
0048  * The exterior_property metafunction defines an appropriate set of types for
0049  * creating an exterior property. An exterior property is comprised of a both
0050  * a container and a property map that acts as its abstraction. An extension
0051  * of this metafunction will select an appropriate "matrix" property that
0052  * records values for pairs of vertices.
0053  *
0054  * @todo This does not currently support the ability to define exterior
0055  * properties for graph types that do not model the IndexGraph concepts. A
0056  * solution should not be especially difficult, but will require an extension
0057  * of type traits to affect the type selection.
0058  */
0059 template < typename Graph, typename Key, typename Value >
0060 struct exterior_property
0061 {
0062     typedef Key key_type;
0063     typedef Value value_type;
0064
0065     typedef std::vector< Value > container_type;
0066     typedef container_property_map< Graph, Key, container_type > map_type;
0067
0068     typedef detail::vector_matrix< Value > matrix_type;
0069     typedef matrix_property_map< Graph, Key, matrix_type > matrix_map_type;
0070
0071 private:
0072     exterior_property() {}
0073     exterior_property(const exterior_property&) {}
0074 };
0075
0076 /**
0077  * Define a the container and property map types requried to create an exterior
0078  * vertex property for the given value type. The Graph parameter is required to
0079  * model the VertexIndexGraph concept.
0080  */
0081 template < typename Graph, typename Value > struct exterior_vertex_property
0082 {
0083     typedef exterior_property< Graph,
0084         typename graph_traits< Graph >::vertex_descriptor, Value >
0085         property_type;
0086     typedef typename property_type::key_type key_type;
0087     typedef typename property_type::value_type value_type;
0088     typedef typename property_type::container_type container_type;
0089     typedef typename property_type::map_type map_type;
0090     typedef typename property_type::matrix_type matrix_type;
0091     typedef typename property_type::matrix_map_type matrix_map_type;
0092 };
0093
0094 /**
0095  * Define a the container and property map types requried to create an exterior
0096  * edge property for the given value type. The Graph parameter is required to
0097  * model the EdgeIndexGraph concept.
0098  */
0099 template < typename Graph, typename Value > struct exterior_edge_property
0100 {
0101     typedef exterior_property< Graph,
0102         typename graph_traits< Graph >::edge_descriptor, Value >
0103         property_type;
0104     typedef typename property_type::key_type key_type;
0105     typedef typename property_type::value_type value_type;
0106     typedef typename property_type::container_type container_type;
0107     typedef typename property_type::map_type map_type;
0108     typedef typename property_type::matrix_type matrix_type;
0109     typedef typename property_type::matrix_map_type matrix_map_type;
0110 };
0111
0112 } /* namespace boost */
0113
0114 #endif