Date view Thread view Subject view Author view

Subject: [Boost-commit] svn:boost r52275 - in trunk: boost/graph libs/graph/doc libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-04-08 20:50:24

Author: jewillco
Date: 2009-04-08 20:50:23 EDT (Wed, 08 Apr 2009)
New Revision: 52275
URL: http://svn.boost.org/trac/boost/changeset/52275

Log:
Added construction of CSR graph from an unsorted list of edges; removed property that targets of out-edges of a single vertex are sorted; removed edge and edge_range functions because they are not supportable under that model; changed tests and docs accordingly
Text files modified:
   trunk/boost/graph/compressed_sparse_row_graph.hpp | 130
   trunk/libs/graph/doc/compressed_sparse_row.html | 4021 ++++++++++++++++++++++++++++++++++++++-
   trunk/libs/graph/test/csr_graph_test.cpp | 49
   3 files changed, 4022 insertions(+), 178 deletions(-)

Modified: trunk/boost/graph/compressed_sparse_row_graph.hpp
==============================================================================
--- trunk/boost/graph/compressed_sparse_row_graph.hpp (original)
+++ trunk/boost/graph/compressed_sparse_row_graph.hpp 2009-04-08 20:50:23 EDT (Wed, 08 Apr 2009)
@@ -40,6 +40,13 @@
 // sparse row graph. This is an internal detail of the BGL.
 struct csr_graph_tag;
 
+// A type (edges_are_sorted_t) and a value (edges_are_sorted) used to indicate
+// that the edge list passed into the CSR graph is already sorted by source
+// vertex.
+struct edges_are_sorted_internal {};
+inline void edges_are_sorted(edges_are_sorted_internal) {}
+typedef void (*edges_are_sorted_t)(edges_are_sorted_internal);
+
 /****************************************************************************
  * Local helper macros to reduce typing and clutter later on. *
  ****************************************************************************/
@@ -167,9 +174,84 @@
       m_rowstart[v] = 0;
   }
 
+ // From number of vertices and unsorted list of edges
+ template <typename MultiPassInputIterator>
+ compressed_sparse_row_graph(MultiPassInputIterator edge_begin,
+ MultiPassInputIterator edge_end,
+ vertices_size_type numverts,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
+ m_column(0), m_property(prop), m_last_source(numverts)
+ {
+ // Put the degree of each vertex v into m_rowstart[v + 1]
+ for (MultiPassInputIterator i = edge_begin; i != edge_end; ++i)
+ ++m_rowstart[i->first + 1];
+
+ // Compute the partial sum of the degrees to get the actual values of
+ // m_rowstart
+ EdgeIndex start_of_this_row = 0;
+ m_rowstart[0] = start_of_this_row;
+ for (vertices_size_type i = 1; i <= numverts; ++i) {
+ start_of_this_row += m_rowstart[i];
+ m_rowstart[i] = start_of_this_row;
+ }
+ m_column.resize(m_rowstart.back());
+
+ // Bucket sort the edges by their source vertices, putting the targets into
+ // m_column. The index current_insert_positions[v] contains the next
+ // location to insert out edges for vertex v.
+ std::vector<EdgeIndex>
+ current_insert_positions(m_rowstart.begin(), m_rowstart.begin() + numverts);
+ for (; edge_begin != edge_end; ++edge_begin)
+ m_column[current_insert_positions[edge_begin->first]++] = edge_begin->second;
+
+ // Default-construct properties for edges
+ inherited_edge_properties::resize(m_column.size());
+ }
+
+ // From number of vertices and unsorted list of edges, plus edge properties
+ template <typename MultiPassInputIterator, typename EdgePropertyIterator>
+ compressed_sparse_row_graph(MultiPassInputIterator edge_begin,
+ MultiPassInputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
+ m_column(0), m_property(prop), m_last_source(numverts)
+ {
+ // Put the degree of each vertex v into m_rowstart[v + 1]
+ for (MultiPassInputIterator i = edge_begin; i != edge_end; ++i)
+ ++m_rowstart[i->first + 1];
+
+ // Compute the partial sum of the degrees to get the actual values of
+ // m_rowstart
+ EdgeIndex start_of_this_row = 0;
+ m_rowstart[0] = start_of_this_row;
+ for (vertices_size_type i = 1; i <= numverts; ++i) {
+ start_of_this_row += m_rowstart[i];
+ m_rowstart[i] = start_of_this_row;
+ }
+ m_column.resize(m_rowstart.back());
+ inherited_edge_properties::resize(m_rowstart.back());
+
+ // Bucket sort the edges by their source vertices, putting the targets into
+ // m_column. The index current_insert_positions[v] contains the next
+ // location to insert out edges for vertex v.
+ std::vector<EdgeIndex>
+ current_insert_positions(m_rowstart.begin(), m_rowstart.begin() + numverts);
+ for (; edge_begin != edge_end; ++edge_begin) {
+ vertices_size_type source = edge_begin->first;
+ EdgeIndex insert_pos = current_insert_positions[source];
+ ++current_insert_positions[source];
+ m_column[insert_pos] = edge_begin->second;
+ inherited_edge_properties::operator[](insert_pos) = edge_begin->second;
+ }
+ }
+
   // From number of vertices and sorted list of edges
   template<typename InputIterator>
- compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ 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())
@@ -209,7 +291,8 @@
 
   // From number of vertices and sorted list of edges
   template<typename InputIterator, typename EdgePropertyIterator>
- compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ 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,
@@ -292,13 +375,10 @@
     for (Vertex i = 0; i != numverts; ++i) {
       m_rowstart[i] = current_edge;
       g_vertex v = vertex(i, g);
- EdgeIndex num_edges_before_this_vertex = current_edge;
       g_out_edge_iter ei, ei_end;
       for (tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) {
         m_column[current_edge++] = get(vi, target(*ei, g));
       }
- std::sort(m_column.begin() + num_edges_before_this_vertex,
- m_column.begin() + current_edge);
     }
     m_rowstart[numverts] = current_edge;
     m_last_source = numverts;
@@ -387,8 +467,8 @@
   return old_num_verts_plus_one - 1;
 }
 
