<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html> <!-- Copyright Doug Gregor 2004. Use, modification and distribution is subject to the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) For more information, see http://www.boost.org --> <head> <title>Bundled Properties</title> </head> <body BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" ALINK="#ff0000"> <IMG SRC="../../../boost.png" ALT="C++ Boost" width="277" height="86"/> <h1>Bundled Properties</h1> <p>Class templates <code><a href="adjacency_list.html">adjacency_list</a></code> and <code><a href="adjacency_matrix.html">adjacency_matrix</a></code> support the introduction of named properties via <a href="using_adjacency_list.html#sec:adjacency-list-properties">internal properties</a>. However, this method is cumbersome in many uses, where it would be more intuitive to just specify a structure or class that contains internal properties for edges or vertices. Bundled properties allow one to use <code>adjacency_list</code> and <code>adjacency_matrix</code> in this manner, providing a simple way to introduce and access any number of internal properties for vertices and edges.</p> <p>One can introduce bundled properties into an either graph type by providing a user-defined class type for the <code>VertexProperties</code> or <code>EdgeProperties</code> template arguments. The user-defined class may alternatively be placed at the end of a <code>property</code> list, replacing the (implicit) <code>boost::no_property</code> argument.</p> <h2>Example: Route planning</h2> <p>Consider the implementation of a simple route planner that should find the shortest directions from one city to another via a set of highways. The vertices of the graph are cities, and we may wish to store several bits of information about the city within each vertex:</p> <pre> struct City { string name; int population; vector<int> zipcodes; }; </pre> <p>The edges in the graph represent highways, which also have several interesting attributes:</p> <pre> struct Highway { string name; double miles; int speed_limit; int lanes; bool divided; }; </pre> <p>Without bundled properties, translating this example directly into an instantiation of <code>adjacency_list</code> would involve several custom properties and would result in a type like this:</p> <pre> typedef boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS, // Vertex properties boost::property<boost::vertex_name_t, std::string, boost::property<population_t, int, boost::property<zipcodes_t, std::vector<int> > > >, // Edge properties boost::property<boost::edge_name_t, std::string, boost::property<boost::edge_length_t, double, boost::property<edge_speed_limit_t, int, boost::property<edge_lanes_t, int, boost::property<edge_divided, bool> > > > > > Map; </pre> <p>With bundled properties, we can directly use the <code>City</code> and <code>Highway</code> structures:</p> <pre> typedef boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS, City, Highway> Map; </pre> <h2>Accessing bundled properties</h2> <p>To access a bundled property for a particular edge or vertex, subscript your graph with the descriptor of the edge or vertex whose bundled property you wish to access. For instance:</p> <pre> Map map; // load the map Map::vertex_descriptor v = *vertices(map).first; map[v].name = "Troy"; map[v].population = 49170; map[v].zipcodes.push_back(12180); Map::edge_descriptor e = *out_edges(v, map).first; map[e].name = "I-87"; map[e].miles = 10; map[e].speed_limit = 65; map[e].lanes = 4; map[e].divided = true; </pre> <h2>Properties maps from bundled properties</h2> <p>Often one needs to create a property map from an internal property for use in a generic algorithm. For instance, using the graph without bundled properties we might invoke <a href="dijkstra_shortest_paths.html">Dijkstra's shortest paths</a> algorithm like this:</p> <pre> vector<double> distances(num_vertices(map)); dijkstra_shortest_paths(map, from, weight_map(get(edge_length, map)) .distance_map(make_iterator_property_map(distances.begin(), get(vertex_index, map)))); </pre> <p>With bundled properties, we can just pass a <em>member pointer</em> as the property for <code>get</code>. The equivalent example using bundled properties is:</p> <pre> vector<double> distances(num_vertices(map)); dijkstra_shortest_paths(map, from, weight_map(get(<font color="#ff0000">&Highway::miles</font>, map)) .distance_map(make_iterator_property_map(distances.begin(), get(vertex_index, map)))); </pre> <p>The type of the returned property map is <code>property_map<Map, int Highway::*>::type</code> or <code>property_map<Map, int Highway::*>::const_type</code>, depending on whether the graph <code>map</code> is non-constant or constant. <p> You may also access the entire vertex or edge bundle as a property map using the <code>vertex_bundle</code> or <code>edge_bundle</code> properties, respectively. For instance, the property map returned by <code>get(vertex_bundle, map)</code> is an <a href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a> providing access to the <code>City</code> values stored in each vertex. <h2>Getting the type of bundled properties</h2> <p>To get the type of the vertex or edge bundle for a given graph type <tt>Graph</tt>, you can use the trait classes <tt>vertex_bundle_type</tt> and <tt>edge_bundle_type</tt>. The type <tt>vertex_bundle_type<Graph>::type</tt> will be the type bundled with vertices (or <tt>no_vertex_bundle</tt> if the graph supports bundles but no vertex bundle exists). Likewise, <tt>edge_bundle_type<Graph>::type</tt> will be the type bundled with edges (or <tt>no_edge_bundle</tt> if no edge bundle exists).</p> <h2>Compatibility</h2> <p>Bundled properties will only work properly on compilers that support class template partial specialization.</p> <hr> Copyright © 2004 <a href="http://www.boost.org/people/doug_gregor.html">Doug Gregor</a>. <address><a href="mailto:gregod@cs.rpi.edu"></a></address> <!-- Created: Fri May 7 09:59:21 EDT 2004 --> <!-- hhmts start --> Last modified: Fri May 7 10:56:01 EDT 2004 <!-- hhmts end --> </body> </html>