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