-// This function requires that (src, tgt) be lexicographically at least as
-// large as the largest edge in the graph so far
+// This function requires that src be at least as large as the largest source
+// in the graph so far
 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
 inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor
 add_edge(Vertex src, Vertex tgt, BOOST_CSR_GRAPH_TYPE& g) {
@@ -404,8 +484,8 @@
   return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, num_edges_orig);
 }
 
-// This function requires that (src, tgt) be lexicographically at least as
-// large as the largest edge in the graph so far
+// This function requires that src be at least as large as the largest source
+// in the graph so far
 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
 inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor
 add_edge(Vertex src, Vertex tgt,
@@ -532,38 +612,6 @@
   return i;
 }
 
-// Unlike for an adjacency_matrix, edge_range and edge take lg(out_degree(i))
-// time
-template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
-inline std::pair<typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator,
- typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator>
-edge_range(Vertex i, Vertex j, const BOOST_CSR_GRAPH_TYPE& g)
-{
- typedef typename std::vector<Vertex>::const_iterator adj_iter;
- typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
- typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor edge_desc;
- std::pair<adj_iter, adj_iter> raw_adjacencies = adjacent_vertices(i, g);
- std::pair<adj_iter, adj_iter> adjacencies =
- std::equal_range(raw_adjacencies.first, raw_adjacencies.second, j);
- EdgeIndex idx_begin = adjacencies.first - g.m_column.begin();
- EdgeIndex idx_end = adjacencies.second - g.m_column.begin();
- return std::make_pair(out_edge_iter(edge_desc(i, idx_begin)),
- out_edge_iter(edge_desc(i, idx_end)));
-}
-
-template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
-inline std::pair<typename BOOST_CSR_GRAPH_TYPE::edge_descriptor, bool>
-edge(Vertex i, Vertex j, const BOOST_CSR_GRAPH_TYPE& g)
-{
- typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
- std::pair<out_edge_iter, out_edge_iter> range = edge_range(i, j, g);
- if (range.first == range.second)
- return std::make_pair(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(),
- false);
- else
- return std::make_pair(*range.first, true);
-}
-
 // Find an edge given its index in the graph
 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
 inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor

Modified: trunk/libs/graph/doc/compressed_sparse_row.html
==============================================================================
--- trunk/libs/graph/doc/compressed_sparse_row.html (original)
+++ trunk/libs/graph/doc/compressed_sparse_row.html 2009-04-08 20:50:23 EDT (Wed, 08 Apr 2009)
@@ -1,11 +1,11 @@
 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
 <html>
 <!--
- -- Copyright (c) 2005 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)
+ Copyright (c) 2005 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>
@@ -103,14 +103,27 @@
   <i>// Graph constructors</i>
   <a href="#default-const">compressed_sparse_row_graph</a>();
 
