[Boost-commit] svn:boost r52275 - in trunk: boost/graph libs/graph/doc libs/graph/test

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;
 }