Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/bundles.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 6.9 KB
RevLine 
[29]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>
50struct City
51{
52  string name;
53  int population;
54  vector&lt;int&gt; zipcodes;
55};
56      </pre>
57     
58      <p>The edges in the graph represent highways, which also have
59        several interesting attributes:</p>
60
61      <pre>
62struct Highway
63{
64  string name;
65  double miles;
66  int speed_limit;
67  int lanes;
68  bool divided;
69};
70      </pre>
71
72      <p>Without bundled properties, translating this example directly
73      into an instantiation of <code>adjacency_list</code> would
74      involve several custom properties and would result in a type
75      like this:</p>
76      <pre>
77typedef boost::adjacency_list&lt;
78    boost::listS, boost::vecS, boost::bidirectionalS,
79    // Vertex properties
80    boost::property&lt;boost::vertex_name_t, std::string,
81    boost::property&lt;population_t, int,
82    boost::property&lt;zipcodes_t, std::vector&lt;int&gt; &gt; &gt; &gt;,
83    // Edge properties
84    boost::property&lt;boost::edge_name_t, std::string,
85    boost::property&lt;boost::edge_length_t, double,
86    boost::property&lt;edge_speed_limit_t, int,
87    boost::property&lt;edge_lanes_t, int,
88    boost::property&lt;edge_divided, bool&gt; &gt; &gt; &gt; &gt; &gt;
89  Map;
90      </pre>
91
92      <p>With bundled properties, we can directly use the
93        <code>City</code> and <code>Highway</code> structures:</p>
94      <pre>
95typedef boost::adjacency_list&lt;
96    boost::listS, boost::vecS, boost::bidirectionalS,
97    City, Highway&gt; Map;
98      </pre>
99
100    <h2>Accessing bundled properties</h2>
101    <p>To access a bundled property for a particular edge or vertex,
102        subscript your graph with the descriptor of the edge or vertex
103        whose bundled property you wish to access. For instance:</p>
104    <pre>
105Map map; // load the map
106Map::vertex_descriptor v = *vertices(map).first;
107map[v].name = "Troy";
108map[v].population = 49170;
109map[v].zipcodes.push_back(12180);
110Map::edge_descriptor e = *out_edges(v, map).first;
111map[e].name = "I-87";
112map[e].miles = 10;
113map[e].speed_limit = 65;
114map[e].lanes = 4;
115map[e].divided = true;
116    </pre>
117
118    <h2>Properties maps from bundled properties</h2>
119    <p>Often one needs to create a property map from an internal
120      property for use in a generic algorithm. For instance, using the
121      graph without bundled properties we might invoke <a
122        href="dijkstra_shortest_paths.html">Dijkstra's shortest
123        paths</a> algorithm like this:</p>
124    <pre>
125vector&lt;double&gt; distances(num_vertices(map));
126dijkstra_shortest_paths(map, from,
127      weight_map(get(edge_length, map))
128      .distance_map(make_iterator_property_map(distances.begin(),
129                                               get(vertex_index, map))));
130    </pre>
131
132    <p>With bundled properties, we can just pass a <em>member pointer</em>
133          as the property for <code>get</code>. The equivalent example
134      using bundled properties is:</p>
135    <pre>
136vector&lt;double&gt; distances(num_vertices(map));
137dijkstra_shortest_paths(map, from,
138      weight_map(get(<font color="#ff0000">&amp;Highway::miles</font>, map))
139      .distance_map(make_iterator_property_map(distances.begin(),
140                                               get(vertex_index, map))));
141    </pre>
142
143    <p>The type of the returned property map is <code>property_map&lt;Map, int Highway::*&gt;::type</code> 
144        or <code>property_map&lt;Map, int Highway::*&gt;::const_type</code>, depending on whether the graph
145        <code>map</code> is non-constant or constant.
146       
147    <p> You may also access the entire vertex or edge bundle as a property map
148        using the <code>vertex_bundle</code> or <code>edge_bundle</code> properties,
149        respectively. For instance, the property map returned by <code>get(vertex_bundle, map)</code> is
150        an <a href="../../property_map/LvaluePropertyMap.html">Lvalue Property Map</a> providing access to the
151        <code>City</code> values stored in each vertex.
152
153    <h2>Getting the type of bundled properties</h2>
154
155    <p>To get the type of the vertex or edge bundle for a given graph
156    type <tt>Graph</tt>, you can use the trait
157    classes <tt>vertex_bundle_type</tt>
158    and <tt>edge_bundle_type</tt>. The
159    type <tt>vertex_bundle_type&lt;Graph&gt;::type</tt> will be the
160    type bundled with vertices (or <tt>no_vertex_bundle</tt> if the
161    graph supports bundles but no vertex bundle
162    exists). Likewise, <tt>edge_bundle_type&lt;Graph&gt;::type</tt>
163    will be the type bundled with edges (or <tt>no_edge_bundle</tt> if
164    no edge bundle exists).</p>
165
166    <h2>Compatibility</h2> <p>Bundled properties will only work
167    properly on compilers that support class template partial
168    specialization.</p>
169
170    <hr>
171Copyright &copy; 2004 <a href="../../../people/doug_gregor.html">Doug Gregor</a>.
172    <address><a href="mailto:gregod@cs.rpi.edu"></a></address>
173<!-- Created: Fri May  7 09:59:21 EDT 2004 -->
174<!-- hhmts start -->
175Last modified: Fri May  7 10:56:01 EDT 2004
176<!-- hhmts end -->
177  </body>
178</html>
Note: See TracBrowser for help on using the repository browser.