Planet

navi

home

PPS

about

screenshots

download

development

forum

Context Navigation

source: downloads/boost_1_34_1/libs/graph/doc/compressed_sparse_row.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: 29.4 KB

Line
1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
2	<html>
3	<!--
4	-- Copyright (c) 2005 Trustees of Indiana University
5	--
6	-- Distributed under the Boost Software License, Version 1.0.
7	-- (See accompanying file LICENSE_1_0.txt or copy at
8	-- http://www.boost.org/LICENSE_1_0.txt)
9	-->
10	<head>
11	<title>Compressed Sparse Row Graph</title>
12
13	<STYLE TYPE="text/css">
14	<!--
15	.indent
16	{
17	padding-left: 50pt;
18	padding-right: 50pt;
19	}
20	-->
21	</STYLE>
22
23	<script language="JavaScript" type="text/JavaScript">
24	<!--
25	function address(host, user) {
26	var atchar = '@';
27	var thingy = user+atchar+host;
28	thingy = '<a hre' + 'f=' + "mai" + "lto:" + thingy + '>' + user+atchar+host + '</a>';
29	document.write(thingy);
30	}
31	//-->
32	</script>
33
34	</head>
35
36	<body>
37	<IMG SRC="../../../boost.png"
38	ALT="C++ Boost" width="277" height="86"></img>
39	<h1>Compressed Sparse Row Graph</h1>
40
41	<p>The class template <code>compressed_sparse_row_graph</code> is
42	a graph class that uses the compact Compressed Sparse Row (CSR)
43	format to store directed graphs. While CSR graphs have much less
44	overhead than many other graph formats (e.g., <a
45	href="adjacency_list.html"><code>adjacency_list</code></a>), they
46	do not provide any mutability: one cannot add or remove vertices
47	or edges from a CSR graph. Use this format in high-performance
48	applications or for very large graphs that you do not need to
49	change.</p>
50
51	<p>The CSR format stores vertices and edges in separate arrays,
52	with the indices into these arrays corresponding to the identifier
53	for the vertex or edge, respectively. The edge array is sorted by
54	the source of each edge, but contains only the targets for the
55	edges. The vertex array stores offsets into the edge array,
56	providing the offset of the first edge outgoing from each
57	vertex. Iteration over the out-edges for the <i>i</i><sup>th</sup>
58	vertex in the graph is achieved by
59	visiting <tt>edge_array[vertex_array[i]]</tt>, <tt>edge_array[vertex_array[i]+1]</tt>,
60	..., <tt>edge_array[vertex_array[i+1]]</tt>. This format minimizes
61	memory use to <i>O(n + m)</i>, where <i>n</i> and <i>m</i> are the
62	number of vertices and edges, respectively. The constants
63	multiplied by <i>n</i> and <i>m</i> are based on the size of the
64	integers needed to represent indices into the edge and vertex
65	arrays, respectively, which can be controlled using
66	the <a href="#template-parms">template parameters</a>.</p>
67
68	<ul>
69	<li><a href="#synopsis">Synopsis</a></li>
70	<li><a href="#where">Where Defined</a></li>
71	<li><a href="#models">Models</a></li>
72	<li><a href="#template-parms">Template parameters</a></li>
73	<li><a href="#properties">Properties</a></li>
74	<li><a href="#member-functions">Member functions</a>
75	<ul>
76	<li><a href="#constructors">Constructors</a></li>
77	<li><a href="#mutators">Mutators</a></li>
78	<li><a href="#property-access">Property access</a></li>
79	</ul></li>
80
81	<li><a href="#non-members">Non-member functions</a>
82	<ul>
83	<li><a href="#vertex-access">Vertex access</a></li>
84	<li><a href="#edge-access">Edge access</a></li>
85	<li><a href="#property-map-accessors">Property map accessors</a></li>
86	<li><a href="#incremental-construction-functions">Incremental construction functions</a></li>
87	</ul></li>
88
89	<li><a href="#example">Example</a></li>
90	</ul>
91
92	<a name="synopsis"></a><h2>Synopsis</h2>
93
94	<pre>
95	namespace boost {
96
97	template<typename <a href="#Directed">Directed</a> = directedS, typename <a href="#VertexProperty">VertexProperty</a> = void,
98	typename <a href="#EdgeProperty">EdgeProperty</a> = void, typename <a href="#GraphProperty">GraphProperty</a> = no_property,
99	typename <a href="#Vertex">Vertex</a> = std::size_t, typename <a href="#EdgeIndex">EdgeIndex</a> = Vertex>
100	class compressed_sparse_row_graph
101	{
102	public:
103	<i>// <a href="#constructors">Graph constructors</a></i>
104	<a href="#default-const">compressed_sparse_row_graph</a>();
105
106	template<typename InputIterator>
107	<a href="#edge-const">compressed_sparse_row_graph</a>(InputIterator edge_begin, InputIterator edge_end,
108	vertices_size_type numverts,
109	edges_size_type numedges = 0,
110	const GraphProperty& prop = GraphProperty());
111
112	template<typename InputIterator, typename EdgePropertyIterator>
113	<a href="#edge-prop-const">compressed_sparse_row_graph</a>(InputIterator edge_begin, InputIterator edge_end,
114	EdgePropertyIterator ep_iter,
115	vertices_size_type numverts,
116	edges_size_type numedges = 0,
117	const GraphProperty& prop = GraphProperty());
118
119	template<typename Graph, typename VertexIndexMap>
120	<a href="#graph-const">compressed_sparse_row_graph</a>(const Graph& g, const VertexIndexMap& vi,
121	vertices_size_type numverts,
122	edges_size_type numedges);
123
124	template<typename Graph, typename VertexIndexMap>
125	compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi);
126
127	template<typename Graph>
128	explicit <a href="#graph-const">compressed_sparse_row_graph</a>(const Graph& g);
129
130	<i>// <a href="#mutators">Graph mutators</a></i>
131	template<typename Graph, typename VertexIndexMap>
132	void <a href="#assign">assign</a>(const Graph& g, const VertexIndexMap& vi,
133	vertices_size_type numverts, edges_size_type numedges);
134
135	template<typename Graph, typename VertexIndexMap>
136	void <a href="#assign">assign</a>(const Graph& g, const VertexIndexMap& vi);
137
138	template<typename Graph>
139	void <a href="#assign">assign</a>(const Graph& g);
140
141	<i>// <a href="#property-access">Property Access</a></i>
142	VertexProperty& <a href="#vertex-subscript">operator[]</a>(vertex_descriptor v);
143	const VertexProperty& <a href="#vertex-subscript">operator[]</a>(vertex_descriptor v) const;
144	EdgeProperty& <a href="#edge-subscript">operator[]</a>(edge_descriptor v);
145	const EdgeProperty& <a href="#edge-subscript">operator[]</a>(edge_descriptor v) const;
146	};
147
148	<i>// <a href="IncidenceGraph.html">Incidence Graph requirements</a></i>
149	vertex_descriptor source(edge_descriptor, const compressed_sparse_row_graph&);
150	vertex_descriptor target(edge_descriptor, const compressed_sparse_row_graph&);
151	std::pair<out_edge_iterator, out_edge_iterator>
152	out_edges(vertex_descriptor, const compressed_sparse_row_graph&);
153	degree_size_type out_degree(vertex_descriptor v, const compressed_sparse_row_graph&);
154
155	<i>// <a href="AdjacencyGraph.html">Adjacency Graph requirements</a></i>
156	std::pair<adjacency_iterator, adjacency_iterator>
157	adjacent_vertices(vertex_descriptor, const compressed_sparse_row_graph&);
158
159	<i>// <a href="VertexListGraph.html">Vertex List Graph requirements</a></i>
160	std::pair<vertex_iterator, vertex_iterator> vertices(const compressed_sparse_row_graph&);
161	vertices_size_type num_vertices(const compressed_sparse_row_graph&);
162
163	<i>// <a href="EdgeListGraph.html">Edge List Graph requirements</a></i>
164	std::pair<edge_iterator, edge_iterator> edges(const compressed_sparse_row_graph&);
165	edges_size_type num_edges(const compressed_sparse_row_graph&);
166
167	<i>// <a href="#vertex-access">Vertex access</a></i>
168	vertex_descriptor <a href="#vertex">vertex</a>(vertices_size_type i, const compressed_sparse_row_graph&);
169
170	<i>// <a href="#edge-access">Edge access</a></i>
171	std::pair<out_edge_iterator, out_edge_iterator>
172	<a href="#edge_range">edge_range</a>(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&);
173	std::pair<edge_descriptor, bool>
174	<a href="#edge">edge</a>(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&);
175	edge_descriptor <a href="#edge_from_index">edge_from_index</a>(edges_size_type i, const compressed_sparse_row_graph&);
176
177	<i>// <a href="#property-map-accessors">Property map accessors</a></i>
178	template<typename <a href="./PropertyTag.html">PropertyTag</a>>
179	property_map<compressed_sparse_row_graph, PropertyTag>::type
180	<a href="#get">get</a>(PropertyTag, compressed_sparse_row_graph& g)
181
182	template<typename <a href="./PropertyTag.html">PropertyTag</a>>
183	property_map<compressed_sparse_row_graph, Tag>::const_type
184	<a href="#get">get</a>(PropertyTag, const compressed_sparse_row_graph& g)
185
186	template<typename <a href="./PropertyTag.html">PropertyTag</a>, class X>
187	typename property_traits<property_map<compressed_sparse_row_graph, PropertyTag>::const_type&gt::value_type
188	<a href="#get-x">get</a>(PropertyTag, const compressed_sparse_row_graph& g, X x)
189
190	template<typename <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value>
191	void <a href="#put-x">put</a>(PropertyTag, const compressed_sparse_row_graph& g, X x, const Value& value);
192
193	template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>>
194	typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type&
195	<a href="#get_property">get_property</a>(compressed_sparse_row_graph& g, GraphPropertyTag);
196
197	template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>>
198	typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type const &
199	<a href="#get_property">get_property</a>(const compressed_sparse_row_graph& g, GraphPropertyTag);
200
201	template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>>
202	void <a href="#set_property">set_property</a>(const compressed_sparse_row_graph& g, GraphPropertyTag,
203	const typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type& value);
204
205	<i>// <a href="#incremental-construction-functions">Incremental construction functions</a></i>
206	template<typename Graph>
207	vertex_descriptor <a href=#add_vertex">add_vertex</a>(compressed_sparse_row_graph& g);
208
209	template<typename Graph>
210	vertex_descriptor <a href=#add_vertices">add_vertices</a>(vertices_size_type count, compressed_sparse_row_graph& g);
211
212	template<typename Graph>
213	edge_descriptor <a href=#add_edge">add_vertices</a>(vertex_descriptor src, vertex_descriptor tgt, compressed_sparse_row_graph& g);
214
215	} <i>// end namespace boost</i>
216	</pre>
217
218	<a name="where"></a><h2>Where Defined</h2>
219	<p><code><<a href="../../../boost/graph/compressed_sparse_row_graph.hpp">boost/graph/compressed_sparse_row_graph.hpp</a>></code></p>
220
221	<a name="models"></a><h2>Models</h2>
222
223	<p>The <tt>compressed_sparse_row_graph</tt> class template models
224	(i.e., implements the requirements of) many of the
225	BGL <a href="graph_concepts.html">graph concepts</a>, allowing it
226	to be used with most of the BGL algorithms. In particular, it
227	models the following specific graph concepts:</p>
228
229	<ul>
230	<li><a href="Graph.html">Graph</a></li>
231	<li><a href="IncidenceGraph.html">IncidenceGraph</a></li>
232	<li><a href="AdjacencyGraph.html">AdjacencyGraph</a></li>
233	<li><a href="VertexListGraph.html">VertexListGraph</a></li>
234	<li><a href="EdgeListGraph.html">EdgeListGraph</a></li>
235	<li><a href="PropertyGraph.html">PropertyGraph</a></li>
236	</ul>
237
238	<a name="template-parms"></a><h2>Template Parameters</h2>
239
240	<p>The <tt>compressed_sparse_row_graph</tt> class has several
241	template parameters that can customize the layout in memory and
242	what properties are attached to the graph itself. All
243	parameters have defaults, so users interested only in the
244	structure of a graph can use the
245	type <tt>compressed_sparse_row_graph<></tt> and ignore
246	the parameters.</p>
247
248	<b>Parameters</b>
249	<br>
250	<br>
251
252	<a name="Directed"></a><code>Directed</code>
253	<blockquote>
254	A selector that determines whether the graph will be directed,
255	bidirectional or undirected. At this time, the CSR graph type
256	only supports directed graphs, so this value must
257	be <code>boost::directedS</code>.<br>
258	<b>Default</b>: <code>boost::directedS</code>
259	</blockquote>
260
261	<a name="VertexProperty"></a><code>VertexProperty</code>
262	<blockquote>
263	A class type that will be
264	attached to each vertex in the graph. If this value
265	is <code>void</code>, no properties will be attached to
266	the vertices of the graph.<br>
267	<b>Default</b>: <code>void</code>
268	</blockquote>
269
270	<a name="EdgeProperty"></a><code>EdgeProperty</code>
271	<blockquote>
272	A class type that will be attached to each edge in the graph. If
273	this value is <code>void</code>, no properties will be
274	attached to the edges of the graph.<br>
275	<b>Default</b>: <code>void</code>
276	</blockquote>
277
278	<a name="GraphProperty"></a><code>GraphProperty</code>
279	<blockquote>
280	A nested set
281	of <code>property</code> templates that describe the
282	properties of the graph itself. If this value
283	is <code>no_property</code>, no properties will be attached to
284	the graph.<br>
285	<b>Default</b>: <code>no_property</code>
286	</blockquote>
287
288	<a name="Vertex"></a><code>Vertex</code>
289	<blockquote>
290	An unsigned integral type that will be
291	used as both the index into the array of vertices and as the
292	vertex descriptor itself. Larger types permit the CSR graph to
293	store more vertices; smaller types reduce the storage required
294	per vertex.<br>
295	<b>Default</b>: <code>std::size_t</code>
296	</blockquote>
297
298	<a name="EdgeIndex"></a><code>EdgeIndex</code>
299	<blockquote>
300	An unsigned integral type that will be used as the index into
301	the array of edges. As with the <code>Vertex</code> parameter,
302	larger types permit more edges whereas smaller types reduce
303	the amount of storage needed per
304	edge. The <code>EdgeIndex</code> type shall not be smaller
305	than the <code>Vertex</code> type, but it may be larger. For
306	instance, <code>Vertex</code> may be a 16-bit integer
307	(allowing 32,767 vertices in the graph)
308	whereas <code>EdgeIndex</code> could then be a 32-bit integer
309	to allow a complete graph to be stored in the CSR format.<br>
310	<b>Default</b>: <code>Vertex</code>
311	</blockquote>
312
313	<a name="properties"></a><h2>Interior Properties</h2>
314
315	<p> The <tt>compressed_sparse_row_graph</tt> allows properties to
316	be attached to its vertices, edges, or to the graph itself by way
317	of its <a href="#template-parms">template parameters</a>. These
318	properties may be accessed via
319	the <a href="#property-access">member</a>
320	and <a href="#property-map-accessors">non-member</a> property
321	access functions, using the <a href="bundles.html">bundled
322	properties</a> scheme.</p>
323
324	<p>The CSR graph provides two kinds of built-in
325	properties: <tt>vertex_index</tt>, which maps from vertices to
326	values in <tt>[0, n)</tt> and <tt>edge_index</tt>, which maps
327	from edges to values in <tt>[0, m)</tt>, where <tt>n</tt>
328	and <tt>m</tt> are the number of vertices and edges in the graph,
329	respectively. </p>
330
331	<a name="member-functions"></a><h2>Member Functions</h2>
332
333	<a name="constructors"></a><h3>Constructors</h3>
334	<pre><a name="default-const"></a>
335	compressed_sparse_row_graph();
336	</pre>
337	<p class="indent">Constructs a graph with no vertices or edges.</p>
338
339	<hr></hr>
340
341	<pre><a name="edge-const"></a>
342	template<typename InputIterator>
343	compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
344	vertices_size_type numverts,
345	edges_size_type numedges = 0,
346	const GraphProperty& prop = GraphProperty());
347	</pre>
348
349	<p class="indent">
350	Constructs a graph with <code>numverts</code> vertices whose
351	edges are specified by the iterator range <code>[edge_begin,
352	edge_end)</code>. The <tt>InputIterator</tt> must be a model of
353	<a
354	href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>
355	whose <code>value_type</code> is an <code>std::pair</code> of
356	integer values. These integer values are the source and target
357	vertices for the edges, and must fall within the range <code>[0,
358	numverts)</code>. The edges in <code>[edge_begin,
359	edge_end)</code> must be sorted so that all edges originating
360	from vertex <i>i</i> preceed any edges originating from all
361	vertices <i>j</i> where <i>j > i</i>.
362	</p>
363
364	<p class="indent">
365	The value <code>numedges</code>, if provided, tells how many
366	edges are in the range <code>[edge_begin, edge_end)</code> and
367	will be used to preallocate data structures to save both memory
368	and time during construction.
369	</p>
370
371	<p class="indent">
372	The value <code>prop</code> will be used to initialize the graph
373	property.
374	</p>
375
376	<hr></hr>
377
378	<pre><a name="edge-prop-const"></a>
379	template<typename InputIterator, typename EdgePropertyIterator>
380	compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
381	EdgePropertyIterator ep_iter,
382	vertices_size_type numverts,
383	edges_size_type numedges = 0,
384	const GraphProperty& prop = GraphProperty());
385	</pre>
386	<p class="indent">
387	This constructor constructs a graph with <code>numverts</code>
388	vertices and the edges provided in the iterator range
389	<code>[edge_begin, edge_end)</code>. Its semantics are identical
390	to the <a href="#edge-const">edge range constructor</a>, except
391	that edge properties are also initialized. The type
392	<tt>EdgePropertyIterator</tt> must be a model of the <a
393	href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>
394	concept whose <tt>value_type</tt> is convertible to
395	<tt>EdgeProperty</tt>. The iterator range <tt>[ep_iter, ep_ter +
396	m)</tt> will be used to initialize the properties on the edges
397	of the graph, where <tt>m</tt> is distance from
398	<tt>edge_begin</tt> to <tt>edge_end</tt>.
399	</p>
400
401	<hr></hr>
402
403	<pre><a name="#graph-const"></a>
404	template<typename Graph, typename VertexIndexMap>
405	compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi,
406	vertices_size_type numverts,
407	edges_size_type numedges);
408
409	template<typename Graph, typename VertexIndexMap>
410	compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi);
411
412	template<typename Graph>
413	explicit compressed_sparse_row_graph(const Graph& g);
414	</pre>
415
416	<p class="indent">
417	Calls the <a href="#assign"><tt>assign</tt></a> function with
418	all of the arguments it is given.
419	</p>
420
421	<hr></hr>
422
423	<a name="mutators"></a><h3>Mutators</h3>
424	<pre><a name="assign"></a>
425	template<typename Graph, typename VertexIndexMap>
426	void assign(const Graph& g, const VertexIndexMap& vi,
427	vertices_size_type numverts, edges_size_type numedges);
428
429	template<typename Graph, typename VertexIndexMap>
430	void assign(const Graph& g, const VertexIndexMap& vi);
431
432	template<typename Graph>
433	void assign(const Graph& g);
434	</pre>
435
436	<p class="indent">
437	Clears the CSR graph and builds a CSR graph in place from the
438	structure of another graph. The graph type <tt>Graph</tt> must
439	be a model of <a href="IncidenceGraph.html">IncidenceGraph</a>
440	and have a <tt>vertex(i, g)</tt> function that retrieves the
441	<i>i</i><sup>th</sup> vertex in the graph.
442
443	<br><b>Parameters</b>
444
445	<ul>
446	<li><tt>g</tt>: The incoming graph.</li>
447
448	<li><tt>vi</tt>: A map from vertices to indices. If not
449	provided, <tt>get(vertex_index, g)</tt> will be used.</li>
450
451	<li><tt>numverts</tt>: The number of vertices in the graph
452	<tt>g</tt>. If not provided, <tt>Graph</tt> must be a model of
453	<a href="VertexListGraph.html">VertexListGraph</a>.</li>
454
455	<li><tt>numedges</tt>: The number of edges in the graph
456	<tt>g</tt>. If not provided, <tt>Graph</tt> must be a model of
457	<a href="EdgeListGraph.html">EdgeListGraph</a>.</li>
458	</ul>
459	</p>
460
461	<hr></hr>
462
463	<a name="property-access"></a><h3>Property Access</h3>
464
465	<pre><a name="vertex-subscript"></a>
466	VertexProperty& operator[](vertex_descriptor v);
467	const VertexProperty& operator[](vertex_descriptor v) const;
468	</pre>
469
470	<p class="indent">
471	Retrieves the property value associated with vertex
472	<tt>v</tt>. Only valid when <tt>VertexProperty</tt> is a class
473	type that is not <tt>no_property</tt>.
474	</p>
475
476	<hr></hr>
477
478	<pre><a name="edge-subscript">
479	EdgeProperty& operator[](edge_descriptor v);
480	const EdgeProperty& operator[](edge_descriptor v) const;
481	</pre>
482
483	<p class="indent">
484	Retrieves the property value associated with edge
485	<tt>v</tt>. Only valid when <tt>EdgeProperty</tt> is a class
486	type that is not <tt>no_property</tt>.
487	</p>
488
489	<hr></hr>
490	<a name="non-members"></a><h2>Non-member Functions</h2>
491
492	<a name="vertex-access"></a><h3>Vertex access</h3>
493
494	<pre><a name="vertex"></a>
495	vertex_descriptor vertex(vertices_size_type i, const compressed_sparse_row_graph&);
496	</pre>
497	<p class="indent">
498	Retrieves the <i>i</i><sup>th</sup> vertex in the graph in
499	constant time.
500	</p>
501
502	<hr></hr>
503
504	<a name="edge-access"></a><h3>Edge access</h3>
505	<pre><a name="edge_range"></a>
506	std::pair<out_edge_iterator, out_edge_iterator>
507	edge_range(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&);
508	</pre>
509
510	<p class="indent">
511	Returns all edges from <tt>u</tt> to <tt>v</tt>. Requires time
512	linear in the number of edges outgoing from <tt>u</tt>.
513	</p>
514
515	<hr></hr>
516
517	<pre><a name="edge"></a>
518	std::pair<edge_descriptor, bool>
519	edge(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&);
520	</pre>
521
522	<p class="indent">
523	If there exists an edge <i>(u, v)</i> in the graph, returns the
524	descriptor for that edge and <tt>true</tt>; otherwise, the
525	second value in the pair will be <tt>false</tt>. If multiple
526	edges exist from <tt>u</tt> to <tt>v</tt>, the first edge will
527	be returned; use <a href="#edge_range"><tt>edge_range</tt></a>
528	to retrieve all edges.
529	</p>
530
531	<hr></hr>
532
533	<pre><a name="edge_from_index"></a>
534	edge_descriptor edge_from_index(edges_size_type i, const compressed_sparse_row_graph&);
535	</pre>
536
537	<p class="indent">
538	Returns the <i>i</i><sup>th</sup> edge in the graph. This
539	operation requires logarithmic time in the number of vertices.
540	</p>
541
542	<hr></hr>
543
544	<h3><a name="property-map-accessors">Property Map Accessors</a></h3>
545
546	<pre><a name="get"></a>
547	template<typename <a href="./PropertyTag.html">PropertyTag</a>>
548	property_map<compressed_sparse_row_graph, PropertyTag>::type
549	get(PropertyTag, compressed_sparse_row_graph& g)
550
551	template<typename <a href="./PropertyTag.html">PropertyTag</a>>
552	property_map<compressed_sparse_row_graph, Tag>::const_type
553	get(PropertyTag, const compressed_sparse_row_graph& g)
554	</pre>
555
556	<p class="indent">
557	Returns the property map object for the vertex property
558	specified by <TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must
559	be a member pointer to access one of the fields in
560	<tt>VertexProperty</tt> or <tt>EdgeProperty</tt>.
561	</p>
562
563	<hr></hr>
564
565	<pre><a name="get-x"></a>
566	template<typename <a href="./PropertyTag.html">PropertyTag</a>, class X>
567	typename property_traits<property_map<compressed_sparse_row_graph, PropertyTag>::const_type&gt::value_type
568	get(PropertyTag, const compressed_sparse_row_graph& g, X x)
569	</pre>
570
571	<p class="indent">
572	This returns the property value for <tt>x</tt>, where <tt>x</tt>
573	is either a vertex or edge descriptor.
574	</p>
575
576	<hr></hr>
577
578	<pre><a name="put-x"></a>
579	template<typename <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value>
580	void put(PropertyTag, const compressed_sparse_row_graph& g, X x, const Value& value);
581	</pre>
582
583	<p class="indent">
584	This sets the property value for <tt>x</tt> to
585	<tt>value</tt>. <tt>x</tt> is either a vertex or edge
586	descriptor. <tt>Value</tt> must be convertible to <tt>typename
587	property_traits<property_map<compressed_sparse_row_graph,
588	PropertyTag>::type&gt::value_type</tt>
589	</p>
590
591	<hr></hr>
592
593	<pre><a name="get_property"></a>
594	template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>>
595	typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type&
596	get_property(compressed_sparse_row_graph& g, GraphPropertyTag);
597
598	template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>>
599	typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type const &
600	get_property(const compressed_sparse_row_graph& g, GraphPropertyTag);
601	</pre>
602
603	<p class="indent">
604	Return the property specified by <tt>GraphPropertyTag</tt> that
605	is attached to the graph object <tt>g</tt>.
606	</p>
607
608	<hr></hr>
609
610	<pre><a name="set_property"></a>
611	template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>>
612	void set_property(const compressed_sparse_row_graph& g, GraphPropertyTag,
613	const typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type& value);
614	</pre>
615
616	<p class="indent">
617	Set the property specified by <tt>GraphPropertyTag</tt> that
618	is attached to the graph object <tt>g</tt>.
619	</p>
620
621	<hr></hr>
622
623	<h3><a name="incremental-construction-functions">Incremental construction functions</a></h3>
624
625	<pre><a name="add_vertex"></a>
626	vertex_descriptor add_vertex(compressed_sparse_row_graph& g)
627	</pre>
628
629	<p class="indent">
630	Add a new vertex to the end of the graph <tt>g</tt>, and return a
631	descriptor for that vertex. The new vertex will be greater than any of
632	the previous vertices in <tt>g</tt>.
633	</p>
634
635	<hr></hr>
636
637	<pre><a name="add_vertices"></a>
638	vertex_descriptor add_vertices(vertices_size_type count, compressed_sparse_row_graph& g)
639	</pre>
640
641	<p class="indent">
642	Add <tt>count</tt> new vertices to the end of the graph <tt>g</tt>, and
643	return a descriptor for the smallest new vertex. The new vertices will
644	be greater than any of the previous vertices in <tt>g</tt>.
645	</p>
646
647	<hr></hr>
648
649	<pre><a name="add_edge"></a>
650	edge_descriptor add_edge(vertex_descriptor src, vertex_descriptor tgt, compressed_sparse_row_graph& g)
651	</pre>
652
653	<p class="indent">
654	Add a new edge from <tt>src</tt> to <tt>tgt</tt> in the graph <tt>g</tt>,
655	and return a descriptor for it. There must not be an edge in <tt>g</tt>
656	whose source vertex is greater than <tt>src</tt>. If the vertex
657	<tt>src</tt> has out edges before this operation is called, there must be
658	none whose target is larger than <tt>tgt</tt>.
659	</p>
660
661	<hr></hr>
662	<a name="example"></a><h2>Example</h2>
663
664	<br>[<a
665	href="../example/csr-example.cpp">libs/graph/example/csr-example.cpp</a>]
666
667	<p>We will use the <tt>compressed_sparse_row_graph</tt> graph
668	class to store a simple Web graph. In this web graph the vertices
669	represent web pages and the edges represent links from one web
670	page to another. With each web page we want to associate a URL, so
671	we initially create a <tt>WebPage</tt> class that stores the
672	URL. Then we can create our graph type by providing
673	<tt>WebPage</tt> as a parameter to the
674	<tt>compressed_sparse_row_graph</tt> class template.</p>
675
676	<pre>
677	class WebPage
678	{
679	public:
680	std::string url;
681	};
682
683	// ...
684
685	typedef compressed_sparse_row_graph<directedS, WebPage> WebGraph;
686	WebGraph g(&the_edges[0], &the_edges[0] + sizeof(the_edges)/sizeof(E), 6);
687	</pre>
688
689	<p>We can then set the properties on the vertices of the graph
690	using the <a href="bundles.html">bundled properties</a> syntax,
691	and display the edges for the user.</p>
692
693	<pre>
694	// Set the URLs of each vertex
695	int index = 0;
696	BGL_FORALL_VERTICES(v, g, WebGraph)
697	g[v].url = urls[index++];
698
699	// Output each of the links
700	std::cout << "The web graph:" << std::endl;
701	BGL_FORALL_EDGES(e, g, WebGraph)
702	std::cout << " " << g[source(e, g)].url << " -> " << g[target(e, g)].url
703	<< std::endl;
704	</pre>
705
706	<p>See the <a href="../example/csr-example.cpp">complete example
707	source</a> for other operations one can perform with a
708	<tt>compressed_sparse_row_graph</tt>.</p>
709	<br>
710	<HR>
711	<TABLE>
712	<TR valign=top>
713	<TD nowrap>Copyright © 2005</TD><TD>
714	<A HREF="../../../people/doug_gregor.html">Doug Gregor</A>, Indiana University (<script language="Javascript">address("cs.indiana.edu", "dgregor")</script>)<br>
715	Jeremiah Willcock, Indiana University (<script language="Javascript">address("osl.iu.edu", "jewillco")</script>)<br>
716	<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
717	Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
718	</TD></TR></TABLE>
719	</body>
720	</html>

Note: See TracBrowser for help on using the repository browser.

Download in other formats: