| <!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>With bundled properties, we can directly use the <code>City</code> and |
| <code>Highway</code> structures to define the graph:</p> |
| <pre> |
| typedef boost::adjacency_list< |
| boost::listS, boost::vecS, boost::bidirectionalS, |
| City, Highway> |
| Map; |
| </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> |
| Bundling vertex and edge properties greatly simplifies the declaration of |
| graphs. |
| </p> |
| <p> |
| In addition to vertex and edge bundles, we can also bundle properties of the |
| graph itself. Suppopse we extend the application to include a portfolio of |
| route-planning maps for different countries. In addition to the <code>City</code> |
| and <code>Highway</code> bundles above, we can declare a graph bundle, |
| <code>Country</Code>. |
| </p> |
| |
| <pre> |
| struct Country { |
| string name; |
| bool use_right; // Drive on the left or right |
| bool use_metric; // mph or km/h |
| }; |
| </pre> |
| |
| <p>The graph would now be declared as:</p> |
| |
| <pre> |
| <pre> |
| typedef boost::adjacency_list< |
| boost::listS, boost::vecS, boost::bidirectionalS, |
| City, Highway, Country> |
| Map; |
| </pre> |
| </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> |
| |
| <p> |
| The graph bundle, since it does not correspond to a vertex or edge descripor |
| is accessed using the graph_bundle object as a key. |
| </p> |
| |
| <pre> |
| map[graph_bundle].name = "United States"; |
| map[graph_bundle].use_right = true; |
| map[graph_bundle].use_metric = false; |
| </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>Property maps for a graph bundle</h2> |
| There is currently no support for creating property maps from the bundled |
| properties of a graph. |
| |
| <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> |