[ceph.git] / ceph / src / boost / libs / graph / doc / bundles.html

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