]>
Commit | Line | Data |
---|---|---|
1 | <HTML> | |
2 | <!-- | |
3 | Copyright (c) Jeremy Siek 2000 | |
4 | ||
5 | Distributed under the Boost Software License, Version 1.0. | |
6 | (See accompanying file LICENSE_1_0.txt or copy at | |
7 | http://www.boost.org/LICENSE_1_0.txt) | |
8 | --> | |
9 | <Head> | |
10 | <Title>Boost Graph Library: Using Property Maps</Title> | |
11 | <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" | |
12 | ALINK="#ff0000"> | |
13 | <IMG SRC="../../../boost.png" | |
14 | ALT="C++ Boost" width="277" height="86"> | |
15 | ||
16 | <BR Clear> | |
17 | ||
18 | ||
19 | <H1><A NAME="sec:property-maps"></A> | |
20 | Property Maps | |
21 | </H1> | |
22 | ||
23 | <P> | |
24 | The main link between the abstract mathematical nature of graphs and | |
25 | the concrete problems they are used to solve is the properties that | |
26 | are attached to the vertices and edges of a graph, things like | |
27 | distance, capacity, weight, color, etc. There are many ways to attach | |
28 | properties to graph in terms of data-structure implementation, but | |
29 | graph algorithms should not have to deal with the implementation | |
30 | details of the properties. The <I>property map</I> interface | |
31 | defined in Section <A | |
32 | HREF="../../property_map/doc/property_map.html">Property | |
33 | Map Concepts</A> provides a generic method for accessing | |
34 | properties from graphs. This is the interface used in the BGL | |
35 | algorithms to access properties. | |
36 | ||
37 | <P> | |
38 | ||
39 | <H2>Property Map Interface</H2> | |
40 | ||
41 | <P> | |
42 | The property map interface specifies that each property is | |
43 | accessed using a separate property map object. In the following | |
44 | example we show an implementation of the <TT>relax()</TT> function used | |
45 | inside of Dijkstra's shortest paths algorithm. In this function, we | |
46 | need to access the weight property of an edge, and the distance | |
47 | property of a vertex. We write <TT>relax()</TT> as a template function | |
48 | so that it can be used in many difference situations. Two of the | |
49 | arguments to the function, <TT>weight</TT> and <TT>distance</TT>, are the | |
50 | property map objects. In general, BGL algorithms explicitly pass | |
51 | property map objects for every property that a function will | |
52 | need. The property map interface defines several functions, two | |
53 | of which we use here: <TT>get()</TT> and <TT>put()</TT>. The <TT>get()</TT> | |
54 | function takes a property map object, such as <TT>distance</TT> and | |
55 | a <I>key</I> object. In the case of the distance property we are using | |
56 | the vertex objects <TT>u</TT> and <TT>v</TT> as keys. The <TT>get()</TT> | |
57 | function then returns the property value for the vertex. | |
58 | ||
59 | <P> | |
60 | <PRE> | |
61 | template <class Edge, class Graph, | |
62 | class WeightPropertyMap, | |
63 | class DistancePropertyMap> | |
64 | bool relax(Edge e, const Graph& g, | |
65 | WeightPropertyMap weight, | |
66 | DistancePropertyMap distance) | |
67 | { | |
68 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
69 | Vertex u = source(e,g), v = target(e,g); | |
70 | if ( get(distance, u) + get(weight, e) < get(distance, v)) { | |
71 | put(distance, v, get(distance, u) + get(weight, e)); | |
72 | return true; | |
73 | } else | |
74 | return false; | |
75 | } | |
76 | </PRE> | |
77 | ||
78 | The function <TT>get()</TT> returns a copy of the property value. There | |
79 | is a third function in the property map interface, <TT>at()</TT>, | |
80 | that returns a reference to the property value (a const reference if | |
81 | the map is not mutable). | |
82 | ||
83 | <P> | |
84 | Similar to the <TT>iterator_traits</TT> class of the STL, there is a | |
85 | <TT>property_traits</TT> class that can be used to deduce the types | |
86 | associated with a property map type: the key and value types, and | |
87 | the property map category (which is used to tell whether the | |
88 | map is readable, writeable, or both). In the <TT>relax()</TT> | |
89 | function we could have used <TT>property_traits</TT> to declare local | |
90 | variables of the distance property type. | |
91 | ||
92 | <P> | |
93 | <PRE> | |
94 | { | |
95 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
96 | Vertex u = source(e,g), v = target(e,g); | |
97 | typename property_traits<DistancePropertyMap>::value_type | |
98 | du, dv; // local variables of the distance property type | |
99 | du = get(distance, u); | |
100 | dv = get(distance, v); | |
101 | if (du + get(weight, e) < dv) { | |
102 | put(distance, v, du + get(weight, e)); | |
103 | return true; | |
104 | } else | |
105 | return false; | |
106 | } | |
107 | </PRE> | |
108 | ||
109 | <P> | |
110 | There are two kinds of graph properties: interior and exterior. | |
111 | ||
112 | <P> | |
113 | <DL> | |
114 | <DT><STRONG>Interior Properties</STRONG></DT> | |
115 | <DD>are stored ``inside'' the graph object | |
116 | in some way, and the lifetime of the property value objects is the | |
117 | same as that of the graph object. | |
118 | ||
119 | <P> | |
120 | </DD> | |
121 | <DT><STRONG>Exterior Properties</STRONG></DT> | |
122 | <DD>are stored ``outside'' of the graph | |
123 | object and the lifetime of the property value objects is independent | |
124 | of the graph. This is useful for properties that are only needed | |
125 | temporarily, perhaps for the duration of a particular algorithm such | |
126 | as the color property used in <TT>breadth_first_search()</TT>. When | |
127 | using exterior properties with a BGL algorithm a property map | |
128 | object for the exterior property must be passed as an argument to the | |
129 | algorithm. | |
130 | </DD> | |
131 | </DL> | |
132 | ||
133 | <P> | |
134 | ||
135 | <H2><A NAME="sec:interior-properties"></A> | |
136 | Interior Properties | |
137 | </H2> | |
138 | ||
139 | <P> | |
140 | A graph type that supports interior property storage (such as | |
141 | <TT>adjacency_list</TT>) provides access to its property map | |
142 | objects through the interface defined in <a | |
143 | href="./PropertyGraph.html">PropertyGraph</a>. There is a function | |
144 | <TT>get(Property, g)</TT> that get property map objects from a | |
145 | graph. The first argument is the property type to specify which | |
146 | property you want to access and the second argument is the graph | |
147 | object. A graph type must document which properties (and therefore | |
148 | tags) it provides access to. The type of the property map depends on | |
149 | the type of graph and the property being mapped. A trait class is | |
150 | defined that provides a generic way to deduce the property map type: | |
151 | <TT>property_map</TT>. The following code shows how one can obtain the | |
152 | property map for the distance and weight properties of some graph | |
153 | type. | |
154 | ||
155 | <P> | |
156 | <PRE> | |
157 | property_map<Graph, vertex_distance_t>::type d | |
158 | = get(vertex_distance, g); | |
159 | ||
160 | property_map<Graph, edge_weight_t>::type w | |
161 | = get(edge_weight, g); | |
162 | </PRE> | |
163 | ||
164 | <P> | |
165 | In general, the BGL algorithms require all property maps needed | |
166 | by the algorithm to be explicitly passed to the algorithm. For | |
167 | example, the BGL Dijkstra's shortest paths algorithm requires four | |
168 | property maps: distance, weight, color, and vertex ID. | |
169 | ||
170 | <P> | |
171 | Often times some or all of the properties will be interior to the | |
172 | graph, so one would call Dijkstra's algorithm in the following way | |
173 | (given some graph <TT>g</TT> and source vertex <TT>src</TT>). | |
174 | ||
175 | <P> | |
176 | <PRE> | |
177 | dijkstra_shortest_paths(g, src, | |
178 | distance_map(get(vertex_distance, g)). | |
179 | weight_map(get(edge_weight, g)). | |
180 | color_map(get(vertex_color, g)). | |
181 | vertex_index_map(get(vertex_index, g))); | |
182 | </PRE> | |
183 | ||
184 | <P> | |
185 | Since it is somewhat cumbersome to specify all of the property maps, | |
186 | BGL provides defaults that assume some of the properties are interior | |
187 | and can be accessed via <TT>get(Property, g)</TT> from the graph, or | |
188 | if the property map is only used internally, then the algorithm will | |
189 | create a property map for itself out of an array and using the graph's | |
190 | vertex index map as the offset into the array. Below we show a call to | |
191 | <TT>dijkstra_shortest_paths</TT> algorithm using all defaults for the | |
192 | named parameters. This call is equivalent to the previous call to | |
193 | Dijkstra's algorithm. | |
194 | ||
195 | <P> | |
196 | <PRE> | |
197 | dijkstra_shortest_paths(g, src); | |
198 | </PRE> | |
199 | ||
200 | <P> | |
201 | The next question is: how do interior properties become attached to a | |
202 | graph object in the first place? This depends on the graph class that | |
203 | you are using. The <TT>adjacency_list</TT> graph class of BGL uses a | |
204 | property mechanism (see Section <A | |
205 | HREF="using_adjacency_list.html#sec:adjacency-list-properties">Internal | |
206 | Properties</A>) to allow an arbitrary number of properties to be | |
207 | stored on the edges and vertices of the graph. | |
208 | ||
209 | <P> | |
210 | ||
211 | <H2><A NAME="sec:exterior-properties"></A> | |
212 | Exterior Properties | |
213 | </H2> | |
214 | ||
215 | <P> | |
216 | In this section we will describe two methods for constructing exterior | |
217 | property maps, however there is an unlimited number of ways that | |
218 | one could create exterior properties for a graph. | |
219 | ||
220 | <P> | |
221 | The first method uses the adaptor class | |
222 | <TT>iterator_property_map</TT>. This | |
223 | class wraps a random access iterator, creating a property map out | |
224 | of it. The random access iterator must point to the beginning of a | |
225 | range of property values, and the length of the range must be the | |
226 | number of vertices or edges in the graph (depending on whether it is a | |
227 | vertex or edge property map). The adaptor must also be supplied | |
228 | with an ID property map, which will be used to map the vertex or | |
229 | edge descriptor to the offset of the property value (offset from the | |
230 | random access iterator). The ID property map will typically be an | |
231 | interior property map of the graph. The following example shows | |
232 | how the <TT>iterator_property_map</TT> | |
233 | can be used to create exterior property maps for the capacity and flow properties, which are stored in arrays. The arrays are | |
234 | indexed by edge ID. The edge ID is added to the graph using a property, | |
235 | and the values of the ID's are given when each edge is added to the | |
236 | graph. The complete source code for this example is in | |
237 | <TT>example/exterior_edge_properties.cpp</TT>. The | |
238 | <TT>print_network()</TT> function prints out the graph with | |
239 | the flow and capacity values. | |
240 | ||
241 | <P> | |
242 | <PRE> | |
243 | typedef adjacency_list<vecS, vecS, bidirectionalS, | |
244 | no_property, property<edge_index_t, std::size_t> > Graph; | |
245 | ||
246 | const int num_vertices = 9; | |
247 | Graph G(num_vertices); | |
248 | ||
249 | int capacity_array[] = { 10, 20, 20, 20, 40, 40, 20, 20, 20, 10 }; | |
250 | int flow_array[] = { 8, 12, 12, 12, 12, 12, 16, 16, 16, 8 }; | |
251 | ||
252 | // Add edges to the graph, and assign each edge an ID number. | |
253 | add_edge(0, 1, 0, G); | |
254 | // ... | |
255 | ||
256 | typedef graph_traits<Graph>::edge_descriptor Edge; | |
257 | typedef property_map<Graph, edge_index_t>::type EdgeID_Map; | |
258 | EdgeID_Map edge_id = get(edge_index, G); | |
259 | ||
260 | iterator_property_map | |
261 | <int*, int, int&, EdgeID_Map> | |
262 | capacity(capacity_array, edge_id), | |
263 | flow(flow_array, edge_id); | |
264 | ||
265 | print_network(G, capacity, flow); | |
266 | </PRE> | |
267 | ||
268 | <P> | |
269 | The second method uses a pointer type (a pointer to an array of | |
270 | property values) as a property map. This requires the key type to | |
271 | be an integer so that it can be used as an offset to the pointer. The | |
272 | <TT>adjacency_list</TT> class with template parameter | |
273 | <TT>VertexList=vecS</TT> uses integers for vertex descriptors (indexed | |
274 | from zero to the number of vertices in the graph), so they are | |
275 | suitable as the key type for a pointer property map. When the | |
276 | <TT>VertexList</TT> is not <TT>vecS</TT>, then the vertex descriptor is | |
277 | not an integer, and cannot be used with a pointer property map. | |
278 | Instead the method described above of using a | |
279 | <TT>iterator_property_map</TT> with an ID | |
280 | property must be used. The <TT>edge_list</TT> class may also use an | |
281 | integer type for the vertex descriptor, depending on how the adapted | |
282 | edge iterator is defined. The example in | |
283 | <TT>example/bellman_ford.cpp</TT> shows <TT>edge_list</TT> being used | |
284 | with pointers as vertex property maps. | |
285 | ||
286 | <P> | |
287 | The reason that pointers can be used as property maps is that | |
288 | there are several overloaded functions and a specialization of | |
289 | <TT>property_traits</TT> in the header <a | |
290 | href="../../../boost/property_map/property_map.hpp"><TT>boost/property_map/property_map.hpp</TT></a> | |
291 | that implement the property map interface in terms of | |
292 | pointers. The definition of those functions is listed here. | |
293 | ||
294 | <P> | |
295 | <PRE> | |
296 | namespace boost { | |
297 | template <class T> | |
298 | struct property_traits<T*> { | |
299 | typedef T value_type; | |
300 | typedef ptrdiff_t key_type; | |
301 | typedef lvalue_property_map_tag category; | |
302 | }; | |
303 | ||
304 | template <class T> | |
305 | void put(T* pa, std::ptrdiff_t key, const T& value) { pa[key] = value; } | |
306 | ||
307 | template <class T> | |
308 | const T& get(const T* pa, std::ptrdiff_t key) { return pa[key]; } | |
309 | ||
310 | template <class T> | |
311 | const T& at(const T* pa, std::ptrdiff_t key) { return pa[key]; } | |
312 | ||
313 | template <class T> | |
314 | T& at(T* pa, std::ptrdiff_t key) { return pa[key]; } | |
315 | } | |
316 | </PRE> | |
317 | ||
318 | <P> | |
319 | In the following example, we use an array to store names of cities for | |
320 | each vertex in the graph, and a <TT>std::vector</TT> to store vertex | |
321 | colors which will be needed in a call to | |
322 | <TT>breadth_first_search()</TT>. Since the iterator of a | |
323 | <TT>std::vector</TT> (obtained with a call to <TT>begin()</TT>) is a | |
324 | pointer, the pointer property map method also works for | |
325 | <TT>std::vector::iterator</TT>. The complete source code for this | |
326 | example is in <a | |
327 | href="../example/city_visitor.cpp"><TT>example/city_visitor.cpp</TT></a>. | |
328 | ||
329 | <P> | |
330 | <PRE> | |
331 | // Definition of city_visitor omitted... | |
332 | ||
333 | int main(int,char*[]) | |
334 | { | |
335 | enum { SanJose, SanFran, LA, SanDiego, Fresno, LosVegas, Reno, | |
336 | Sacramento, SaltLake, Pheonix, N }; | |
337 | ||
338 | // An array of vertex name properties | |
339 | std::string names[] = { "San Jose", "San Francisco", "San Jose", | |
340 | "San Francisco", "Los Angeles", "San Diego", | |
341 | "Fresno", "Los Vegas", "Reno", "Sacramento", | |
342 | "Salt Lake City", "Pheonix" }; | |
343 | ||
344 | // Specify all the connecting roads between cities. | |
345 | typedef std::pair<int,int> E; | |
346 | E edge_array[] = { E(Sacramento, Reno), ... }; | |
347 | ||
348 | // Specify the graph type. | |
349 | typedef adjacency_list<vecS, vecS, undirectedS> Graph; | |
350 | // Create the graph object, based on the edges in edge_array. | |
351 | Graph G(N, edge_array, edge_array + sizeof(edge_array)/sizeof(E)); | |
352 | ||
353 | // DFS and BFS need to "color" the vertices. | |
354 | // Here we use std::vector as exterior property storage. | |
355 | std::vector<default_color_type> colors(N); | |
356 | ||
357 | cout << "*** Depth First ***" << endl; | |
358 | depth_first_search(G, city_visitor(names), colors.begin()); | |
359 | cout << endl; | |
360 | ||
361 | // Get the source vertex | |
362 | boost::graph_traits<Graph>::vertex_descriptor | |
363 | s = vertex(SanJose, G); | |
364 | ||
365 | cout << "*** Breadth First ***" << endl; | |
366 | breadth_first_search(G, s, city_visitor(names), colors.begin()); | |
367 | ||
368 | return 0; | |
369 | } | |
370 | </PRE> | |
371 | ||
372 | <P> | |
373 | ||
374 | <H2><A NAME="sec:custom-exterior-property-maps"></A> | |
375 | Constructing an Exterior Property Map | |
376 | </H2> | |
377 | ||
378 | <P> | |
379 | Implementing your own exterior property maps is not very | |
380 | difficult. You simply need to overload the functions required by the | |
381 | <a href="property_map.html">property map concept</a> | |
382 | that you want your class to model. At most, this means overloading the | |
383 | <TT>put()</TT> and <TT>get()</TT> functions and implementing | |
384 | <TT>operator[]</TT>. Also, your property map class will need to have | |
385 | nested typedefs for all the types defined in <TT>property_traits</TT>, | |
386 | or you can create a specialization of <TT>property_traits</TT> for | |
387 | your new property map type. | |
388 | ||
389 | <P> | |
390 | The implementation of the | |
391 | <TT>iterator_property_map</TT> class | |
392 | serves as a good example for how to build and exterior property | |
393 | map. Here we present a simplified implementation of the | |
394 | <TT>iterator_property_map</TT> class | |
395 | which we will name <TT>iterator_pa</TT>. | |
396 | ||
397 | <P> | |
398 | We start with the definition of the <TT>iterator_map</TT> class | |
399 | itself. This adaptor class is templated on the adapted <TT>Iterator</TT> | |
400 | type and the ID property map. The job of the ID property map | |
401 | is to map the key object (which will typically be a vertex or edge | |
402 | descriptor) to an integer offset. The <TT>iterator_map</TT> class will | |
403 | need the three necessary typedefs for a property map: | |
404 | <TT>key_type</TT>, <TT>value_type</TT>, and <TT>category</TT>. We can use | |
405 | <TT>property_traits</TT> to find the key type of <TT>IDMap</TT>, and | |
406 | we can use <TT>iterator_traits</TT> to determine the value type of | |
407 | <TT>Iterator</TT>. We choose | |
408 | <TT>boost::lvalue_property_map_tag</TT> for the category | |
409 | since we plan on implementing the <TT>at()</TT> function. | |
410 | ||
411 | <P> | |
412 | <PRE> | |
413 | template <class Iterator, class IDMap> | |
414 | class iterator_map | |
415 | { | |
416 | public: | |
417 | typedef typename boost::property_traits<IDMap>::key_type key_type; | |
418 | typedef typename std::iterator_traits<Iterator>::value_type value_type; | |
419 | typedef boost::lvalue_property_map_tag category; | |
420 | ||
421 | iterator_map(Iterator i = Iterator(), | |
422 | const IDMap& id = IDMap()) | |
423 | : m_iter(i), m_id(id) { } | |
424 | Iterator m_iter; | |
425 | IDMap m_id; | |
426 | }; | |
427 | </PRE> | |
428 | ||
429 | <P> | |
430 | Next we implement the three property map functions, <TT>get()</TT>, | |
431 | <TT>put()</TT>, and <TT>at()</TT>. In each of the functions, the | |
432 | <TT>key</TT> object is converted to an integer offset using the | |
433 | <TT>m_id</TT> property map, and then that is used as an offset | |
434 | to the random access iterator <TT>m_iter</TT>. | |
435 | ||
436 | <P> | |
437 | <PRE> | |
438 | template <class Iter, class ID> | |
439 | typename std::iterator_traits<Iter>::value_type | |
440 | get(const iterator_map<Iter,ID>& i, | |
441 | typename boost::property_traits<ID>::key_type key) | |
442 | { | |
443 | return i.m_iter[i.m_id[key]]; | |
444 | } | |
445 | template <class Iter, class ID> | |
446 | void | |
447 | put(const iterator_map<Iter,ID>& i, | |
448 | typename boost::property_traits<ID>::key_type key, | |
449 | const typename std::iterator_traits<Iter>::value_type& value) | |
450 | { | |
451 | i.m_iter[i.m_id[key]] = value; | |
452 | } | |
453 | template <class Iter, class ID> | |
454 | typename std::iterator_traits<Iter>::reference | |
455 | at(const iterator_map<Iter,ID>& i, | |
456 | typename boost::property_traits<ID>::key_type key) | |
457 | { | |
458 | return i.m_iter[i.m_id[key]]; | |
459 | } | |
460 | </PRE> | |
461 | ||
462 | <P> | |
463 | That is it. The <TT>iterator_map</TT> class is complete and could be | |
464 | used just like the | |
465 | <TT>iterator_property_map</TT> in the | |
466 | previous section. | |
467 | ||
468 | <P> | |
469 | ||
470 | ||
471 | <br> | |
472 | <HR> | |
473 | <TABLE> | |
474 | <TR valign=top> | |
475 | <TD nowrap>Copyright © 2000-2001</TD><TD> | |
476 | <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>) | |
477 | </TD></TR></TABLE> | |
478 | ||
479 | </BODY> | |
480 | </HTML> |