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 {
15namespace 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 */
60template <typename Graph, typename Key, typename Value>
61struct 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
72private:
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 */
82template <typename Graph, typename Value>
83struct 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 */
101template <typename Graph, typename Value>
102struct 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

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