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
14namespace boost
15{
16namespace detail
17{
18 // The vector matrix provides a little abstraction over vector
19 // types that makes matrices easier to work with.
20 template < typename Value > 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 n by n 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) : m_matrix(n, container_type(n)) {}
35
36 inline reference operator[](size_type n) { return m_matrix[n]; }
37
38 inline const_reference operator[](size_type n) const
39 {
40 return m_matrix[n];
41 }
42
43 matrix_type m_matrix;
44 };
45} /* namespace detail */
46
47/**
48 * The exterior_property metafunction defines an appropriate set of types for
49 * creating an exterior property. An exterior property is comprised of a both
50 * a container and a property map that acts as its abstraction. An extension
51 * of this metafunction will select an appropriate "matrix" property that
52 * records values for pairs of vertices.
53 *
54 * @todo This does not currently support the ability to define exterior
55 * properties for graph types that do not model the IndexGraph concepts. A
56 * solution should not be especially difficult, but will require an extension
57 * of type traits to affect the type selection.
58 */
59template < typename Graph, typename Key, typename Value >
60struct exterior_property
61{
62 typedef Key key_type;
63 typedef Value value_type;
64
65 typedef std::vector< Value > container_type;
66 typedef container_property_map< Graph, Key, container_type > map_type;
67
68 typedef detail::vector_matrix< Value > matrix_type;
69 typedef matrix_property_map< Graph, Key, matrix_type > matrix_map_type;
70
71private:
72 exterior_property() {}
73 exterior_property(const exterior_property&) {}
74};
75
76/**
77 * Define a the container and property map types requried to create an exterior
78 * vertex property for the given value type. The Graph parameter is required to
79 * model the VertexIndexGraph concept.
80 */
81template < typename Graph, typename Value > struct exterior_vertex_property
82{
83 typedef exterior_property< Graph,
84 typename graph_traits< Graph >::vertex_descriptor, Value >
85 property_type;
86 typedef typename property_type::key_type key_type;
87 typedef typename property_type::value_type value_type;
88 typedef typename property_type::container_type container_type;
89 typedef typename property_type::map_type map_type;
90 typedef typename property_type::matrix_type matrix_type;
91 typedef typename property_type::matrix_map_type matrix_map_type;
92};
93
94/**
95 * Define a the container and property map types requried to create an exterior
96 * edge property for the given value type. The Graph parameter is required to
97 * model the EdgeIndexGraph concept.
98 */
99template < typename Graph, typename Value > struct exterior_edge_property
100{
101 typedef exterior_property< Graph,
102 typename graph_traits< Graph >::edge_descriptor, Value >
103 property_type;
104 typedef typename property_type::key_type key_type;
105 typedef typename property_type::value_type value_type;
106 typedef typename property_type::container_type container_type;
107 typedef typename property_type::map_type map_type;
108 typedef typename property_type::matrix_type matrix_type;
109 typedef typename property_type::matrix_map_type matrix_map_type;
110};
111
112} /* namespace boost */
113
114#endif
115

source code of boost/libs/graph/include/boost/graph/exterior_property.hpp