ceph/src/boost/libs/graph/doc/using_property_maps.html

   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 &lt;class Edge, class Graph,
  62             class WeightPropertyMap,
  63             class DistancePropertyMap&gt;
  64   bool relax(Edge e, const Graph&amp; g,
  65              WeightPropertyMap weight,
  66              DistancePropertyMap distance)
  67   {
  68     typedef typename graph_traits&lt;Graph&gt;::vertex_descriptor Vertex;
  69     Vertex u = source(e,g), v = target(e,g);
  70     if ( get(distance, u) + get(weight, e) &lt; 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&lt;Graph&gt;::vertex_descriptor Vertex;
  96     Vertex u = source(e,g), v = target(e,g);
  97     typename property_traits&lt;DistancePropertyMap&gt;::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) &lt; 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&lt;Graph, vertex_distance_t&gt;::type d
 158     = get(vertex_distance, g);
 159
 160   property_map&lt;Graph, edge_weight_t&gt;::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&lt;vecS, vecS, bidirectionalS,
 244     no_property, property&lt;edge_index_t, std::size_t&gt; &gt; 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&lt;Graph&gt;::edge_descriptor Edge;
 257   typedef property_map&lt;Graph, edge_index_t&gt;::type EdgeID_Map;
 258   EdgeID_Map edge_id = get(edge_index, G);
 259
 260   iterator_property_map
 261     &lt;int*, int, int&amp;, EdgeID_Map&gt;
 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 &lt;class T&gt;
 298   struct property_traits&lt;T*&gt; {
 299     typedef T value_type;
 300     typedef ptrdiff_t key_type;
 301     typedef lvalue_property_map_tag category;
 302   };
 303
 304   template &lt;class T&gt;
 305   void put(T* pa, std::ptrdiff_t key, const T&amp; value) { pa[key] = value;  }
 306
 307   template &lt;class T&gt;
 308   const T&amp; get(const T* pa, std::ptrdiff_t key) { return pa[key]; }
 309
 310   template &lt;class T&gt;
 311   const T&amp; at(const T* pa, std::ptrdiff_t key) { return pa[key]; }
 312
 313   template &lt;class T&gt;
 314   T&amp; 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[] = { &quot;San Jose&quot;, &quot;San Francisco&quot;,  &quot;San Jose&quot;,
 340                           &quot;San Francisco&quot;, &quot;Los Angeles&quot;, &quot;San Diego&quot;,
 341                           &quot;Fresno&quot;, &quot;Los Vegas&quot;, &quot;Reno&quot;, &quot;Sacramento&quot;,
 342                           &quot;Salt Lake City&quot;, &quot;Pheonix&quot; };
 343
 344   // Specify all the connecting roads between cities.
 345   typedef std::pair&lt;int,int&gt; E;
 346   E edge_array[] = { E(Sacramento, Reno), ... };
 347
 348   // Specify the graph type.
 349   typedef adjacency_list&lt;vecS, vecS, undirectedS&gt; 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 &quot;color&quot; the vertices.
 354   // Here we use std::vector as exterior property storage.
 355   std::vector&lt;default_color_type&gt; colors(N);
 356
 357   cout &lt;&lt; &quot;*** Depth First ***&quot; &lt;&lt; endl;
 358   depth_first_search(G, city_visitor(names), colors.begin());
 359   cout &lt;&lt; endl;
 360
 361   // Get the source vertex
 362   boost::graph_traits&lt;Graph&gt;::vertex_descriptor
 363     s = vertex(SanJose, G);
 364
 365   cout &lt;&lt; &quot;*** Breadth First ***&quot; &lt;&lt; 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 &lt;class Iterator, class IDMap&gt;
 414   class iterator_map
 415   {
 416   public:
 417     typedef typename boost::property_traits&lt;IDMap&gt;::key_type key_type;
 418     typedef typename std::iterator_traits&lt;Iterator&gt;::value_type value_type;
 419     typedef boost::lvalue_property_map_tag category;
 420
 421     iterator_map(Iterator i = Iterator(),
 422                 const IDMap&amp; 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 &lt;class Iter, class ID&gt;
 439   typename std::iterator_traits&lt;Iter&gt;::value_type
 440   get(const iterator_map&lt;Iter,ID&gt;&amp; i,
 441       typename boost::property_traits&lt;ID&gt;::key_type key)
 442   {
 443     return i.m_iter[i.m_id[key]];
 444   }
 445   template &lt;class Iter, class ID&gt;
 446   void
 447   put(const iterator_map&lt;Iter,ID&gt;&amp; i,
 448       typename boost::property_traits&lt;ID&gt;::key_type key,
 449       const typename std::iterator_traits&lt;Iter&gt;::value_type&amp; value)
 450   {
 451     i.m_iter[i.m_id[key]] = value;
 452   }
 453   template &lt;class Iter, class ID&gt;
 454   typename std::iterator_traits&lt;Iter&gt;::reference
 455   at(const iterator_map&lt;Iter,ID&gt;&amp; i,
 456       typename boost::property_traits&lt;ID&gt;::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 &copy; 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>