+ template&lt;typename MultiPassInputIterator&gt;
+ compressed_sparse_row_graph(MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
+ vertices_size_type numverts,
+ const GraphProperty&amp; prop = GraphProperty());
+
+ template&lt;typename MultiPassInputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ const GraphProperty&amp; prop = GraphProperty());
+
   template&lt;typename InputIterator&gt;
- compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ 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&amp; prop = GraphProperty());
 
   template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
- compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ 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,
@@ -167,13 +180,6 @@
 <i>// Vertex access</i>
 vertex_descriptor vertex(vertices_size_type i, const compressed_sparse_row_graph&amp;);
 
-<i>// Edge access</i>
-std::pair&lt;out_edge_iterator, out_edge_iterator&gt;
- edge_range(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&amp;);
-std::pair&lt;edge_descriptor, bool&gt;
- edge(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&amp;);
-edge_descriptor edge_from_index(edges_size_type i, const compressed_sparse_row_graph&amp;);
-
 <i>// Property map accessors</i>
 template&lt;typename PropertyTag&gt;
 property_map&lt;compressed_sparse_row_graph, PropertyTag&gt;::type
@@ -339,8 +345,60 @@
     <hr></hr>
 
     <pre><a name="edge-const"></a>
+ template&lt;typename MultiPassInputIterator&gt;
+ compressed_sparse_row_graph(MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
+ vertices_size_type numverts,
+ const GraphProperty&amp; 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.
+ </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&lt;typename MultiPassInputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ const GraphProperty&amp; 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 edge range constructor, 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>.
+ </p>
+
+ <hr></hr>
+
+ <pre><a name="edge-sorted-const"></a>
   template&lt;typename InputIterator&gt;
- compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ 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&amp; prop = GraphProperty());
@@ -349,7 +407,10 @@
     <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
+ 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.sgi.com/tech/stl/InputIterator.html">InputIterator</a>
       whose <code>value_type</code> is an <code>std::pair</code> of
@@ -375,9 +436,10 @@
 
     <hr></hr>
 
- <pre><a name="edge-prop-const"></a>
+ <pre><a name="edge-sorted-prop-const"></a>
   template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
- compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ 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,
@@ -400,132 +462,3885 @@
 
     <hr></hr>
 
- <pre><a name="#graph-const"></a>
- template&lt;typename Graph, typename VertexIndexMap&gt;
- compressed_sparse_row_graph(const Graph&amp; g, const VertexIndexMap&amp; vi,
+ <pre><a name="edge-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
                               vertices_size_type numverts,
- edges_size_type numedges);
-
- template&lt;typename Graph, typename VertexIndexMap&gt;
- compressed_sparse_row_graph(const Graph&amp; g, const VertexIndexMap&amp; vi);
-
- template&lt;typename Graph&gt;
- explicit compressed_sparse_row_graph(const Graph&amp; g);
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; prop = GraphProperty());
     </pre>
 
     <p class="indent">
- Calls the assign function with
- all of the arguments it is given.
+ 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; i</i>.
     </p>
 
- <hr></hr>
+ <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>
 
- <a name="mutators"></a><h3>Mutators</h3>
- <pre><a name="assign"></a>
- template&lt;typename Graph, typename VertexIndexMap&gt;
- void assign(const Graph&amp; g, const VertexIndexMap&amp; vi,
- vertices_size_type numverts, edges_size_type numedges);
+ <p class="indent">
+ The value <code>prop</code> will be used to initialize the graph
+ property.
+ </p>
 
- template&lt;typename Graph, typename VertexIndexMap&gt;
- void assign(const Graph&amp; g, const VertexIndexMap&amp; vi);
+ <hr></hr>
 
- template&lt;typename Graph&gt;
- void assign(const Graph&amp; g);
+ <pre><a name="edge-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; prop = GraphProperty());
     </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 IncidenceGraph
- and have a <tt>vertex(i, g)</tt> function that retrieves the
- <i>i</i><sup>th</sup> vertex in the graph.
-
- <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
- VertexListGraph.</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
- EdgeListGraph.</li>
- </ul>
+ 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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>
 
- <a name="property-access"></a><h3>Property Access</h3>
-
- <pre><a name="vertex-subscript"></a>
- VertexProperty&amp; operator[](vertex_descriptor v);
- const VertexProperty&amp; operator[](vertex_descriptor v) const;
+ <pre><a name="edge-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; prop = GraphProperty());
     </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>.
+ 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; i</i>.
     </p>
 
