Chris@16: // (C) Copyright 2007-2009 Andrew Sutton
Chris@16: //
Chris@16: // Use, modification and distribution are subject to the
Chris@16: // Boost Software License, Version 1.0 (See accompanying file
Chris@16: // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_EXTERIOR_PROPERTY_HPP
Chris@16: #define BOOST_GRAPH_EXTERIOR_PROPERTY_HPP
Chris@16: 
Chris@16: #include <vector>
Chris@16: #include <boost/graph/property_maps/container_property_map.hpp>
Chris@16: #include <boost/graph/property_maps/matrix_property_map.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace detail {
Chris@16:     // The vector matrix provides a little abstraction over vector
Chris@16:     // types that makes matrices easier to work with. Note that it's
Chris@16:     // non-copyable, meaning you should be passing it by value.
Chris@16:     template <typename Value>
Chris@16:     struct vector_matrix
Chris@16:     {
Chris@16:         typedef std::vector<Value> container_type;
Chris@16:         typedef std::vector<container_type> matrix_type;
Chris@16: 
Chris@16:         typedef container_type value_type;
Chris@16:         typedef container_type& reference;
Chris@16:         typedef const container_type const_reference;
Chris@16:         typedef container_type* pointer;
Chris@16:         typedef typename matrix_type::size_type size_type;
Chris@16: 
Chris@16:         // Instantiate the matrix over n elements (creates an nxn matrix).
Chris@16:         // The graph has to be passed in order to ensure the index maps
Chris@16:         // are constructed correctly when returning indexible elements.
Chris@16:         inline vector_matrix(size_type n)
Chris@16:             : m_matrix(n, container_type(n))
Chris@16:         { }
Chris@16: 
Chris@16:         inline reference operator [](size_type n)
Chris@16:         { return m_matrix[n]; }
Chris@16: 
Chris@16:         inline const_reference operator [](size_type n) const
Chris@16:         { return m_matrix[n]; }
Chris@16: 
Chris@16:         matrix_type m_matrix;
Chris@16:     };
Chris@16: } /* namespace detail */
Chris@16: 
Chris@16: /**
Chris@16:  * The exterior_property metafunction defines an appropriate set of types for
Chris@16:  * creating an exterior property. An exterior property is comprised of a both
Chris@16:  * a container and a property map that acts as its abstraction. An extension
Chris@16:  * of this metafunction will select an appropriate "matrix" property that
Chris@16:  * records values for pairs of vertices.
Chris@16:  *
Chris@16:  * @todo This does not currently support the ability to define exterior
Chris@16:  * properties for graph types that do not model the IndexGraph concepts. A
Chris@16:  * solution should not be especially difficult, but will require an extension
Chris@16:  * of type traits to affect the type selection.
Chris@16:  */
Chris@16: template <typename Graph, typename Key, typename Value>
Chris@16: struct exterior_property
Chris@16: {
Chris@16:     typedef Key key_type;
Chris@16:     typedef Value value_type;
Chris@16: 
Chris@16:     typedef std::vector<Value> container_type;
Chris@16:     typedef container_property_map<Graph, Key, container_type> map_type;
Chris@16: 
Chris@16:     typedef detail::vector_matrix<Value> matrix_type;
Chris@16:     typedef matrix_property_map<Graph, Key, matrix_type> matrix_map_type;
Chris@16: 
Chris@16: private:
Chris@16:     exterior_property() { }
Chris@16:     exterior_property(const exterior_property&) { }
Chris@16: };
Chris@16: 
Chris@16: /**
Chris@16:  * Define a the container and property map types requried to create an exterior
Chris@16:  * vertex property for the given value type. The Graph parameter is required to
Chris@16:  * model the VertexIndexGraph concept.
Chris@16:  */
Chris@16: template <typename Graph, typename Value>
Chris@16: struct exterior_vertex_property
Chris@16: {
Chris@16:     typedef exterior_property<
Chris@16:             Graph, typename graph_traits<Graph>::vertex_descriptor, Value
Chris@16:         > property_type;
Chris@16:     typedef typename property_type::key_type key_type;
Chris@16:     typedef typename property_type::value_type value_type;
Chris@16:     typedef typename property_type::container_type container_type;
Chris@16:     typedef typename property_type::map_type map_type;
Chris@16:     typedef typename property_type::matrix_type matrix_type;
Chris@16:     typedef typename property_type::matrix_map_type matrix_map_type;
Chris@16: };
Chris@16: 
Chris@16: /**
Chris@16:  * Define a the container and property map types requried to create an exterior
Chris@16:  * edge property for the given value type. The Graph parameter is required to
Chris@16:  * model the EdgeIndexGraph concept.
Chris@16:  */
Chris@16: template <typename Graph, typename Value>
Chris@16: struct exterior_edge_property
Chris@16: {
Chris@16:     typedef exterior_property<
Chris@16:             Graph, typename graph_traits<Graph>::edge_descriptor, Value
Chris@16:         > property_type;
Chris@16:     typedef typename property_type::key_type key_type;
Chris@16:     typedef typename property_type::value_type value_type;
Chris@16:     typedef typename property_type::container_type container_type;
Chris@16:     typedef typename property_type::map_type map_type;
Chris@16:     typedef typename property_type::matrix_type matrix_type;
Chris@16:     typedef typename property_type::matrix_map_type matrix_map_type;
Chris@16: };
Chris@16: 
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif