1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<!--
Copyright Doug Gregor 2004. Use, modification and
distribution is subject to the Boost Software License, Version
1.0. (See accompanying file LICENSE_1_0.txt or copy at
http://www.boost.org/LICENSE_1_0.txt)
For more information, see http://www.boost.org
-->
<head>
<title>Bundled Properties</title>
</head>
<body BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
ALINK="#ff0000">
<IMG SRC="../../../boost.png"
ALT="C++ Boost" width="277" height="86"/>
<h1>Bundled Properties</h1>
<p>Class templates <code><a
href="adjacency_list.html">adjacency_list</a></code> and
<code><a href="adjacency_matrix.html">adjacency_matrix</a></code> support
the introduction of named properties via <a
href="using_adjacency_list.html#sec:adjacency-list-properties">internal
properties</a>. However, this method is cumbersome in many uses,
where it would be more intuitive to just specify a structure or
class that contains internal properties for edges or
vertices. Bundled properties allow one to use
<code>adjacency_list</code> and <code>adjacency_matrix</code> in this
manner, providing a simple
way to introduce and access any number of internal properties
for vertices and edges.</p>
<p>One can introduce bundled properties into an
either graph type by providing a user-defined class
type for the <code>VertexProperties</code> or
<code>EdgeProperties</code> template arguments. The user-defined
class may alternatively be placed at the end of a
<code>property</code> list, replacing the (implicit)
<code>boost::no_property</code> argument.</p>
<h2>Example: Route planning</h2>
<p>Consider the implementation of a simple route planner that
should find the shortest directions from one city to another
via a set of highways. The vertices of the graph are cities,
and we may wish to store several bits of information about the
city within each vertex:</p>
<pre>
struct City
{
string name;
int population;
vector<int> zipcodes;
};
</pre>
<p>
The edges in the graph represent highways, which also have several interesting
attributes:
</p>
<pre>
struct Highway
{
string name;
double miles;
int speed_limit;
int lanes;
bool divided;
};
</pre>
<p>With bundled properties, we can directly use the <code>City</code> and
<code>Highway</code> structures to define the graph:</p>
<pre>
typedef boost::adjacency_list<
boost::listS, boost::vecS, boost::bidirectionalS,
City, Highway>
Map;
</pre>
<p>Without bundled properties, translating this example directly
into an instantiation of <code>adjacency_list</code> would
involve several custom properties and would result in a type
like this:</p>
<pre>
typedef boost::adjacency_list<
boost::listS, boost::vecS, boost::bidirectionalS,
// Vertex properties
boost::property<boost::vertex_name_t, std::string,
boost::property<population_t, int,
boost::property<zipcodes_t, std::vector<int> > > >,
// Edge properties
boost::property<boost::edge_name_t, std::string,
boost::property<boost::edge_length_t, double,
boost::property<edge_speed_limit_t, int,
boost::property<edge_lanes_t, int,
boost::property<edge_divided, bool> > > > > >
Map;
</pre>
<p>
Bundling vertex and edge properties greatly simplifies the declaration of
graphs.
</p>
<p>
In addition to vertex and edge bundles, we can also bundle properties of the
graph itself. Suppopse we extend the application to include a portfolio of
route-planning maps for different countries. In addition to the <code>City</code>
and <code>Highway</code> bundles above, we can declare a graph bundle,
<code>Country</Code>.
</p>
<pre>
struct Country {
string name;
bool use_right; // Drive on the left or right
bool use_metric; // mph or km/h
};
</pre>
<p>The graph would now be declared as:</p>
<pre>
<pre>
typedef boost::adjacency_list<
boost::listS, boost::vecS, boost::bidirectionalS,
City, Highway, Country>
Map;
</pre>
</pre>
<h2>Accessing bundled properties</h2>
<p>To access a bundled property for a particular edge or vertex,
subscript your graph with the descriptor of the edge or vertex
whose bundled property you wish to access. For instance:</p>
<pre>
Map map; // load the map
Map::vertex_descriptor v = *vertices(map).first;
map[v].name = "Troy";
map[v].population = 49170;
map[v].zipcodes.push_back(12180);
Map::edge_descriptor e = *out_edges(v, map).first;
map[e].name = "I-87";
map[e].miles = 10.;
map[e].speed_limit = 65;
map[e].lanes = 4;
map[e].divided = true;
</pre>
<p>
The graph bundle, since it does not correspond to a vertex or edge descripor
is accessed using the graph_bundle object as a key.
</p>
<pre>
map[graph_bundle].name = "United States";
map[graph_bundle].use_right = true;
map[graph_bundle].use_metric = false;
</pre>
<h2>Properties maps from bundled properties</h2>
<p>Often one needs to create a property map from an internal
property for use in a generic algorithm. For instance, using the
graph without bundled properties we might invoke <a
href="dijkstra_shortest_paths.html">Dijkstra's shortest
paths</a> algorithm like this:</p>
<pre>
vector<double> distances(num_vertices(map));
dijkstra_shortest_paths(map, from,
weight_map(get(edge_length, map))
.distance_map(make_iterator_property_map(distances.begin(),
get(vertex_index, map))));
</pre>
<p>With bundled properties, we can just pass a <em>member pointer</em>
as the property for <code>get</code>. The equivalent example using bundled
properties is:</p>
<pre>
vector<double> distances(num_vertices(map));
dijkstra_shortest_paths(map, from,
weight_map(get(<font color="#ff0000">&Highway::miles</font>, map))
.distance_map(make_iterator_property_map(distances.begin(),
get(vertex_index, map))));
</pre>
<p>The type of the returned property map is <code>property_map<Map, double Highway::*>::type</code>
or <code>property_map<Map, double Highway::*>::const_type</code>, depending on whether the graph
<code>map</code> is non-constant or constant.
<p> You may also access the entire vertex or edge bundle as a property map
using the <code>vertex_bundle</code> or <code>edge_bundle</code> properties,
respectively. For instance, the property map returned by <code>get(vertex_bundle, map)</code> is
an <a href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a> providing access to the
<code>City</code> values stored in each vertex.
<h2>Property maps for a graph bundle</h2>
There is currently no support for creating property maps from the bundled
properties of a graph.
<h2>Getting the type of bundled properties</h2>
<p>To get the type of the vertex or edge bundle for a given graph
type <tt>Graph</tt>, you can use the trait
classes <tt>vertex_bundle_type</tt>
and <tt>edge_bundle_type</tt>. The
type <tt>vertex_bundle_type<Graph>::type</tt> will be the
type bundled with vertices (or <tt>no_vertex_bundle</tt> if the
graph supports bundles but no vertex bundle
exists). Likewise, <tt>edge_bundle_type<Graph>::type</tt>
will be the type bundled with edges (or <tt>no_edge_bundle</tt> if
no edge bundle exists).</p>
<h2>Compatibility</h2> <p>Bundled properties will only work
properly on compilers that support class template partial
specialization.</p>
<hr>
Copyright © 2004 <a href="http://www.boost.org/people/doug_gregor.html">Doug Gregor</a>.
<address><a href="mailto:gregod@cs.rpi.edu"></a></address>
<!-- Created: Fri May 7 09:59:21 EDT 2004 -->
<!-- hhmts start -->
Last modified: Fri May 7 10:56:01 EDT 2004
<!-- hhmts end -->
</body>
</html>
|
