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

Subject: [Boost-commit] svn:boost r54023 - in trunk: boost/graph libs/graph/doc libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-06-17 17:05:07

Author: jewillco
Date: 2009-06-17 17:05:06 EDT (Wed, 17 Jun 2009)
New Revision: 54023
URL: http://svn.boost.org/trac/boost/changeset/54023

Log:
Added incremental add_edges function to new interface; refs #3134
Text files modified: 
   trunk/boost/graph/compressed_sparse_row_graph.hpp |    59 ++++++++++++++++++++++++++++++++++++++++
   trunk/libs/graph/doc/compressed_sparse_row.html   |    26 ++++++++++++++++                        
   trunk/libs/graph/test/csr_graph_test.cpp          |    10 ++++++                                  
   3 files changed, 94 insertions(+), 1 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-06-17 17:05:06 EDT (Wed, 17 Jun 2009)
@@ -1071,6 +1071,65 @@
 }
 #endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
 
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+// Add edges from a range of (source, target) pairs that are unsorted
+template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
+inline void
+add_edges(InputIterator first, InputIterator last, BOOST_CSR_GRAPH_TYPE& g) {
+  typedef BOOST_CSR_GRAPH_TYPE Graph;
+  typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
+  typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num;
+  typedef typename boost::graph_traits<Graph>::edges_size_type edge_num;
+  typedef std::vector<std::pair<vertex_t, vertex_t> > edge_vector_t;
+  edge_vector_t new_edges(first, last);
+  if (new_edges.empty()) return;
+  std::sort(new_edges.begin(), new_edges.end());
+  edge_num edges_added_before_i = new_edges.size(); // Count increment to add to rowstarts
+  g.m_column.resize(g.m_column.size() + new_edges.size());
+  typename edge_vector_t::const_reverse_iterator
+    current_new_edge = new_edges.rbegin(),
+    prev_new_edge = new_edges.rbegin();
+  for (vertex_num i_plus_1 = num_vertices(g); i_plus_1 > 0; --i_plus_1) {
+    vertex_num i = i_plus_1 - 1;
+    prev_new_edge = current_new_edge;
+    // edges_added_to_this_vertex = #mbrs of new_edges with first == i
+    edge_num edges_added_to_this_vertex = 0;
+    while (current_new_edge !=
+            (typename edge_vector_t::const_reverse_iterator)new_edges.rend()) {
+      if (current_new_edge->first != i) break;
+      ++current_new_edge;
+      ++edges_added_to_this_vertex;
+    }
+    edges_added_before_i -= edges_added_to_this_vertex;
+    // Invariant: edges_added_before_i = #mbrs of new_edges with first < i
+    edge_num old_rowstart = g.m_rowstart[i];
+    edge_num new_rowstart = g.m_rowstart[i] + edges_added_before_i;
+    edge_num old_degree = g.m_rowstart[i + 1] - g.m_rowstart[i];
+    edge_num new_degree = old_degree + edges_added_to_this_vertex;
+    // Move old edges forward (by #new_edges before this i) to make room
+    // new_rowstart > old_rowstart, so use copy_backwards
+    if (old_rowstart != new_rowstart) {
+      std::copy_backward(g.m_column.begin() + old_rowstart,
+                         g.m_column.begin() + old_rowstart + old_degree,
+                         g.m_column.begin() + new_rowstart + old_degree);
+    }
+    // Add new edges (reversed because current_new_edge is a
+    // const_reverse_iterator)
+    typename edge_vector_t::const_reverse_iterator temp = current_new_edge;
+    for (; temp != prev_new_edge; ++old_degree) {
+      --temp;
+      g.m_column[new_rowstart + old_degree] = temp->second;
+    }
+    g.m_rowstart[i + 1] = new_rowstart + new_degree;
+    if (edges_added_before_i == 0) break; // No more edges inserted before this point
+    // g.m_rowstart[i] will be fixed up on the next iteration (to avoid
+    // changing the degree of vertex i - 1); the last iteration never changes
+    // it (either because of the condition of the break or because
+    // g.m_rowstart[0] is always 0)
+  }
+}
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
 // From VertexListGraph
 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
 inline Vertex

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-06-17 17:05:06 EDT (Wed, 17 Jun 2009)
@@ -277,16 +277,23 @@
 void set_property(const compressed_sparse_row_graph&amp; g, GraphPropertyTag,
                   const typename graph_property&lt;compressed_sparse_row_graph, GraphPropertyTag&gt;::type&amp; value);
 
-<i>// Incremental construction functions (old interface only)</i>
+<i>// Incremental construction functions</i>
+<b>(old interface only)</b>
 template&lt;typename Graph&gt;
 vertex_descriptor add_vertex(compressed_sparse_row_graph&amp; g);
 
+<b>(old interface only)</b>
 template&lt;typename Graph&gt;
 vertex_descriptor add_vertices(vertices_size_type count, compressed_sparse_row_graph&amp; g);
 
+<b>(old interface only)</b>
 template&lt;typename Graph&gt;
 edge_descriptor add_edge(vertex_descriptor src, vertex_descriptor tgt, compressed_sparse_row_graph&amp; g);
 
+<b>(new interface only)</b>
+template&lt;typename InputIterator, typename Graph&gt;
+void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph&amp; g);
+
 } <i>// end namespace boost</i>
    </pre>
 
@@ -908,6 +915,23 @@
     </p>
 
     <hr></hr>
+
+    <pre><a name="add_edges"></a>
+template&lt;typename InputIterator&gt;
+edge_descriptor add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph&amp; g)
+    </pre>
+    
+    <p class="indent">
+      Add a range of edges (from <tt>first</tt> to <tt>last</tt>) to the graph.
+      The <tt>InputIterator</tt> must be a model of <a
+      href="http://www.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 of the
+      new edges.  The edges do not need to be sorted.
+      <b>(This function is only provided by the new interface.)</b>
+    </p>
+
+    <hr></hr>
     <a name="example"></a><h2>Example</h2>
 
     <br>[<a

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-06-17 17:05:06 EDT (Wed, 17 Jun 2009)
@@ -84,6 +84,7 @@
       std::sort(edges1.begin(), edges1.end());
       std::sort(edges2.begin(), edges2.end());
       if (edges1 != edges2) {
+        std::cerr << "For vertex " << v1 << std::endl;
         std::cerr << "edges1:";
         for (size_t i = 0; i < edges1.size(); ++i) std::cerr << " " << edges1[i];
         std::cerr << std::endl;
@@ -487,6 +488,15 @@
     assert_graphs_equal(g, boost::identity_property_map(),
                         g2, boost::identity_property_map(),
                         boost::identity_property_map());
+    std::cout << "Testing CSR graph built using add_edges" << std::endl;
+    // Test building a graph using add_edges on unsorted lists
+    CSRGraphT g3(boost::edges_are_unsorted, unsorted_edges, unsorted_edges, 6); // Empty range
+    add_edges(unsorted_edges, unsorted_edges + 3, g3);
+    add_edges(unsorted_edges + 3, unsorted_edges + 6, g3);
+    graph_test(g3);
+    assert_graphs_equal(g, boost::identity_property_map(),
+                        g3, boost::identity_property_map(),
+                        boost::identity_property_map());
   }
 #endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE