123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971 |
- <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
- <html>
- <!--
- Copyright (c) 2005-2009 Trustees of Indiana University
-
- Distributed under 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)
- -->
- <head>
- <title>Compressed Sparse Row Graph</title>
- <STYLE TYPE="text/css">
- <!--
- .indent
- {
- padding-left: 50pt;
- padding-right: 50pt;
- }
- -->
- </STYLE>
- <script language="JavaScript" type="text/JavaScript">
- <!--
- function address(host, user) {
- var atchar = '@';
- var thingy = user+atchar+host;
- thingy = '<a hre' + 'f=' + "mai" + "lto:" + thingy + '>' + user+atchar+host + '</a>';
- document.write(thingy);
- }
- //-->
- </script>
- </head>
-
- <body>
- <IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86"></img>
- <h1>Compressed Sparse Row Graph</h1>
-
- <p>The class template <code>compressed_sparse_row_graph</code> is
- a graph class that uses the compact Compressed Sparse Row (CSR)
- format to store directed (and bidirectional) graphs. While CSR graphs have
- much less
- overhead than many other graph formats (e.g., <a
- href="adjacency_list.html"><code>adjacency_list</code></a>), they
- do not provide any mutability: one cannot add or remove vertices
- or edges from a CSR graph. Use this format in high-performance
- applications or for very large graphs that you do not need to
- change.</p>
- <p>The CSR format stores vertices and edges in separate arrays,
- with the indices into these arrays corresponding to the identifier
- for the vertex or edge, respectively. The edge array is sorted by
- the source of each edge, but contains only the targets for the
- edges. The vertex array stores offsets into the edge array,
- providing the offset of the first edge outgoing from each
- vertex. Iteration over the out-edges for the <i>i</i><sup>th</sup>
- vertex in the graph is achieved by
- visiting <tt>edge_array[vertex_array[i]]</tt>,
- <tt>edge_array[vertex_array[i]+1]</tt>,
- ..., <tt>edge_array[vertex_array[i+1]]</tt>. This format minimizes
- memory use to <i>O(n + m)</i>, where <i>n</i> and <i>m</i> are the
- number of vertices and edges, respectively. The constants
- multiplied by <i>n</i> and <i>m</i> are based on the size of the
- integers needed to represent indices into the edge and vertex
- arrays, respectively, which can be controlled using
- the <a href="#template-parms">template parameters</a>. The
- <tt>Directed</tt> template parameter controls whether one edge direction
- (the default) or both directions are stored. A directed CSR graph has
- <tt>Directed</tt> = <tt>directedS</tt> and a bidirectional CSR graph (with
- a limited set of constructors)
- has <tt>Directed</tt> = <tt>bidirectionalS</tt>.</p>
- <ul>
- <li><a href="#synopsis">Synopsis</a></li>
- <li><a href="#where">Where Defined</a></li>
- <li><a href="#models">Models</a></li>
- <li><a href="#template-parms">Template parameters</a></li>
- <li><a href="#properties">Properties</a></li>
- <li><a href="#member-functions">Member functions</a>
- <ul>
- <li><a href="#constructors">Constructors</a></li>
- <li><a href="#mutators">Mutators</a></li>
- <li><a href="#property-access">Property access</a></li>
- </ul></li>
- <li><a href="#non-members">Non-member functions</a>
- <ul>
- <li><a href="#vertex-access">Vertex access</a></li>
- <li><a href="#edge-access">Edge access</a></li>
- <li><a href="#property-map-accessors">Property map accessors</a></li>
- <li><a href="#incremental-construction-functions">Incremental construction functions</a></li>
- </ul></li>
- <li><a href="#example">Example</a></li>
- </ul>
- <a name="synopsis"></a><h2>Synopsis</h2>
- <pre>
- namespace boost {
- template<typename <a href="#Directed">Directed</a> = directedS, typename <a href="#VertexProperty">VertexProperty</a> = no_property,
- typename <a href="#EdgeProperty">EdgeProperty</a> = no_property, typename <a href="#GraphProperty">GraphProperty</a> = no_property,
- typename <a href="#Vertex">Vertex</a> = std::size_t, typename <a href="#EdgeIndex">EdgeIndex</a> = Vertex>
- class compressed_sparse_row_graph
- {
- public:
- <i>// <a href="#constructors">Graph constructors</a></i>
- <a href="#default-const">compressed_sparse_row_graph</a>();
- <i>// Unsorted edge list constructors </i>
- template<typename InputIterator>
- <a href="#edge-const">compressed_sparse_row_graph</a>(edges_are_unsorted_t,
- InputIterator edge_begin, InputIterator edge_end,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty());
- template<typename InputIterator, typename EdgePropertyIterator>
- <a href="#edge-prop-const">compressed_sparse_row_graph</a>(edges_are_unsorted_t,
- InputIterator edge_begin, InputIterator edge_end,
- EdgePropertyIterator ep_iter,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty());
- template<typename MultiPassInputIterator>
- <a href="#edge-multi-const">compressed_sparse_row_graph</a>(edges_are_unsorted_multi_pass_t,
- MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty());
- template<typename MultiPassInputIterator, typename EdgePropertyIterator>
- <a href="#edge-multi-prop-const">compressed_sparse_row_graph</a>(edges_are_unsorted_multi_pass_t,
- MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
- EdgePropertyIterator ep_iter,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty());
- <i>// New sorted edge list constructors <b>(directed only)</b></i>
- template<typename InputIterator>
- <a href="#edge-sorted-const">compressed_sparse_row_graph</a>(edges_are_sorted_t,
- InputIterator edge_begin, InputIterator edge_end,
- vertices_size_type numverts,
- edges_size_type numedges = 0,
- const GraphProperty& prop = GraphProperty());
- template<typename InputIterator, typename EdgePropertyIterator>
- <a href="#edge-sorted-prop-const">compressed_sparse_row_graph</a>(edges_are_sorted_t,
- InputIterator edge_begin, InputIterator edge_end,
- EdgePropertyIterator ep_iter,
- vertices_size_type numverts,
- edges_size_type numedges = 0,
- const GraphProperty& prop = GraphProperty());
- <i>// In-place unsorted edge list constructors <b>(directed only)</b></i>
- template<typename InputIterator>
- <a href="#edge-inplace-const">compressed_sparse_row_graph</a>(construct_inplace_from_sources_and_targets_t,
- std::vector<vertex_descriptor>& sources,
- std::vector<vertex_descriptor>& targets,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty());
- template<typename InputIterator>
- <a href="#edge-inplace-prop-const">compressed_sparse_row_graph</a>(construct_inplace_from_sources_and_targets_t,
- std::vector<vertex_descriptor>& sources,
- std::vector<vertex_descriptor>& targets,
- std::vector<EdgeProperty>& edge_props,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty());
- <i>// Miscellaneous constructors <b>(directed only)</b></i>
- template<typename Graph, typename VertexIndexMap>
- <a href="#graph-const">compressed_sparse_row_graph</a>(const Graph& g, const VertexIndexMap& vi,
- vertices_size_type numverts,
- edges_size_type numedges);
- template<typename Graph, typename VertexIndexMap>
- compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi);
- template<typename Graph>
- explicit <a href="#graph-const">compressed_sparse_row_graph</a>(const Graph& g);
- <i>// <a href="#mutators">Graph mutators <b>(directed only)</b></a></i>
- template<typename Graph, typename VertexIndexMap>
- void <a href="#assign">assign</a>(const Graph& g, const VertexIndexMap& vi,
- vertices_size_type numverts, edges_size_type numedges);
- template<typename Graph, typename VertexIndexMap>
- void <a href="#assign">assign</a>(const Graph& g, const VertexIndexMap& vi);
- template<typename Graph>
- void <a href="#assign">assign</a>(const Graph& g);
- <i>// <a href="#property-access">Property Access</a></i>
- VertexProperty& <a href="#vertex-subscript">operator[]</a>(vertex_descriptor v);
- const VertexProperty& <a href="#vertex-subscript">operator[]</a>(vertex_descriptor v) const;
- EdgeProperty& <a href="#edge-subscript">operator[]</a>(edge_descriptor v);
- const EdgeProperty& <a href="#edge-subscript">operator[]</a>(edge_descriptor v) const;
- };
- <i>// <a href="IncidenceGraph.html">Incidence Graph requirements</a></i>
- vertex_descriptor source(edge_descriptor, const compressed_sparse_row_graph&);
- vertex_descriptor target(edge_descriptor, const compressed_sparse_row_graph&);
- std::pair<out_edge_iterator, out_edge_iterator>
- out_edges(vertex_descriptor, const compressed_sparse_row_graph&);
- degree_size_type out_degree(vertex_descriptor v, const compressed_sparse_row_graph&);
- <i>// <a href="BidirectionalGraph.html">Bidirectional Graph requirements <b>(bidirectional only)</b></a></i>
- std::pair<in_edge_iterator, in_edge_iterator>
- in_edges(vertex_descriptor, const compressed_sparse_row_graph&);
- degree_size_type in_degree(vertex_descriptor v, const compressed_sparse_row_graph&);
- <i>// <a href="AdjacencyGraph.html">Adjacency Graph requirements</a></i>
- std::pair<adjacency_iterator, adjacency_iterator>
- adjacent_vertices(vertex_descriptor, const compressed_sparse_row_graph&);
- <i>// <a href="VertexListGraph.html">Vertex List Graph requirements</a></i>
- std::pair<vertex_iterator, vertex_iterator> vertices(const compressed_sparse_row_graph&);
- vertices_size_type num_vertices(const compressed_sparse_row_graph&);
- <i>// <a href="EdgeListGraph.html">Edge List Graph requirements</a></i>
- std::pair<edge_iterator, edge_iterator> edges(const compressed_sparse_row_graph&);
- edges_size_type num_edges(const compressed_sparse_row_graph&);
- <i>// <a href="#vertex-access">Vertex access</a></i>
- vertex_descriptor <a href="#vertex-lookup">vertex</a>(vertices_size_type i, const compressed_sparse_row_graph&);
- <i>// <a href="#edge-access">Edge access</a></i>
- std::pair<edge_descriptor, bool>
- <a href="#edge">edge</a>(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&);
- edge_descriptor <a href="#edge_from_index">edge_from_index</a>(edges_size_type i, const compressed_sparse_row_graph&);
- <i>// <a href="#property-map-accessors">Property map accessors</a></i>
- template<typename <a href="./PropertyTag.html">PropertyTag</a>>
- property_map<compressed_sparse_row_graph, PropertyTag>::type
- <a href="#get">get</a>(PropertyTag, compressed_sparse_row_graph& g)
- template<typename <a href="./PropertyTag.html">PropertyTag</a>>
- property_map<compressed_sparse_row_graph, Tag>::const_type
- <a href="#get">get</a>(PropertyTag, const compressed_sparse_row_graph& g)
- template<typename <a href="./PropertyTag.html">PropertyTag</a>, class X>
- typename property_traits<property_map<compressed_sparse_row_graph, PropertyTag>::const_type>::value_type
- <a href="#get-x">get</a>(PropertyTag, const compressed_sparse_row_graph& g, X x)
- template<typename <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value>
- void <a href="#put-x">put</a>(PropertyTag, const compressed_sparse_row_graph& g, X x, const Value& value);
- template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>>
- typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type&
- <a href="#get_property">get_property</a>(compressed_sparse_row_graph& g, GraphPropertyTag);
- template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>>
- typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type const &
- <a href="#get_property">get_property</a>(const compressed_sparse_row_graph& g, GraphPropertyTag);
- template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>>
- void <a href="#set_property">set_property</a>(const compressed_sparse_row_graph& g, GraphPropertyTag,
- const typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type& value);
- <i>// <a href="#incremental-construction-functions">Incremental construction functions</a></i>
- <b>(directed only)</b>
- template<typename InputIterator, typename Graph>
- void <a href="#add_edges">add_edges</a>(InputIterator first, InputIterator last, compressed_sparse_row_graph& g);
- <b>(directed only)</b>
- template<typename InputIterator, typename EPIter, typename Graph>
- void <a href="#add_edges_prop">add_edges</a>(InputIterator first, InputIterator last, EPIter ep_first, EPIter ep_last, compressed_sparse_row_graph& g);
- <b>(directed only)</b>
- template<typename BidirectionalIterator, typename Graph>
- void <a href="#add_edges_sorted">add_edges_sorted</a>(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph& g);
- <b>(directed only)</b>
- template<typename BidirectionalIterator, typename EPIter, typename Graph>
- void <a href="#add_edges_sorted_prop">add_edges_sorted</a>(BidirectionalIterator first, BidirectionalIterator last, EPIter ep_iter, compressed_sparse_row_graph& g);
- } <i>// end namespace boost</i>
- </pre>
- <a name="where"></a><h2>Where Defined</h2>
- <p><code><<a href="../../../boost/graph/compressed_sparse_row_graph.hpp">boost/graph/compressed_sparse_row_graph.hpp</a>></code></p>
- <a name="models"></a><h2>Models</h2>
-
- <p>The <tt>compressed_sparse_row_graph</tt> class template models
- (i.e., implements the requirements of) many of the
- BGL <a href="graph_concepts.html">graph concepts</a>, allowing it
- to be used with most of the BGL algorithms. In particular, it
- models the following specific graph concepts:</p>
- <ul>
- <li><a href="Graph.html">Graph</a></li>
- <li><a href="IncidenceGraph.html">IncidenceGraph</a></li>
- <li><a href="AdjacencyGraph.html">AdjacencyGraph</a></li>
- <li><a href="VertexListGraph.html">VertexListGraph</a></li>
- <li><a href="EdgeListGraph.html">EdgeListGraph</a></li>
- <li><a href="PropertyGraph.html">PropertyGraph</a></li>
- </ul>
- <a name="template-parms"></a><h2>Template Parameters</h2>
- <p>The <tt>compressed_sparse_row_graph</tt> class has several
- template parameters that can customize the layout in memory and
- what properties are attached to the graph itself. All
- parameters have defaults, so users interested only in the
- structure of a graph can use the
- type <tt>compressed_sparse_row_graph<></tt> and ignore
- the parameters.</p>
- <b>Parameters</b>
- <br>
- <br>
- <a name="Directed"></a><code>Directed</code>
- <blockquote>
- A selector that determines whether the graph will be directed,
- bidirectional or undirected. At this time, the CSR graph type
- only supports directed and bidirectional graphs, so this value must
- be either <code>boost::directedS</code> or
- <code>boost::bidirectionalS</code>.<br>
- <b>Default</b>: <code>boost::directedS</code>
- </blockquote>
- <a name="VertexProperty"></a><code>VertexProperty</code>
- <blockquote>
- A class type that will be
- attached to each vertex in the graph. If this value
- is <code>void</code>, no properties will be attached to
- the vertices of the graph.<br>
- <b>Default</b>: <code>void</code>
- </blockquote>
- <a name="EdgeProperty"></a><code>EdgeProperty</code>
- <blockquote>
- A class type that will be attached to each edge in the graph. If
- this value is <code>void</code>, no properties will be
- attached to the edges of the graph.<br>
- <b>Default</b>: <code>void</code>
- </blockquote>
- <a name="GraphProperty"></a><code>GraphProperty</code>
- <blockquote>
- A nested set
- of <code>property</code> templates that describe the
- properties of the graph itself. If this value
- is <code>no_property</code>, no properties will be attached to
- the graph.<br>
- <b>Default</b>: <code>no_property</code>
- </blockquote>
- <a name="Vertex"></a><code>Vertex</code>
- <blockquote>
- An unsigned integral type that will be
- used as both the index into the array of vertices and as the
- vertex descriptor itself. Larger types permit the CSR graph to
- store more vertices; smaller types reduce the storage required
- per vertex.<br>
- <b>Default</b>: <code>std::size_t</code>
- </blockquote>
- <a name="EdgeIndex"></a><code>EdgeIndex</code>
- <blockquote>
- An unsigned integral type that will be used as the index into
- the array of edges. As with the <code>Vertex</code> parameter,
- larger types permit more edges whereas smaller types reduce
- the amount of storage needed per
- edge. The <code>EdgeIndex</code> type shall not be smaller
- than the <code>Vertex</code> type, but it may be larger. For
- instance, <code>Vertex</code> may be a 16-bit integer
- (allowing 32,767 vertices in the graph)
- whereas <code>EdgeIndex</code> could then be a 32-bit integer
- to allow a complete graph to be stored in the CSR format.<br>
- <b>Default</b>: <code>Vertex</code>
- </blockquote>
- <a name="properties"></a><h2>Interior Properties</h2>
- <p> The <tt>compressed_sparse_row_graph</tt> allows properties to
- be attached to its vertices, edges, or to the graph itself by way
- of its <a href="#template-parms">template parameters</a>. These
- properties may be accessed via
- the <a href="#property-access">member</a>
- and <a href="#property-map-accessors">non-member</a> property
- access functions, using the <a href="bundles.html">bundled
- properties</a> scheme.</p>
- <p>The CSR graph provides two kinds of built-in
- properties: <tt>vertex_index</tt>, which maps from vertices to
- values in <tt>[0, n)</tt> and <tt>edge_index</tt>, which maps
- from edges to values in <tt>[0, m)</tt>, where <tt>n</tt>
- and <tt>m</tt> are the number of vertices and edges in the graph,
- respectively. </p>
- <a name="member-functions"></a><h2>Member Functions</h2>
- <a name="constructors"></a><h3>Constructors</h3>
- <pre><a name="default-const"></a>
- compressed_sparse_row_graph();
- </pre>
- <p class="indent">Constructs a graph with no vertices or edges.</p>
- <hr></hr>
- <pre><a name="edge-const"></a>
- template<typename InputIterator>
- compressed_sparse_row_graph(edges_are_unsorted_t,
- InputIterator edge_begin, InputIterator edge_end,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty());
- </pre>
- <p class="indent">
- Constructs a graph with <code>numverts</code> vertices whose
- edges are specified by the iterator range <code>[edge_begin,
- edge_end)</code>. The <tt>InputIterator</tt> must be a model of
- <a
- href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a>
- whose <code>value_type</code> is an <code>std::pair</code> of
- integer values. These integer values are the source and target
- vertices for the edges, and must fall within the range <code>[0,
- numverts)</code>. The edges in <code>[edge_begin,
- edge_end)</code> do not need to be sorted. This constructor uses extra
- memory to save the edge information before adding it to the graph,
- avoiding the requirement for the iterator to have multi-pass capability.
- </p>
- <p class="indent">
- The value <code>prop</code> will be used to initialize the graph
- property.
- </p>
- <hr></hr>
- <pre><a name="edge-prop-const"></a>
- template<typename InputIterator, typename EdgePropertyIterator>
- compressed_sparse_row_graph(edges_are_unsorted_t,
- InputIterator edge_begin, InputIterator edge_end,
- EdgePropertyIterator ep_iter,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty());
- </pre>
- <p class="indent">
- This constructor constructs a graph with <code>numverts</code>
- vertices and the edges provided in the iterator range
- <code>[edge_begin, edge_end)</code>. Its semantics are identical
- to the <a href="#edge-const">edge range constructor</a>, except
- that edge properties are also initialized. The type
- <tt>EdgePropertyIterator</tt> must be a model of the <a
- href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a>
- concept whose <tt>value_type</tt> is convertible to
- <tt>EdgeProperty</tt>. The iterator range <tt>[ep_iter, ep_ter +
- m)</tt> will be used to initialize the properties on the edges
- of the graph, where <tt>m</tt> is distance from
- <tt>edge_begin</tt> to <tt>edge_end</tt>. This constructor uses extra
- memory to save the edge information before adding it to the graph,
- avoiding the requirement for the iterator to have multi-pass capability.
- </p>
- <hr></hr>
- <pre><a name="edge-multi-const"></a>
- template<typename MultiPassInputIterator>
- compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
- MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty());
- </pre>
- <p class="indent">
- Constructs a graph with <code>numverts</code> vertices whose
- edges are specified by the iterator range <code>[edge_begin,
- edge_end)</code>. The <tt>MultiPassInputIterator</tt> must be a model of
- <a
- href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>
- whose <code>value_type</code> is an <code>std::pair</code> of
- integer values. These integer values are the source and target
- vertices for the edges, and must fall within the range <code>[0,
- numverts)</code>. The edges in <code>[edge_begin,
- edge_end)</code> do not need to be sorted. Multiple passes will be made
- over the edge range.
- </p>
- <p class="indent">
- The value <code>prop</code> will be used to initialize the graph
- property.
- </p>
- <hr></hr>
- <pre><a name="edge-multi-prop-const"></a>
- template<typename MultiPassInputIterator, typename EdgePropertyIterator>
- compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
- MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
- EdgePropertyIterator ep_iter,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty());
- </pre>
- <p class="indent">
- This constructor constructs a graph with <code>numverts</code>
- vertices and the edges provided in the iterator range
- <code>[edge_begin, edge_end)</code>. Its semantics are identical
- to the <a href="#edge-const">edge range constructor</a>, except
- that edge properties are also initialized. The type
- <tt>EdgePropertyIterator</tt> must be a model of the <a
- href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>
- concept whose <tt>value_type</tt> is convertible to
- <tt>EdgeProperty</tt>. The iterator range <tt>[ep_iter, ep_ter +
- m)</tt> will be used to initialize the properties on the edges
- of the graph, where <tt>m</tt> is distance from
- <tt>edge_begin</tt> to <tt>edge_end</tt>. Multiple passes will be made
- over the edge and property ranges.
- </p>
- <hr></hr>
- <pre><a name="edge-sorted-const"></a>
- template<typename InputIterator>
- compressed_sparse_row_graph(edges_are_sorted_t,
- InputIterator edge_begin, InputIterator edge_end,
- vertices_size_type numverts,
- edges_size_type numedges = 0,
- const GraphProperty& prop = GraphProperty());
- </pre>
- <p class="indent">
- Constructs a graph with <code>numverts</code> vertices whose
- edges are specified by the iterator range <code>[edge_begin,
- edge_end)</code>. The argument of type <code>edges_are_sorted_t</code> is
- a tag used to distinguish this constructor; the value
- <code>edges_are_sorted</code> can be used to initialize this parameter.
- The <tt>InputIterator</tt> must be a model of
- <a
- href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a>
- whose <code>value_type</code> is an <code>std::pair</code> of
- integer values. These integer values are the source and target
- vertices for the edges, and must fall within the range <code>[0,
- numverts)</code>. The edges in <code>[edge_begin,
- edge_end)</code> must be sorted so that all edges originating
- from vertex <i>i</i> precede any edges originating from all
- vertices <i>j</i> where <i>j > i</i>.
- </p>
- <p class="indent">
- The value <code>numedges</code>, if provided, tells how many
- edges are in the range <code>[edge_begin, edge_end)</code> and
- will be used to preallocate data structures to save both memory
- and time during construction.
- </p>
- <p class="indent">
- The value <code>prop</code> will be used to initialize the graph
- property.
- </p>
- <hr></hr>
- <pre><a name="edge-sorted-prop-const"></a>
- template<typename InputIterator, typename EdgePropertyIterator>
- compressed_sparse_row_graph(edges_are_sorted_t,
- InputIterator edge_begin, InputIterator edge_end,
- EdgePropertyIterator ep_iter,
- vertices_size_type numverts,
- edges_size_type numedges = 0,
- const GraphProperty& prop = GraphProperty());
- </pre>
- <p class="indent">
- This constructor constructs a graph with <code>numverts</code>
- vertices and the edges provided in the iterator range
- <code>[edge_begin, edge_end)</code>. Its semantics are identical
- to the <a href="#edge-const">edge range constructor</a>, except
- that edge properties are also initialized. The type
- <tt>EdgePropertyIterator</tt> must be a model of the <a
- href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a>
- concept whose <tt>value_type</tt> is convertible to
- <tt>EdgeProperty</tt>. The iterator range <tt>[ep_iter, ep_ter +
- m)</tt> will be used to initialize the properties on the edges
- of the graph, where <tt>m</tt> is distance from
- <tt>edge_begin</tt> to <tt>edge_end</tt>.
- </p>
- <hr></hr>
- <pre><a name="edge-inplace-const"></a>
- template<typename InputIterator>
- compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
- std::vector<vertex_descriptor>& sources,
- std::vector<vertex_descriptor>& targets,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty());
- </pre>
- <p class="indent">
- This constructor constructs a graph with <code>numverts</code> vertices
- and the edges provided in the two vectors <code>sources</code> and
- <code>targets</code>. The two vectors are mutated in-place to sort them
- by source vertex. They are returned with unspecified values, but do not
- share storage with the constructed graph (and so are safe to destroy).
- The parameter <code>prop</code>, if provided, is used to initialize the
- graph property.
- </p>
- <hr></hr>
- <pre><a name="edge-inplace-prop-const"></a>
- template<typename InputIterator>
- compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
- std::vector<vertex_descriptor>& sources,
- std::vector<vertex_descriptor>& targets,
- std::vector<EdgeProperty>& edge_props,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty());
- </pre>
- <p class="indent">
- This constructor constructs a graph with <code>numverts</code> vertices
- and the edges provided in the two vectors <code>sources</code> and
- <code>targets</code>. Edge properties are initialized from the vector
- <code>edge_props</code>. The three vectors are mutated in-place to sort
- them by source vertex. They are returned with unspecified values, but do
- not share storage with the constructed graph (and so are safe to
- destroy). The parameter <code>prop</code>, if provided, is used to
- initialize the graph property.
- </p>
- <hr></hr>
- <pre><a name="graph-const"></a>
- template<typename Graph, typename VertexIndexMap>
- compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi,
- vertices_size_type numverts,
- edges_size_type numedges);
- template<typename Graph, typename VertexIndexMap>
- compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi);
- template<typename Graph>
- explicit compressed_sparse_row_graph(const Graph& g);
- </pre>
- <p class="indent">
- Calls the <a href="#assign"><tt>assign</tt></a> function with
- all of the arguments it is given.
- </p>
- <hr></hr>
- <a name="mutators"></a><h3>Mutators</h3>
- <pre><a name="assign"></a>
- template<typename Graph, typename VertexIndexMap>
- void assign(const Graph& g, const VertexIndexMap& vi,
- vertices_size_type numverts, edges_size_type numedges);
- template<typename Graph, typename VertexIndexMap>
- void assign(const Graph& g, const VertexIndexMap& vi);
- template<typename Graph>
- void assign(const Graph& g);
- </pre>
- <p class="indent">
- Clears the CSR graph and builds a CSR graph in place from the
- structure of another graph. The graph type <tt>Graph</tt> must
- be a model of <a href="IncidenceGraph.html">IncidenceGraph</a>.
- <br><b>Parameters</b>
- <ul>
- <li><tt>g</tt>: The incoming graph.</li>
-
- <li><tt>vi</tt>: A map from vertices to indices. If not
- provided, <tt>get(vertex_index, g)</tt> will be used.</li>
-
- <li><tt>numverts</tt>: The number of vertices in the graph
- <tt>g</tt>. If not provided, <tt>Graph</tt> must be a model of
- <a href="VertexListGraph.html">VertexListGraph</a>.</li>
-
- <li><tt>numedges</tt>: The number of edges in the graph
- <tt>g</tt>. If not provided, <tt>Graph</tt> must be a model of
- <a href="EdgeListGraph.html">EdgeListGraph</a>.</li>
- </ul>
- </p>
- <hr></hr>
- <a name="property-access"></a><h3>Property Access</h3>
- <pre><a name="vertex-subscript"></a>
- VertexProperty& operator[](vertex_descriptor v);
- const VertexProperty& operator[](vertex_descriptor v) const;
- </pre>
- <p class="indent">
- Retrieves the property value associated with vertex
- <tt>v</tt>. Only valid when <tt>VertexProperty</tt> is a class
- type that is not <tt>no_property</tt>.
- </p>
- <hr></hr>
- <pre><a name="edge-subscript">
- EdgeProperty& operator[](edge_descriptor v);
- const EdgeProperty& operator[](edge_descriptor v) const;
- </pre>
- <p class="indent">
- Retrieves the property value associated with edge
- <tt>v</tt>. Only valid when <tt>EdgeProperty</tt> is a class
- type that is not <tt>no_property</tt>.
- </p>
- <hr></hr>
- <a name="non-members"></a><h2>Non-member Functions</h2>
- <a name="vertex-access"></a><h3>Vertex access</h3>
- <pre><a name="vertex-lookup"></a>
- vertex_descriptor vertex(vertices_size_type i, const compressed_sparse_row_graph&);
- </pre>
- <p class="indent">
- Retrieves the <i>i</i><sup>th</sup> vertex in the graph in
- constant time.
- </p>
- <hr></hr>
- <a name="edge-access"></a><h3>Edge access</h3>
- <pre><a name="edge"></a>
- std::pair<edge_descriptor, bool>
- edge(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&);
- </pre>
- <p class="indent">
- If there exists an edge <i>(u, v)</i> in the graph, returns the
- descriptor for that edge and <tt>true</tt>; otherwise, the
- second value in the pair will be <tt>false</tt>. If multiple
- edges exist from <tt>u</tt> to <tt>v</tt>, the first edge will
- be returned; use <a href="IncidenceGraph.html"><tt>out_edges</tt></a> and a
- conditional statement
- to retrieve all edges to a given target. This function requires linear
- time in the
- number of edges outgoing from <tt>u</tt>.
- </p>
- <hr></hr>
- <pre><a name="edge_from_index"></a>
- edge_descriptor edge_from_index(edges_size_type i, const compressed_sparse_row_graph&);
- </pre>
- <p class="indent">
- Returns the <i>i</i><sup>th</sup> edge in the graph. This
- operation requires logarithmic time in the number of vertices.
- </p>
- <hr></hr>
- <h3><a name="property-map-accessors">Property Map Accessors</a></h3>
- <pre><a name="get"></a>
- template<typename <a href="./PropertyTag.html">PropertyTag</a>>
- property_map<compressed_sparse_row_graph, PropertyTag>::type
- get(PropertyTag, compressed_sparse_row_graph& g)
- template<typename <a href="./PropertyTag.html">PropertyTag</a>>
- property_map<compressed_sparse_row_graph, Tag>::const_type
- get(PropertyTag, const compressed_sparse_row_graph& g)
- </pre>
-
- <p class="indent">
- Returns the property map object for the vertex property
- specified by <TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must
- be a member pointer to access one of the fields in
- <tt>VertexProperty</tt> or <tt>EdgeProperty</tt>.
- </p>
- <hr></hr>
- <pre><a name="get-x"></a>
- template<typename <a href="./PropertyTag.html">PropertyTag</a>, class X>
- typename property_traits<property_map<compressed_sparse_row_graph, PropertyTag>::const_type>::value_type
- get(PropertyTag, const compressed_sparse_row_graph& g, X x)
- </pre>
- <p class="indent">
- This returns the property value for <tt>x</tt>, where <tt>x</tt>
- is either a vertex or edge descriptor.
- </p>
- <hr></hr>
- <pre><a name="put-x"></a>
- template<typename <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value>
- void put(PropertyTag, const compressed_sparse_row_graph& g, X x, const Value& value);
- </pre>
- <p class="indent">
- This sets the property value for <tt>x</tt> to
- <tt>value</tt>. <tt>x</tt> is either a vertex or edge
- descriptor. <tt>Value</tt> must be convertible to <tt>typename
- property_traits<property_map<compressed_sparse_row_graph,
- PropertyTag>::type>::value_type</tt>
- </p>
- <hr></hr>
- <pre><a name="get_property"></a>
- template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>>
- typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type&
- get_property(compressed_sparse_row_graph& g, GraphPropertyTag);
- template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>>
- typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type const &
- get_property(const compressed_sparse_row_graph& g, GraphPropertyTag);
- </pre>
- <p class="indent">
- Return the property specified by <tt>GraphPropertyTag</tt> that
- is attached to the graph object <tt>g</tt>.
- </p>
- <hr></hr>
- <pre><a name="set_property"></a>
- template<typename <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>>
- void set_property(const compressed_sparse_row_graph& g, GraphPropertyTag,
- const typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type& value);
- </pre>
- <p class="indent">
- Set the property specified by <tt>GraphPropertyTag</tt> that
- is attached to the graph object <tt>g</tt>.
- </p>
- <hr></hr>
- <h3><a name="incremental-construction-functions">Incremental construction functions</a></h3>
- <pre><a name="add_edges"></a>
- template<typename InputIterator>
- void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g)
- </pre>
-
- <p class="indent">
- Add a range of edges (from <tt>first</tt> to <tt>last</tt>) to the graph.
- The <tt>InputIterator</tt> must be a model of <a
- href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a>
- whose <code>value_type</code> is an <code>std::pair</code> of integer
- values. These integer values are the source and target vertices of the
- new edges. The edges do not need to be sorted.
- </p>
- <hr></hr>
- <pre><a name="add_edges_prop"></a>
- template<typename InputIterator, typename EPIter>
- void add_edges(InputIterator first, InputIterator last, EPIter ep_first, EPIter ep_last, compressed_sparse_row_graph& g)
- </pre>
-
- <p class="indent">
- Add a range of edges (from <tt>first</tt> to <tt>last</tt>) with
- corresponding edge properties (from <tt>ep_first</tt> to
- <tt>ep_last</tt>) to the graph. The <tt>InputIterator</tt> and
- <tt>EPIter</tt> must be models of <a
- href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a>;
- the <code>value_type</code> of <tt>InputIterator</tt> must be an
- <code>std::pair</code> of integer values, and the <code>value_type</code>
- of <tt>EPIter</tt> must be the edge property type of the graph. The
- integer values produced by the <tt>InputIterator</tt> are the source and
- target vertices of the new edges. The edges do not need to be sorted.
- </p>
- <hr></hr>
- <pre><a name="add_edges_sorted"></a>
- template<typename BidirectionalIterator>
- void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph& g)
- </pre>
-
- <p class="indent">
- Add a range of edges (from <tt>first</tt> to <tt>last</tt>) to the graph.
- The <tt>BidirectionalIterator</tt> must be a model of <a
- href="http://www.boost.org/sgi/stl/BidirectionalIterator.html">BidirectionalIterator</a>
- whose <code>value_type</code> is an <code>std::pair</code> of integer
- values. These integer values are the source and target vertices of the
- new edges. The edges must be sorted in increasing order by source vertex
- index.
- </p>
- <hr></hr>
- <pre><a name="add_edges_sorted_prop"></a>
- template<typename BidirectionalIterator, typename EPIter>
- void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, EPIter ep_iter, compressed_sparse_row_graph& g)
- </pre>
-
- <p class="indent">
- Add a range of edges (from <tt>first</tt> to <tt>last</tt>) to the graph.
- The <tt>BidirectionalIterator</tt> and <tt>EPIter</tt> must be models of
- <a
- href="http://www.boost.org/sgi/stl/BidirectionalIterator.html">BidirectionalIterator</a>.
- The <code>value_type</code> of the <tt>BidirectionalIterator</tt> must be
- an <code>std::pair</code> of integer
- values. These integer values are the source and target vertices of the
- new edges.
- The <code>value_type</code> of the <tt>EPIter</tt> must be the edge
- property type of the graph.
- The edges must be sorted in increasing order by source vertex
- index.
- </p>
- <hr></hr>
- <a name="example"></a><h2>Example</h2>
- <br>[<a
- href="../example/csr-example.cpp">libs/graph/example/csr-example.cpp</a>]
- <p>We will use the <tt>compressed_sparse_row_graph</tt> graph
- class to store a simple Web graph. In this web graph the vertices
- represent web pages and the edges represent links from one web
- page to another. With each web page we want to associate a URL, so
- we initially create a <tt>WebPage</tt> class that stores the
- URL. Then we can create our graph type by providing
- <tt>WebPage</tt> as a parameter to the
- <tt>compressed_sparse_row_graph</tt> class template.</p>
- <pre>
- class WebPage
- {
- public:
- std::string url;
- };
- // ...
- typedef compressed_sparse_row_graph<directedS, WebPage> WebGraph;
- WebGraph g(&the_edges[0], &the_edges[0] + sizeof(the_edges)/sizeof(E), 6);
- </pre>
- <p>We can then set the properties on the vertices of the graph
- using the <a href="bundles.html">bundled properties</a> syntax,
- and display the edges for the user.</p>
- <pre>
- // Set the URLs of each vertex
- int index = 0;
- BGL_FORALL_VERTICES(v, g, WebGraph)
- g[v].url = urls[index++];
- // Output each of the links
- std::cout << "The web graph:" << std::endl;
- BGL_FORALL_EDGES(e, g, WebGraph)
- std::cout << " " << g[source(e, g)].url << " -> " << g[target(e, g)].url
- << std::endl;
- </pre>
- <p>See the <a href="../example/csr-example.cpp">complete example
- source</a> for other operations one can perform with a
- <tt>compressed_sparse_row_graph</tt>.</p>
- <br>
- <HR>
- <TABLE>
- <TR valign=top>
- <TD nowrap>Copyright © 2005</TD><TD>
- <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>
- Jeremiah Willcock, Indiana University (<script language="Javascript">address("osl.iu.edu", "jewillco")</script>)<br>
- <A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>,
- Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
- </TD></TR></TABLE>
- </body>
- </html>
|