- <hr></hr>
-
- <pre><a name="edge-subscript">
- EdgeProperty&amp; operator[](edge_descriptor v);
- const EdgeProperty&amp; operator[](edge_descriptor v) const;
- </pre>
+ <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">
- 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>.
+ The value <code>prop</code> will be used to initialize the graph
+ property.
     </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"></a>
- vertex_descriptor vertex(vertices_size_type i, const compressed_sparse_row_graph&amp;);
+ <pre><a name="edge-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; prop = GraphProperty());
     </pre>
     <p class="indent">
- Retrieves the <i>i</i><sup>th</sup> vertex in the graph in
- constant time.
+ 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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>
 
- <a name="edge-access"></a><h3>Edge access</h3>
- <pre><a name="edge_range"></a>
- std::pair&lt;out_edge_iterator, out_edge_iterator&gt;
- edge_range(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&amp;);
+ <pre><a name="edge-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; prop = GraphProperty());
     </pre>
 
     <p class="indent">
- Returns all edges from <tt>u</tt> to <tt>v</tt>. Requires time
- linear in the number of edges outgoing from <tt>u</tt>.
+ 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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"></a>
- std::pair&lt;edge_descriptor, bool&gt;
- edge(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&amp;);
+ <pre><a name="edge-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; prop = GraphProperty());
     </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 edge_range
- to retrieve all edges.
+ 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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-const"></a>
+ template&lt;typename InputIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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.sgi.com/tech/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> preceed any edges originating from all
+ vertices <i>j</i> where <i>j &gt; 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-prop-const"></a>
+ template&lt;typename InputIterator, typename EdgePropertyIterator&gt;
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty&amp; 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 edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/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="#graph-const"></a>
+ template&lt;typename Graph, typename VertexIndexMap&gt;
+ compressed_sparse_row_graph(const Graph&amp; g, const VertexIndexMap&amp; vi,
+ vertices_size_type numverts,
+ edges_size_type numedges);
+
+ template&lt;typename Graph, typename VertexIndexMap&gt;
+ compressed_sparse_row_graph(const Graph&amp; g, const VertexIndexMap&amp; vi);
+
+ template&lt;typename Graph&gt;
+ explicit compressed_sparse_row_graph(const Graph&amp; g);
+ </pre>
+
+ <p class="indent">
+ Calls the assign 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&lt;typename Graph, typename VertexIndexMap&gt;
+ void assign(const Graph&amp; g, const VertexIndexMap&amp; vi,
+ vertices_size_type numverts, edges_size_type numedges);
+
+ template&lt;typename Graph, typename VertexIndexMap&gt;
+ void assign(const Graph&amp; g, const VertexIndexMap&amp; vi);
+
+ template&lt;typename Graph&gt;
+ void assign(const Graph&amp; 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 IncidenceGraph
+ and have a <tt>vertex(i, g)</tt> function that retrieves the
+ <i>i</i><sup>th</sup> vertex in the graph.
+
+ <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
+ VertexListGraph.</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
+ EdgeListGraph.</li>
+ </ul>
+ </p>
+
+ <hr></hr>
+
+ <a name="property-access"></a><h3>Property Access</h3>
+
+ <pre><a name="vertex-subscript"></a>
+ VertexProperty&amp; operator[](vertex_descriptor v);
+ const VertexProperty&amp; 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&amp; operator[](edge_descriptor v);
+ const EdgeProperty&amp; 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"></a>
+ vertex_descriptor vertex(vertices_size_type i, const compressed_sparse_row_graph&amp;);
+ </pre>
+ <p class="indent">
+ Retrieves the <i>i</i><sup>th</sup> vertex in the graph in
+ constant time.
     </p>
 
     <hr></hr>

Modified: trunk/libs/graph/test/csr_graph_test.cpp
==============================================================================
--- trunk/libs/graph/test/csr_graph_test.cpp (original)
+++ trunk/libs/graph/test/csr_graph_test.cpp 2009-04-08 20:50:23 EDT (Wed, 08 Apr 2009)
@@ -181,11 +181,12 @@
                       boost::identity_property_map());
 
   // Check constructing a graph from iterators
- CSRGraphT g3(boost::make_transform_iterator(edges(g2).first,
- make_edge_to_index_pair(g2)),
- boost::make_transform_iterator(edges(g2).second,
- make_edge_to_index_pair(g2)),
- num_vertices(g));
+ CSRGraphT g3(boost::edges_are_sorted,
+ boost::make_transform_iterator(edges(g2).first,
+ make_edge_to_index_pair(g2)),
+ boost::make_transform_iterator(edges(g2).second,
+ make_edge_to_index_pair(g2)),
+ num_vertices(g));
   check_consistency(g3);
   BOOST_CHECK((std::size_t)std::distance(edges(g3).first, edges(g3).second)
               == num_edges(g3));
