1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> 2<html> 3<!-- 4 Copyright (c) 2005-2009 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<!-- 25function 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 (and bidirectional) graphs. While CSR graphs have 44 much less 45 overhead than many other graph formats (e.g., <a 46 href="adjacency_list.html"><code>adjacency_list</code></a>), they 47 do not provide any mutability: one cannot add or remove vertices 48 or edges from a CSR graph. Use this format in high-performance 49 applications or for very large graphs that you do not need to 50 change.</p> 51 52 <p>The CSR format stores vertices and edges in separate arrays, 53 with the indices into these arrays corresponding to the identifier 54 for the vertex or edge, respectively. The edge array is sorted by 55 the source of each edge, but contains only the targets for the 56 edges. The vertex array stores offsets into the edge array, 57 providing the offset of the first edge outgoing from each 58 vertex. Iteration over the out-edges for the <i>i</i><sup>th</sup> 59 vertex in the graph is achieved by 60 visiting <tt>edge_array[vertex_array[i]]</tt>, 61 <tt>edge_array[vertex_array[i]+1]</tt>, 62 ..., <tt>edge_array[vertex_array[i+1]]</tt>. This format minimizes 63 memory use to <i>O(n + m)</i>, where <i>n</i> and <i>m</i> are the 64 number of vertices and edges, respectively. The constants 65 multiplied by <i>n</i> and <i>m</i> are based on the size of the 66 integers needed to represent indices into the edge and vertex 67 arrays, respectively, which can be controlled using 68 the <a href="#template-parms">template parameters</a>. The 69 <tt>Directed</tt> template parameter controls whether one edge direction 70 (the default) or both directions are stored. A directed CSR graph has 71 <tt>Directed</tt> = <tt>directedS</tt> and a bidirectional CSR graph (with 72 a limited set of constructors) 73 has <tt>Directed</tt> = <tt>bidirectionalS</tt>.</p> 74 75 <ul> 76 <li><a href="#synopsis">Synopsis</a></li> 77 <li><a href="#where">Where Defined</a></li> 78 <li><a href="#models">Models</a></li> 79 <li><a href="#template-parms">Template parameters</a></li> 80 <li><a href="#properties">Properties</a></li> 81 <li><a href="#member-functions">Member functions</a> 82 <ul> 83 <li><a href="#constructors">Constructors</a></li> 84 <li><a href="#mutators">Mutators</a></li> 85 <li><a href="#property-access">Property access</a></li> 86 </ul></li> 87 88 <li><a href="#non-members">Non-member functions</a> 89 <ul> 90 <li><a href="#vertex-access">Vertex access</a></li> 91 <li><a href="#edge-access">Edge access</a></li> 92 <li><a href="#property-map-accessors">Property map accessors</a></li> 93 <li><a href="#incremental-construction-functions">Incremental construction functions</a></li> 94 </ul></li> 95 96 <li><a href="#example">Example</a></li> 97 </ul> 98 99 <a name="synopsis"></a><h2>Synopsis</h2> 100 101 <pre> 102namespace boost { 103 104template<typename <a href="#Directed">Directed</a> = directedS, typename <a href="#VertexProperty">VertexProperty</a> = no_property, 105 typename <a href="#EdgeProperty">EdgeProperty</a> = no_property, typename <a href="#GraphProperty">GraphProperty</a> = no_property, 106 typename <a href="#Vertex">Vertex</a> = std::size_t, typename <a href="#EdgeIndex">EdgeIndex</a> = Vertex> 107class compressed_sparse_row_graph 108{ 109public: 110 <i>// <a href="#constructors">Graph constructors</a></i> 111 <a href="#default-const">compressed_sparse_row_graph</a>(); 112 113 <i>// Unsorted edge list constructors </i> 114 template<typename InputIterator> 115 <a href="#edge-const">compressed_sparse_row_graph</a>(edges_are_unsorted_t, 116 InputIterator edge_begin, InputIterator edge_end, 117 vertices_size_type numverts, 118 const GraphProperty& prop = GraphProperty()); 119 120 template<typename InputIterator, typename EdgePropertyIterator> 121 <a href="#edge-prop-const">compressed_sparse_row_graph</a>(edges_are_unsorted_t, 122 InputIterator edge_begin, InputIterator edge_end, 123 EdgePropertyIterator ep_iter, 124 vertices_size_type numverts, 125 const GraphProperty& prop = GraphProperty()); 126 127 template<typename MultiPassInputIterator> 128 <a href="#edge-multi-const">compressed_sparse_row_graph</a>(edges_are_unsorted_multi_pass_t, 129 MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end, 130 vertices_size_type numverts, 131 const GraphProperty& prop = GraphProperty()); 132 133 template<typename MultiPassInputIterator, typename EdgePropertyIterator> 134 <a href="#edge-multi-prop-const">compressed_sparse_row_graph</a>(edges_are_unsorted_multi_pass_t, 135 MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end, 136 EdgePropertyIterator ep_iter, 137 vertices_size_type numverts, 138 const GraphProperty& prop = GraphProperty()); 139 140 <i>// New sorted edge list constructors <b>(directed only)</b></i> 141 template<typename InputIterator> 142 <a href="#edge-sorted-const">compressed_sparse_row_graph</a>(edges_are_sorted_t, 143 InputIterator edge_begin, InputIterator edge_end, 144 vertices_size_type numverts, 145 edges_size_type numedges = 0, 146 const GraphProperty& prop = GraphProperty()); 147 148 template<typename InputIterator, typename EdgePropertyIterator> 149 <a href="#edge-sorted-prop-const">compressed_sparse_row_graph</a>(edges_are_sorted_t, 150 InputIterator edge_begin, InputIterator edge_end, 151 EdgePropertyIterator ep_iter, 152 vertices_size_type numverts, 153 edges_size_type numedges = 0, 154 const GraphProperty& prop = GraphProperty()); 155 156 <i>// In-place unsorted edge list constructors <b>(directed only)</b></i> 157 template<typename InputIterator> 158 <a href="#edge-inplace-const">compressed_sparse_row_graph</a>(construct_inplace_from_sources_and_targets_t, 159 std::vector<vertex_descriptor>& sources, 160 std::vector<vertex_descriptor>& targets, 161 vertices_size_type numverts, 162 const GraphProperty& prop = GraphProperty()); 163 164 template<typename InputIterator> 165 <a href="#edge-inplace-prop-const">compressed_sparse_row_graph</a>(construct_inplace_from_sources_and_targets_t, 166 std::vector<vertex_descriptor>& sources, 167 std::vector<vertex_descriptor>& targets, 168 std::vector<EdgeProperty>& edge_props, 169 vertices_size_type numverts, 170 const GraphProperty& prop = GraphProperty()); 171 172 <i>// Miscellaneous constructors <b>(directed only)</b></i> 173 template<typename Graph, typename VertexIndexMap> 174 <a href="#graph-const">compressed_sparse_row_graph</a>(const Graph& g, const VertexIndexMap& vi, 175 vertices_size_type numverts, 176 edges_size_type numedges); 177 178 template<typename Graph, typename VertexIndexMap> 179 compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi); 180 181 template<typename Graph> 182 explicit <a href="#graph-const">compressed_sparse_row_graph</a>(const Graph& g); 183 184 <i>// <a href="#mutators">Graph mutators <b>(directed only)</b></a></i> 185 template<typename Graph, typename VertexIndexMap> 186 void <a href="#assign">assign</a>(const Graph& g, const VertexIndexMap& vi, 187 vertices_size_type numverts, edges_size_type numedges); 188 189 template<typename Graph, typename VertexIndexMap> 190 void <a href="#assign">assign</a>(const Graph& g, const VertexIndexMap& vi); 191 192 template<typename Graph> 193 void <a href="#assign">assign</a>(const Graph& g); 194 195 <i>// <a href="#property-access">Property Access</a></i> 196 VertexProperty& <a href="#vertex-subscript">operator[]</a>(vertex_descriptor v); 197 const VertexProperty& <a href="#vertex-subscript">operator[]</a>(vertex_descriptor v) const; 198 EdgeProperty& <a href="#edge-subscript">operator[]</a>(edge_descriptor v); 199 const EdgeProperty& <a href="#edge-subscript">operator[]</a>(edge_descriptor v) const; 200}; 201 202<i>// <a href="IncidenceGraph.html">Incidence Graph requirements</a></i> 203vertex_descriptor source(edge_descriptor, const compressed_sparse_row_graph&); 204vertex_descriptor target(edge_descriptor, const compressed_sparse_row_graph&); 205std::pair<out_edge_iterator, out_edge_iterator> 206 out_edges(vertex_descriptor, const compressed_sparse_row_graph&); 207degree_size_type out_degree(vertex_descriptor v, const compressed_sparse_row_graph&); 208 209<i>// <a href="BidirectionalGraph.html">Bidirectional Graph requirements <b>(bidirectional only)</b></a></i> 210std::pair<in_edge_iterator, in_edge_iterator> 211 in_edges(vertex_descriptor, const compressed_sparse_row_graph&); 212degree_size_type in_degree(vertex_descriptor v, const compressed_sparse_row_graph&); 213 214<i>// <a href="AdjacencyGraph.html">Adjacency Graph requirements</a></i> 215std::pair<adjacency_iterator, adjacency_iterator> 216 adjacent_vertices(vertex_descriptor, const compressed_sparse_row_graph&); 217 218<i>// <a href="VertexListGraph.html">Vertex List Graph requirements</a></i> 219std::pair<vertex_iterator, vertex_iterator> vertices(const compressed_sparse_row_graph&); 220vertices_size_type num_vertices(const compressed_sparse_row_graph&); 221 222<i>// <a href="EdgeListGraph.html">Edge List Graph requirements</a></i> 223std::pair<edge_iterator, edge_iterator> edges(const compressed_sparse_row_graph&); 224edges_size_type num_edges(const compressed_sparse_row_graph&); 225 226<i>// <a href="#vertex-access">Vertex access</a></i> 227vertex_descriptor <a href="#vertex-lookup">vertex</a>(vertices_size_type i, const compressed_sparse_row_graph&); 228 229<i>// <a href="#edge-access">Edge access</a></i> 230std::pair<edge_descriptor, bool> 231 <a href="#edge">edge</a>(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&); 232edge_descriptor <a href="#edge_from_index">edge_from_index</a>(edges_size_type i, const compressed_sparse_row_graph&); 233 234<i>// <a href="#property-map-accessors">Property map accessors</a></i> 235template<typename <a href="./PropertyTag.html">PropertyTag</a>> 236property_map<compressed_sparse_row_graph, PropertyTag>::type 237<a href="#get">get</a>(PropertyTag, compressed_sparse_row_graph& g) 238 239template<typename <a href="./PropertyTag.html">PropertyTag</a>> 240property_map<compressed_sparse_row_graph, Tag>::const_type 241<a href="#get">get</a>(PropertyTag, const compressed_sparse_row_graph& g) 242 243template<typename <a href="./PropertyTag.html">PropertyTag</a>, class X> 244typename property_traits<property_map<compressed_sparse_row_graph, PropertyTag>::const_type>::value_type 245<a href="#get-x">get</a>(PropertyTag, const compressed_sparse_row_graph& g, X x) 246 247template<typename <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value> 248void <a href="#put-x">put</a>(PropertyTag, const compressed_sparse_row_graph& g, X x, const Value& value); 249 250template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> 251typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type& 252<a href="#get_property">get_property</a>(compressed_sparse_row_graph& g, GraphPropertyTag); 253 254template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> 255typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type const & 256<a href="#get_property">get_property</a>(const compressed_sparse_row_graph& g, GraphPropertyTag); 257 258template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> 259void <a href="#set_property">set_property</a>(const compressed_sparse_row_graph& g, GraphPropertyTag, 260 const typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type& value); 261 262<i>// <a href="#incremental-construction-functions">Incremental construction functions</a></i> 263<b>(directed only)</b> 264template<typename InputIterator, typename Graph> 265void <a href="#add_edges">add_edges</a>(InputIterator first, InputIterator last, compressed_sparse_row_graph& g); 266 267<b>(directed only)</b> 268template<typename InputIterator, typename EPIter, typename Graph> 269void <a href="#add_edges_prop">add_edges</a>(InputIterator first, InputIterator last, EPIter ep_first, EPIter ep_last, compressed_sparse_row_graph& g); 270 271<b>(directed only)</b> 272template<typename BidirectionalIterator, typename Graph> 273void <a href="#add_edges_sorted">add_edges_sorted</a>(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph& g); 274 275<b>(directed only)</b> 276template<typename BidirectionalIterator, typename EPIter, typename Graph> 277void <a href="#add_edges_sorted_prop">add_edges_sorted</a>(BidirectionalIterator first, BidirectionalIterator last, EPIter ep_iter, compressed_sparse_row_graph& g); 278 279} <i>// end namespace boost</i> 280 </pre> 281 282 <a name="where"></a><h2>Where Defined</h2> 283 <p><code><<a href="../../../boost/graph/compressed_sparse_row_graph.hpp">boost/graph/compressed_sparse_row_graph.hpp</a>></code></p> 284 285 <a name="models"></a><h2>Models</h2> 286 287 <p>The <tt>compressed_sparse_row_graph</tt> class template models 288 (i.e., implements the requirements of) many of the 289 BGL <a href="graph_concepts.html">graph concepts</a>, allowing it 290 to be used with most of the BGL algorithms. In particular, it 291 models the following specific graph concepts:</p> 292 293 <ul> 294 <li><a href="Graph.html">Graph</a></li> 295 <li><a href="IncidenceGraph.html">IncidenceGraph</a></li> 296 <li><a href="AdjacencyGraph.html">AdjacencyGraph</a></li> 297 <li><a href="VertexListGraph.html">VertexListGraph</a></li> 298 <li><a href="EdgeListGraph.html">EdgeListGraph</a></li> 299 <li><a href="PropertyGraph.html">PropertyGraph</a></li> 300 </ul> 301 302 <a name="template-parms"></a><h2>Template Parameters</h2> 303 304 <p>The <tt>compressed_sparse_row_graph</tt> class has several 305 template parameters that can customize the layout in memory and 306 what properties are attached to the graph itself. All 307 parameters have defaults, so users interested only in the 308 structure of a graph can use the 309 type <tt>compressed_sparse_row_graph<></tt> and ignore 310 the parameters.</p> 311 312 <b>Parameters</b> 313 <br> 314 <br> 315 316 <a name="Directed"></a><code>Directed</code> 317 <blockquote> 318 A selector that determines whether the graph will be directed, 319 bidirectional or undirected. At this time, the CSR graph type 320 only supports directed and bidirectional graphs, so this value must 321 be either <code>boost::directedS</code> or 322 <code>boost::bidirectionalS</code>.<br> 323 <b>Default</b>: <code>boost::directedS</code> 324 </blockquote> 325 326 <a name="VertexProperty"></a><code>VertexProperty</code> 327 <blockquote> 328 A class type that will be 329 attached to each vertex in the graph. If this value 330 is <code>void</code>, no properties will be attached to 331 the vertices of the graph.<br> 332 <b>Default</b>: <code>void</code> 333 </blockquote> 334 335 <a name="EdgeProperty"></a><code>EdgeProperty</code> 336 <blockquote> 337 A class type that will be attached to each edge in the graph. If 338 this value is <code>void</code>, no properties will be 339 attached to the edges of the graph.<br> 340 <b>Default</b>: <code>void</code> 341 </blockquote> 342 343 <a name="GraphProperty"></a><code>GraphProperty</code> 344 <blockquote> 345 A nested set 346 of <code>property</code> templates that describe the 347 properties of the graph itself. If this value 348 is <code>no_property</code>, no properties will be attached to 349 the graph.<br> 350 <b>Default</b>: <code>no_property</code> 351 </blockquote> 352 353 <a name="Vertex"></a><code>Vertex</code> 354 <blockquote> 355 An unsigned integral type that will be 356 used as both the index into the array of vertices and as the 357 vertex descriptor itself. Larger types permit the CSR graph to 358 store more vertices; smaller types reduce the storage required 359 per vertex.<br> 360 <b>Default</b>: <code>std::size_t</code> 361 </blockquote> 362 363 <a name="EdgeIndex"></a><code>EdgeIndex</code> 364 <blockquote> 365 An unsigned integral type that will be used as the index into 366 the array of edges. As with the <code>Vertex</code> parameter, 367 larger types permit more edges whereas smaller types reduce 368 the amount of storage needed per 369 edge. The <code>EdgeIndex</code> type shall not be smaller 370 than the <code>Vertex</code> type, but it may be larger. For 371 instance, <code>Vertex</code> may be a 16-bit integer 372 (allowing 32,767 vertices in the graph) 373 whereas <code>EdgeIndex</code> could then be a 32-bit integer 374 to allow a complete graph to be stored in the CSR format.<br> 375 <b>Default</b>: <code>Vertex</code> 376 </blockquote> 377 378 <a name="properties"></a><h2>Interior Properties</h2> 379 380 <p> The <tt>compressed_sparse_row_graph</tt> allows properties to 381 be attached to its vertices, edges, or to the graph itself by way 382 of its <a href="#template-parms">template parameters</a>. These 383 properties may be accessed via 384 the <a href="#property-access">member</a> 385 and <a href="#property-map-accessors">non-member</a> property 386 access functions, using the <a href="bundles.html">bundled 387 properties</a> scheme.</p> 388 389 <p>The CSR graph provides two kinds of built-in 390 properties: <tt>vertex_index</tt>, which maps from vertices to 391 values in <tt>[0, n)</tt> and <tt>edge_index</tt>, which maps 392 from edges to values in <tt>[0, m)</tt>, where <tt>n</tt> 393 and <tt>m</tt> are the number of vertices and edges in the graph, 394 respectively. </p> 395 396 <a name="member-functions"></a><h2>Member Functions</h2> 397 398 <a name="constructors"></a><h3>Constructors</h3> 399 <pre><a name="default-const"></a> 400 compressed_sparse_row_graph(); 401 </pre> 402 <p class="indent">Constructs a graph with no vertices or edges.</p> 403 404 <hr></hr> 405 406 <pre><a name="edge-const"></a> 407 template<typename InputIterator> 408 compressed_sparse_row_graph(edges_are_unsorted_t, 409 InputIterator edge_begin, InputIterator edge_end, 410 vertices_size_type numverts, 411 const GraphProperty& prop = GraphProperty()); 412 </pre> 413 414 <p class="indent"> 415 Constructs a graph with <code>numverts</code> vertices whose 416 edges are specified by the iterator range <code>[edge_begin, 417 edge_end)</code>. The <tt>InputIterator</tt> must be a model of 418 <a 419 href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a> 420 whose <code>value_type</code> is an <code>std::pair</code> of 421 integer values. These integer values are the source and target 422 vertices for the edges, and must fall within the range <code>[0, 423 numverts)</code>. The edges in <code>[edge_begin, 424 edge_end)</code> do not need to be sorted. This constructor uses extra 425 memory to save the edge information before adding it to the graph, 426 avoiding the requirement for the iterator to have multi-pass capability. 427 </p> 428 429 <p class="indent"> 430 The value <code>prop</code> will be used to initialize the graph 431 property. 432 </p> 433 434 <hr></hr> 435 436 <pre><a name="edge-prop-const"></a> 437 template<typename InputIterator, typename EdgePropertyIterator> 438 compressed_sparse_row_graph(edges_are_unsorted_t, 439 InputIterator edge_begin, InputIterator edge_end, 440 EdgePropertyIterator ep_iter, 441 vertices_size_type numverts, 442 const GraphProperty& prop = GraphProperty()); 443 </pre> 444 <p class="indent"> 445 This constructor constructs a graph with <code>numverts</code> 446 vertices and the edges provided in the iterator range 447 <code>[edge_begin, edge_end)</code>. Its semantics are identical 448 to the <a href="#edge-const">edge range constructor</a>, except 449 that edge properties are also initialized. The type 450 <tt>EdgePropertyIterator</tt> must be a model of the <a 451 href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a> 452 concept whose <tt>value_type</tt> is convertible to 453 <tt>EdgeProperty</tt>. The iterator range <tt>[ep_iter, ep_ter + 454 m)</tt> will be used to initialize the properties on the edges 455 of the graph, where <tt>m</tt> is distance from 456 <tt>edge_begin</tt> to <tt>edge_end</tt>. This constructor uses extra 457 memory to save the edge information before adding it to the graph, 458 avoiding the requirement for the iterator to have multi-pass capability. 459 </p> 460 461 <hr></hr> 462 463 <pre><a name="edge-multi-const"></a> 464 template<typename MultiPassInputIterator> 465 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t, 466 MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end, 467 vertices_size_type numverts, 468 const GraphProperty& prop = GraphProperty()); 469 </pre> 470 471 <p class="indent"> 472 Constructs a graph with <code>numverts</code> vertices whose 473 edges are specified by the iterator range <code>[edge_begin, 474 edge_end)</code>. The <tt>MultiPassInputIterator</tt> must be a model of 475 <a 476 href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a> 477 whose <code>value_type</code> is an <code>std::pair</code> of 478 integer values. These integer values are the source and target 479 vertices for the edges, and must fall within the range <code>[0, 480 numverts)</code>. The edges in <code>[edge_begin, 481 edge_end)</code> do not need to be sorted. Multiple passes will be made 482 over the edge range. 483 </p> 484 485 <p class="indent"> 486 The value <code>prop</code> will be used to initialize the graph 487 property. 488 </p> 489 490 <hr></hr> 491 492 <pre><a name="edge-multi-prop-const"></a> 493 template<typename MultiPassInputIterator, typename EdgePropertyIterator> 494 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t, 495 MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end, 496 EdgePropertyIterator ep_iter, 497 vertices_size_type numverts, 498 const GraphProperty& prop = GraphProperty()); 499 </pre> 500 <p class="indent"> 501 This constructor constructs a graph with <code>numverts</code> 502 vertices and the edges provided in the iterator range 503 <code>[edge_begin, edge_end)</code>. Its semantics are identical 504 to the <a href="#edge-const">edge range constructor</a>, except 505 that edge properties are also initialized. The type 506 <tt>EdgePropertyIterator</tt> must be a model of the <a 507 href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a> 508 concept whose <tt>value_type</tt> is convertible to 509 <tt>EdgeProperty</tt>. The iterator range <tt>[ep_iter, ep_ter + 510 m)</tt> will be used to initialize the properties on the edges 511 of the graph, where <tt>m</tt> is distance from 512 <tt>edge_begin</tt> to <tt>edge_end</tt>. Multiple passes will be made 513 over the edge and property ranges. 514 </p> 515 516 <hr></hr> 517 518 <pre><a name="edge-sorted-const"></a> 519 template<typename InputIterator> 520 compressed_sparse_row_graph(edges_are_sorted_t, 521 InputIterator edge_begin, InputIterator edge_end, 522 vertices_size_type numverts, 523 edges_size_type numedges = 0, 524 const GraphProperty& prop = GraphProperty()); 525 </pre> 526 527 <p class="indent"> 528 Constructs a graph with <code>numverts</code> vertices whose 529 edges are specified by the iterator range <code>[edge_begin, 530 edge_end)</code>. The argument of type <code>edges_are_sorted_t</code> is 531 a tag used to distinguish this constructor; the value 532 <code>edges_are_sorted</code> can be used to initialize this parameter. 533 The <tt>InputIterator</tt> must be a model of 534 <a 535 href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a> 536 whose <code>value_type</code> is an <code>std::pair</code> of 537 integer values. These integer values are the source and target 538 vertices for the edges, and must fall within the range <code>[0, 539 numverts)</code>. The edges in <code>[edge_begin, 540 edge_end)</code> must be sorted so that all edges originating 541 from vertex <i>i</i> precede any edges originating from all 542 vertices <i>j</i> where <i>j > i</i>. 543 </p> 544 545 <p class="indent"> 546 The value <code>numedges</code>, if provided, tells how many 547 edges are in the range <code>[edge_begin, edge_end)</code> and 548 will be used to preallocate data structures to save both memory 549 and time during construction. 550 </p> 551 552 <p class="indent"> 553 The value <code>prop</code> will be used to initialize the graph 554 property. 555 </p> 556 557 <hr></hr> 558 559 <pre><a name="edge-sorted-prop-const"></a> 560 template<typename InputIterator, typename EdgePropertyIterator> 561 compressed_sparse_row_graph(edges_are_sorted_t, 562 InputIterator edge_begin, InputIterator edge_end, 563 EdgePropertyIterator ep_iter, 564 vertices_size_type numverts, 565 edges_size_type numedges = 0, 566 const GraphProperty& prop = GraphProperty()); 567 </pre> 568 <p class="indent"> 569 This constructor constructs a graph with <code>numverts</code> 570 vertices and the edges provided in the iterator range 571 <code>[edge_begin, edge_end)</code>. Its semantics are identical 572 to the <a href="#edge-const">edge range constructor</a>, except 573 that edge properties are also initialized. The type 574 <tt>EdgePropertyIterator</tt> must be a model of the <a 575 href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a> 576 concept whose <tt>value_type</tt> is convertible to 577 <tt>EdgeProperty</tt>. The iterator range <tt>[ep_iter, ep_ter + 578 m)</tt> will be used to initialize the properties on the edges 579 of the graph, where <tt>m</tt> is distance from 580 <tt>edge_begin</tt> to <tt>edge_end</tt>. 581 </p> 582 583 <hr></hr> 584 585 <pre><a name="edge-inplace-const"></a> 586 template<typename InputIterator> 587 compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t, 588 std::vector<vertex_descriptor>& sources, 589 std::vector<vertex_descriptor>& targets, 590 vertices_size_type numverts, 591 const GraphProperty& prop = GraphProperty()); 592 </pre> 593 <p class="indent"> 594 This constructor constructs a graph with <code>numverts</code> vertices 595 and the edges provided in the two vectors <code>sources</code> and 596 <code>targets</code>. The two vectors are mutated in-place to sort them 597 by source vertex. They are returned with unspecified values, but do not 598 share storage with the constructed graph (and so are safe to destroy). 599 The parameter <code>prop</code>, if provided, is used to initialize the 600 graph property. 601 </p> 602 603 <hr></hr> 604 605 <pre><a name="edge-inplace-prop-const"></a> 606 template<typename InputIterator> 607 compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t, 608 std::vector<vertex_descriptor>& sources, 609 std::vector<vertex_descriptor>& targets, 610 std::vector<EdgeProperty>& edge_props, 611 vertices_size_type numverts, 612 const GraphProperty& prop = GraphProperty()); 613 </pre> 614 <p class="indent"> 615 This constructor constructs a graph with <code>numverts</code> vertices 616 and the edges provided in the two vectors <code>sources</code> and 617 <code>targets</code>. Edge properties are initialized from the vector 618 <code>edge_props</code>. The three vectors are mutated in-place to sort 619 them by source vertex. They are returned with unspecified values, but do 620 not share storage with the constructed graph (and so are safe to 621 destroy). The parameter <code>prop</code>, if provided, is used to 622 initialize the graph property. 623 </p> 624 625 <hr></hr> 626 627 <pre><a name="graph-const"></a> 628 template<typename Graph, typename VertexIndexMap> 629 compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi, 630 vertices_size_type numverts, 631 edges_size_type numedges); 632 633 template<typename Graph, typename VertexIndexMap> 634 compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi); 635 636 template<typename Graph> 637 explicit compressed_sparse_row_graph(const Graph& g); 638 </pre> 639 640 <p class="indent"> 641 Calls the <a href="#assign"><tt>assign</tt></a> function with 642 all of the arguments it is given. 643 </p> 644 645 <hr></hr> 646 647 <a name="mutators"></a><h3>Mutators</h3> 648 <pre><a name="assign"></a> 649 template<typename Graph, typename VertexIndexMap> 650 void assign(const Graph& g, const VertexIndexMap& vi, 651 vertices_size_type numverts, edges_size_type numedges); 652 653 template<typename Graph, typename VertexIndexMap> 654 void assign(const Graph& g, const VertexIndexMap& vi); 655 656 template<typename Graph> 657 void assign(const Graph& g); 658 </pre> 659 660 <p class="indent"> 661 Clears the CSR graph and builds a CSR graph in place from the 662 structure of another graph. The graph type <tt>Graph</tt> must 663 be a model of <a href="IncidenceGraph.html">IncidenceGraph</a>. 664 665 <br><b>Parameters</b> 666 667 <ul> 668 <li><tt>g</tt>: The incoming graph.</li> 669 670 <li><tt>vi</tt>: A map from vertices to indices. If not 671 provided, <tt>get(vertex_index, g)</tt> will be used.</li> 672 673 <li><tt>numverts</tt>: The number of vertices in the graph 674 <tt>g</tt>. If not provided, <tt>Graph</tt> must be a model of 675 <a href="VertexListGraph.html">VertexListGraph</a>.</li> 676 677 <li><tt>numedges</tt>: The number of edges in the graph 678 <tt>g</tt>. If not provided, <tt>Graph</tt> must be a model of 679 <a href="EdgeListGraph.html">EdgeListGraph</a>.</li> 680 </ul> 681 </p> 682 683 <hr></hr> 684 685 <a name="property-access"></a><h3>Property Access</h3> 686 687 <pre><a name="vertex-subscript"></a> 688 VertexProperty& operator[](vertex_descriptor v); 689 const VertexProperty& operator[](vertex_descriptor v) const; 690 </pre> 691 692 <p class="indent"> 693 Retrieves the property value associated with vertex 694 <tt>v</tt>. Only valid when <tt>VertexProperty</tt> is a class 695 type that is not <tt>no_property</tt>. 696 </p> 697 698 <hr></hr> 699 700 <pre><a name="edge-subscript"> 701 EdgeProperty& operator[](edge_descriptor v); 702 const EdgeProperty& operator[](edge_descriptor v) const; 703 </pre> 704 705 <p class="indent"> 706 Retrieves the property value associated with edge 707 <tt>v</tt>. Only valid when <tt>EdgeProperty</tt> is a class 708 type that is not <tt>no_property</tt>. 709 </p> 710 711 <hr></hr> 712 <a name="non-members"></a><h2>Non-member Functions</h2> 713 714 <a name="vertex-access"></a><h3>Vertex access</h3> 715 716 <pre><a name="vertex-lookup"></a> 717 vertex_descriptor vertex(vertices_size_type i, const compressed_sparse_row_graph&); 718 </pre> 719 <p class="indent"> 720 Retrieves the <i>i</i><sup>th</sup> vertex in the graph in 721 constant time. 722 </p> 723 724 <hr></hr> 725 726 <a name="edge-access"></a><h3>Edge access</h3> 727 728 <pre><a name="edge"></a> 729 std::pair<edge_descriptor, bool> 730 edge(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&); 731 </pre> 732 733 <p class="indent"> 734 If there exists an edge <i>(u, v)</i> in the graph, returns the 735 descriptor for that edge and <tt>true</tt>; otherwise, the 736 second value in the pair will be <tt>false</tt>. If multiple 737 edges exist from <tt>u</tt> to <tt>v</tt>, the first edge will 738 be returned; use <a href="IncidenceGraph.html"><tt>out_edges</tt></a> and a 739 conditional statement 740 to retrieve all edges to a given target. This function requires linear 741 time in the 742 number of edges outgoing from <tt>u</tt>. 743 </p> 744 745 <hr></hr> 746 747 <pre><a name="edge_from_index"></a> 748 edge_descriptor edge_from_index(edges_size_type i, const compressed_sparse_row_graph&); 749 </pre> 750 751 <p class="indent"> 752 Returns the <i>i</i><sup>th</sup> edge in the graph. This 753 operation requires logarithmic time in the number of vertices. 754 </p> 755 756 <hr></hr> 757 758 <h3><a name="property-map-accessors">Property Map Accessors</a></h3> 759 760 <pre><a name="get"></a> 761template<typename <a href="./PropertyTag.html">PropertyTag</a>> 762property_map<compressed_sparse_row_graph, PropertyTag>::type 763get(PropertyTag, compressed_sparse_row_graph& g) 764 765template<typename <a href="./PropertyTag.html">PropertyTag</a>> 766property_map<compressed_sparse_row_graph, Tag>::const_type 767get(PropertyTag, const compressed_sparse_row_graph& g) 768 </pre> 769 770 <p class="indent"> 771 Returns the property map object for the vertex property 772 specified by <TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must 773 be a member pointer to access one of the fields in 774 <tt>VertexProperty</tt> or <tt>EdgeProperty</tt>. 775 </p> 776 777 <hr></hr> 778 779 <pre><a name="get-x"></a> 780template<typename <a href="./PropertyTag.html">PropertyTag</a>, class X> 781typename property_traits<property_map<compressed_sparse_row_graph, PropertyTag>::const_type>::value_type 782get(PropertyTag, const compressed_sparse_row_graph& g, X x) 783 </pre> 784 785 <p class="indent"> 786 This returns the property value for <tt>x</tt>, where <tt>x</tt> 787 is either a vertex or edge descriptor. 788 </p> 789 790 <hr></hr> 791 792 <pre><a name="put-x"></a> 793template<typename <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value> 794void put(PropertyTag, const compressed_sparse_row_graph& g, X x, const Value& value); 795 </pre> 796 797 <p class="indent"> 798 This sets the property value for <tt>x</tt> to 799 <tt>value</tt>. <tt>x</tt> is either a vertex or edge 800 descriptor. <tt>Value</tt> must be convertible to <tt>typename 801 property_traits<property_map<compressed_sparse_row_graph, 802 PropertyTag>::type>::value_type</tt> 803 </p> 804 805 <hr></hr> 806 807 <pre><a name="get_property"></a> 808template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> 809typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type& 810get_property(compressed_sparse_row_graph& g, GraphPropertyTag); 811 812template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> 813typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type const & 814get_property(const compressed_sparse_row_graph& g, GraphPropertyTag); 815 </pre> 816 817 <p class="indent"> 818 Return the property specified by <tt>GraphPropertyTag</tt> that 819 is attached to the graph object <tt>g</tt>. 820 </p> 821 822 <hr></hr> 823 824 <pre><a name="set_property"></a> 825template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> 826void set_property(const compressed_sparse_row_graph& g, GraphPropertyTag, 827 const typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type& value); 828 </pre> 829 830 <p class="indent"> 831 Set the property specified by <tt>GraphPropertyTag</tt> that 832 is attached to the graph object <tt>g</tt>. 833 </p> 834 835 <hr></hr> 836 837 <h3><a name="incremental-construction-functions">Incremental construction functions</a></h3> 838 839 <pre><a name="add_edges"></a> 840template<typename InputIterator> 841void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g) 842 </pre> 843 844 <p class="indent"> 845 Add a range of edges (from <tt>first</tt> to <tt>last</tt>) to the graph. 846 The <tt>InputIterator</tt> must be a model of <a 847 href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a> 848 whose <code>value_type</code> is an <code>std::pair</code> of integer 849 values. These integer values are the source and target vertices of the 850 new edges. The edges do not need to be sorted. 851 </p> 852 853 <hr></hr> 854 855 <pre><a name="add_edges_prop"></a> 856template<typename InputIterator, typename EPIter> 857void add_edges(InputIterator first, InputIterator last, EPIter ep_first, EPIter ep_last, compressed_sparse_row_graph& g) 858 </pre> 859 860 <p class="indent"> 861 Add a range of edges (from <tt>first</tt> to <tt>last</tt>) with 862 corresponding edge properties (from <tt>ep_first</tt> to 863 <tt>ep_last</tt>) to the graph. The <tt>InputIterator</tt> and 864 <tt>EPIter</tt> must be models of <a 865 href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a>; 866 the <code>value_type</code> of <tt>InputIterator</tt> must be an 867 <code>std::pair</code> of integer values, and the <code>value_type</code> 868 of <tt>EPIter</tt> must be the edge property type of the graph. The 869 integer values produced by the <tt>InputIterator</tt> are the source and 870 target vertices of the new edges. The edges do not need to be sorted. 871 </p> 872 873 <hr></hr> 874 875 <pre><a name="add_edges_sorted"></a> 876template<typename BidirectionalIterator> 877void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph& g) 878 </pre> 879 880 <p class="indent"> 881 Add a range of edges (from <tt>first</tt> to <tt>last</tt>) to the graph. 882 The <tt>BidirectionalIterator</tt> must be a model of <a 883 href="http://www.boost.org/sgi/stl/BidirectionalIterator.html">BidirectionalIterator</a> 884 whose <code>value_type</code> is an <code>std::pair</code> of integer 885 values. These integer values are the source and target vertices of the 886 new edges. The edges must be sorted in increasing order by source vertex 887 index. 888 </p> 889 890 <hr></hr> 891 892 <pre><a name="add_edges_sorted_prop"></a> 893template<typename BidirectionalIterator, typename EPIter> 894void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, EPIter ep_iter, compressed_sparse_row_graph& g) 895 </pre> 896 897 <p class="indent"> 898 Add a range of edges (from <tt>first</tt> to <tt>last</tt>) to the graph. 899 The <tt>BidirectionalIterator</tt> and <tt>EPIter</tt> must be models of 900 <a 901 href="http://www.boost.org/sgi/stl/BidirectionalIterator.html">BidirectionalIterator</a>. 902 The <code>value_type</code> of the <tt>BidirectionalIterator</tt> must be 903 an <code>std::pair</code> of integer 904 values. These integer values are the source and target vertices of the 905 new edges. 906 The <code>value_type</code> of the <tt>EPIter</tt> must be the edge 907 property type of the graph. 908 The edges must be sorted in increasing order by source vertex 909 index. 910 </p> 911 912 <hr></hr> 913 <a name="example"></a><h2>Example</h2> 914 915 <br>[<a 916 href="../example/csr-example.cpp">libs/graph/example/csr-example.cpp</a>] 917 918 <p>We will use the <tt>compressed_sparse_row_graph</tt> graph 919 class to store a simple Web graph. In this web graph the vertices 920 represent web pages and the edges represent links from one web 921 page to another. With each web page we want to associate a URL, so 922 we initially create a <tt>WebPage</tt> class that stores the 923 URL. Then we can create our graph type by providing 924 <tt>WebPage</tt> as a parameter to the 925 <tt>compressed_sparse_row_graph</tt> class template.</p> 926 927 <pre> 928class WebPage 929{ 930 public: 931 std::string url; 932}; 933 934// ... 935 936typedef compressed_sparse_row_graph<directedS, WebPage> WebGraph; 937WebGraph g(&the_edges[0], &the_edges[0] + sizeof(the_edges)/sizeof(E), 6); 938 </pre> 939 940 <p>We can then set the properties on the vertices of the graph 941 using the <a href="bundles.html">bundled properties</a> syntax, 942 and display the edges for the user.</p> 943 944 <pre> 945// Set the URLs of each vertex 946int index = 0; 947BGL_FORALL_VERTICES(v, g, WebGraph) 948 g[v].url = urls[index++]; 949 950// Output each of the links 951std::cout << "The web graph:" << std::endl; 952BGL_FORALL_EDGES(e, g, WebGraph) 953 std::cout << " " << g[source(e, g)].url << " -> " << g[target(e, g)].url 954 << std::endl; 955 </pre> 956 957 <p>See the <a href="../example/csr-example.cpp">complete example 958 source</a> for other operations one can perform with a 959 <tt>compressed_sparse_row_graph</tt>.</p> 960<br> 961<HR> 962<TABLE> 963<TR valign=top> 964<TD nowrap>Copyright © 2005</TD><TD> 965<A HREF="http://www.boost.org/people/doug_gregor.html">Doug Gregor</A>, Indiana University (<script language="Javascript">address("cs.indiana.edu", "dgregor")</script>)<br> 966Jeremiah Willcock, Indiana University (<script language="Javascript">address("osl.iu.edu", "jewillco")</script>)<br> 967 <A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>, 968Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>) 969</TD></TR></TABLE> 970 </body> 971</html> 972
