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

   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&lt;int&gt; 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&lt;
  78     boost::listS, boost::vecS, boost::bidirectionalS,
  79     City, Highway&gt;
  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&lt;
  89     boost::listS, boost::vecS, boost::bidirectionalS,
  90     // Vertex properties
  91     boost::property&lt;boost::vertex_name_t, std::string,
  92     boost::property&lt;population_t, int,
  93     boost::property&lt;zipcodes_t, std::vector&lt;int&gt; &gt; &gt; &gt;,
  94     // Edge properties
  95     boost::property&lt;boost::edge_name_t, std::string,
  96     boost::property&lt;boost::edge_weight_t, double,
  97     boost::property&lt;edge_speed_limit_t, int,
  98     boost::property&lt;edge_lanes_t, int,
  99     boost::property&lt;edge_divided, bool&gt; &gt; &gt; &gt; &gt; &gt;
 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&lt;
 128     boost::listS, boost::vecS, boost::bidirectionalS,
 129     City, Highway, Country&gt;
 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&lt;double&gt; 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&lt;double&gt; distances(num_vertices(map));
 183 dijkstra_shortest_paths(map, from,
 184       weight_map(get(<font color="#ff0000">&amp;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&lt;Map, double Highway::*&gt;::type</code>
 190 or <code>property_map&lt;Map, double Highway::*&gt;::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&lt;Graph&gt;::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&lt;Graph&gt;::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 &copy; 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>