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 |
118 | |