|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r65386 - trunk/libs/graph/doc
From: asutton_at_[hidden]
Date: 2010-09-11 10:33:42
Author: asutton
Date: 2010-09-11 10:33:38 EDT (Sat, 11 Sep 2010)
New Revision: 65386
URL: http://svn.boost.org/trac/boost/changeset/65386
Log:
Adding documentation for bundled graph properties.
Text files modified:
trunk/libs/graph/doc/bundles.html | 260 +++++++++++++++++++++++----------------
1 files changed, 155 insertions(+), 105 deletions(-)
Modified: trunk/libs/graph/doc/bundles.html
==============================================================================
--- trunk/libs/graph/doc/bundles.html (original)
+++ trunk/libs/graph/doc/bundles.html 2010-09-11 10:33:38 EDT (Sat, 11 Sep 2010)
@@ -8,57 +8,59 @@
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>adjacency_matrix</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>
+<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>adjacency_matrix</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>
- <pre>
+<p>
+The edges in the graph represent highways, which also have several interesting
+attributes:
+</p>
+
+<pre>
struct Highway
{
string name;
@@ -67,17 +69,26 @@
int lanes;
bool divided;
};
- </pre>
+</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>
+<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<boost::vertex_name_t, std::string,
boost::property<population_t, int,
boost::property<zipcodes_t, std::vector<int> > > >,
// Edge properties
@@ -87,21 +98,44 @@
boost::property<edge_lanes_t, int,
boost::property<edge_divided, bool> > > > > >
Map;
- </pre>
+</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>
- <p>With bundled properties, we can directly use the
- <code>City</code> and <code>Highway</code> structures:</p>
- <pre>
+<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> Map;
- </pre>
+ 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>
+<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";
@@ -113,66 +147,82 @@
map[e].speed_limit = 65;
map[e].lanes = 4;
map[e].divided = true;
- </pre>
+</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>
+<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>
+</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>
+<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>
+</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 Lvalue Property Map 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>
+<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 Lvalue Property Map 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>
+<hr>
Copyright © 2004 Doug Gregor.
- <address><a href="mailto:gregod_at_[hidden]"></a></address>
+<address><a href="mailto:gregod_at_[hidden]"></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>
+</body>
</html>
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk