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& g, GraphPropertyTag,
const typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type& value);
-<i>// Incremental construction functions (old interface only)</i>
+<i>// Incremental construction functions</i>
+<b>(old interface only)</b>
template<typename Graph>
vertex_descriptor add_vertex(compressed_sparse_row_graph& g);
+<b>(old interface only)</b>
template<typename Graph>
vertex_descriptor add_vertices(vertices_size_type count, compressed_sparse_row_graph& g);
+<b>(old interface only)</b>
template<typename Graph>
edge_descriptor add_edge(vertex_descriptor src, vertex_descriptor tgt, compressed_sparse_row_graph& g);
+<b>(new interface only)</b>
+template<typename InputIterator, typename Graph>
+void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g);
+
} <i>// end namespace boost</i>
</pre>
@@ -908,6 +915,23 @@
</p>
<hr></hr>
+
+ <pre><a name="add_edges"></a>
+template<typename InputIterator>
+edge_descriptor add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g)
+ </pre>
+
+ <p class="indent">
+ Add a range of edges (from <tt>first</tt> to <tt>last</tt>) to the graph.
+ The <tt>InputIterator</tt> must be a model of <a
+ href="http://www.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