@@ -216,19 +217,17 @@
 
   // Check edge_from_index (and implicitly the edge_index property map) for
   // each edge in g2
- // This test also checks for the correct sorting of the edge iteration
   std::size_t last_src = 0, last_tgt = 0;
   for (boost::tie(ei, ei_end) = edges(g2); ei != ei_end; ++ei) {
     BOOST_CHECK(edge_from_index(get(boost::edge_index, g2, *ei), g2) == *ei);
     std::size_t src = get(boost::vertex_index, g2, source(*ei, g2));
     std::size_t tgt = get(boost::vertex_index, g2, target(*ei, g2));
- BOOST_CHECK(src > last_src || (src == last_src && tgt >= last_tgt));
+ BOOST_CHECK(src >= last_src);
     last_src = src;
     last_tgt = tgt;
   }
 
   // Check out edge iteration and vertex iteration for sortedness
- // Also, check a few runs of edge and edge_range
   CSRGraphT::vertex_iterator vi, vi_end;
   std::size_t last_vertex = 0;
   bool first_iter = true;
@@ -239,25 +238,8 @@
     first_iter = false;
 
     CSRGraphT::out_edge_iterator oei, oei_end;
- std::size_t last_tgt = 0;
     for (boost::tie(oei, oei_end) = out_edges(*vi, g2); oei != oei_end; ++oei) {
       BOOST_CHECK(source(*oei, g2) == *vi);
- CSRGraphT::vertex_descriptor tgtd = target(*oei, g2);
- std::size_t tgt = get(boost::vertex_index, g2, tgtd);
- BOOST_CHECK(tgt >= last_tgt);
- last_tgt = tgt;
-
- std::pair<CSRGraphT::edge_descriptor, bool> edge_info = edge(*vi, tgtd, g2);
- BOOST_CHECK(edge_info.second == true);
- BOOST_CHECK(source(edge_info.first, g2) == *vi);
- BOOST_CHECK(target(edge_info.first, g2) == tgtd);
- std::pair<CSRGraphT::out_edge_iterator, CSRGraphT::out_edge_iterator> er =
- edge_range(*vi, tgtd, g2);
- BOOST_CHECK(er.first != er.second);
- for (; er.first != er.second; ++er.first) {
- BOOST_CHECK(source(*er.first, g2) == *vi);
- BOOST_CHECK(target(*er.first, g2) == tgtd);
- }
     }
 
     // Find a vertex for testing
@@ -268,14 +250,6 @@
       if (target(*oei2, g2) == test_vertex)
         ++edge_count;
     }
-
- // Test edge and edge_range on an edge that may not be present
- std::pair<CSRGraphT::edge_descriptor, bool> edge_info =
- edge(*vi, test_vertex, g2);
- BOOST_CHECK(edge_info.second == (edge_count != 0));
- std::pair<CSRGraphT::out_edge_iterator, CSRGraphT::out_edge_iterator> er =
- edge_range(*vi, test_vertex, g2);
- BOOST_CHECK(er.second - er.first == edge_count);
   }
 
   // Run brandes_betweenness_centrality, which touches on a whole lot
@@ -356,7 +330,7 @@
   double weights[6] = { 1.0, 1.0, 0.5, 1.0, 1.0, 0.5 };
   double centrality[5] = { 0.0, 1.5, 0.0, 1.0, 0.5 };
 
- CSRGraphWithPropsT g(&edges_init[0], &edges_init[0] + 6, &weights[0], 5, 6);
+ CSRGraphWithPropsT g(boost::edges_are_sorted, &edges_init[0], &edges_init[0] + 6, &weights[0], 5, 6);
   brandes_betweenness_centrality
     (g,
      centrality_map(get(&Vertex::centrality, g)).
@@ -404,5 +378,12 @@
   test_graph_properties();
   test_vertex_and_edge_properties();
 
+ {
+ std::cout << "Testing CSR graph built from unsorted edges" << std::endl;
+ std::pair<int, int> unsorted_edges[] = {std::make_pair(5, 0), std::make_pair(3, 2), std::make_pair(4, 1), std::make_pair(4, 0), std::make_pair(0, 2), std::make_pair(5, 2)};
+ CSRGraphT g(unsorted_edges, unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges), 6);
+ graph_test(g);
+ }
+
   return 0;
 }

Date view Thread view Subject view Author view