Subject: [Boost-commit] svn:boost r54316 - in trunk: boost/graph boost/graph/detail libs/graph/doc
From: jewillco_at_[hidden]
Date: 2009-06-24 16:44:55
Author: jewillco
Date: 2009-06-24 16:44:53 EDT (Wed, 24 Jun 2009)
New Revision: 54316
URL: http://svn.boost.org/trac/boost/changeset/54316
Log:
Added capability to add sorted edge/property sets to CSR graphs; refs #3134
Text files modified:
trunk/boost/graph/compressed_sparse_row_graph.hpp | 191 ++++++++++++++++++++++++++++-----------
trunk/boost/graph/detail/indexed_properties.hpp | 18 +++
trunk/libs/graph/doc/compressed_sparse_row.html | 51 ++++++++++
3 files changed, 204 insertions(+), 56 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-24 16:44:53 EDT (Wed, 24 Jun 2009)
@@ -27,6 +27,7 @@
#include <boost/graph/filtered_graph.hpp> // For keep_all
#include <boost/graph/detail/indexed_properties.hpp>
#include <boost/iterator/counting_iterator.hpp>
+#include <boost/iterator/reverse_iterator.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/integer.hpp>
#include <boost/iterator/iterator_facade.hpp>
@@ -157,6 +158,18 @@
category;
return reserve_count_for_single_pass_helper(first, last, category());
}
+
+ template <typename T>
+ struct default_construct_iterator: public boost::iterator_facade<default_construct_iterator<T>, T, boost::random_access_traversal_tag, const T&> {
+ typedef boost::iterator_facade<default_construct_iterator<T>, T, std::random_access_iterator_tag, const T&> base_type;
+ T saved_value;
+ const T& dereference() const {return saved_value;}
+ bool equal(default_construct_iterator i) const {return true;}
+ void increment() {}
+ void decrement() {}
+ void advance(typename base_type::difference_type) {}
+ typename base_type::difference_type distance_to(default_construct_iterator) const {return 0;}
+ };
}
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
@@ -179,6 +192,7 @@
EdgeIndex> >
{
+ public:
typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,
VertexProperty, Vertex>
inherited_vertex_properties;
@@ -961,6 +975,100 @@
assign(g, get(vertex_index, g), num_vertices(g), num_edges(g));
}
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+ // Add edges from a sorted (smallest sources first) range of pairs and edge
+ // properties
+ template <typename BidirectionalIteratorOrig, typename EPIterOrig>
+ void
+ add_edges_sorted_internal(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ EPIterOrig ep_iter_sorted) {
+ typedef boost::reverse_iterator<BidirectionalIteratorOrig> BidirectionalIterator;
+ typedef boost::reverse_iterator<EPIterOrig> EPIter;
+ // Flip sequence
+ BidirectionalIterator first(last_sorted);
+ BidirectionalIterator last(first_sorted);
+ typedef compressed_sparse_row_graph 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;
+ edge_num new_edge_count = std::distance(first, last);
+ EPIter ep_iter(ep_iter_sorted);
+ std::advance(ep_iter, -(std::ptrdiff_t)new_edge_count);
+ edge_num edges_added_before_i = new_edge_count; // Count increment to add to rowstarts
+ m_column.resize(m_column.size() + new_edge_count);
+ inherited_edge_properties::resize(inherited_edge_properties::size() + new_edge_count);
+ BidirectionalIterator current_new_edge = first, prev_new_edge = first;
+ EPIter current_new_edge_prop = ep_iter;
+ for (vertex_num i_plus_1 = num_vertices(*this); 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 != last) {
+ if (current_new_edge->first != i) break;
+ ++current_new_edge;
+ ++current_new_edge_prop;
+ ++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 = m_rowstart[i];
+ edge_num new_rowstart = m_rowstart[i] + edges_added_before_i;
+ edge_num old_degree = m_rowstart[i + 1] - 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(m_column.begin() + old_rowstart,
+ m_column.begin() + old_rowstart + old_degree,
+ m_column.begin() + new_rowstart + old_degree);
+ inherited_edge_properties::move_range(old_rowstart, old_rowstart + old_degree, new_rowstart);
+ }
+ // Add new edges (reversed because current_new_edge is a
+ // const_reverse_iterator)
+ BidirectionalIterator temp = current_new_edge;
+ EPIter temp_prop = current_new_edge_prop;
+ for (; temp != prev_new_edge; ++old_degree) {
+ --temp;
+ m_column[new_rowstart + old_degree] = temp->second;
+ inherited_edge_properties::write_by_index(new_rowstart + old_degree, *temp_prop);
+ }
+ m_rowstart[i + 1] = new_rowstart + new_degree;
+ if (edges_added_before_i == 0) break; // No more edges inserted before this point
+ // 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
+ // m_rowstart[0] is always 0)
+ }
+ }
+
+ // Add edges from a sorted (smallest sources first) range of pairs
+ template <typename BidirectionalIteratorOrig>
+ void
+ add_edges_sorted_internal(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted) {
+ add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<typename inherited_edge_properties::edge_property_type>());
+ }
+
+ // Add edges from a range of (source, target) pairs that are unsorted
+ template <typename InputIterator>
+ inline void
+ add_edges_internal(InputIterator first, InputIterator last) {
+ typedef compressed_sparse_row_graph 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());
+ add_edges_sorted_internal(new_edges.begin(), new_edges.end());
+ }
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
using inherited_vertex_properties::operator[];
using inherited_edge_properties::operator[];
@@ -1072,62 +1180,35 @@
#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)
+ // Add edges from a sorted (smallest sources first) range of pairs and edge
+ // properties
+ template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
+ typename EPIterOrig>
+ void
+ add_edges_sorted(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ EPIterOrig ep_iter_sorted,
+ BOOST_CSR_GRAPH_TYPE& g) {
+ g.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted);
+ }
+
+ // Add edges from a sorted (smallest sources first) range of pairs
+ template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig>
+ void
+ add_edges_sorted(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ BOOST_CSR_GRAPH_TYPE& g) {
+ g.add_edges_sorted_internal(first_sorted, last_sorted);
+ }
+
+ // 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) {
+ g.add_edges_internal(first, last);
}
-}
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// From VertexListGraph
Modified: trunk/boost/graph/detail/indexed_properties.hpp
==============================================================================
--- trunk/boost/graph/detail/indexed_properties.hpp (original)
+++ trunk/boost/graph/detail/indexed_properties.hpp 2009-06-24 16:44:53 EDT (Wed, 24 Jun 2009)
@@ -127,6 +127,12 @@
// Initialize with n default-constructed property values
indexed_edge_properties(std::size_t n) : m_edge_properties(n) { }
+ // Get the size of the properties vector
+ std::size_t size() const
+ {
+ return m_edge_properties.size();
+ }
+
// Resize the properties vector
void resize(std::size_t n)
{
@@ -152,6 +158,14 @@
m_edge_properties.push_back(prop);
}
+ // Move range of properties backwards
+ void move_range(std::size_t src_begin, std::size_t src_end, std::size_t dest_begin) {
+ std::copy_backward(
+ m_edge_properties.begin() + src_begin,
+ m_edge_properties.begin() + src_end,
+ m_edge_properties.begin() + dest_begin + (src_end - src_begin));
+ }
+
private:
// Access to the derived object
Derived& derived() { return *static_cast<Derived*>(this); }
@@ -174,16 +188,20 @@
typedef void* edge_push_back_type;
secret operator[](secret) { return secret(); }
+ void write_by_index(std::size_t idx, const no_property& prop) {}
protected:
// All operations do nothing.
indexed_edge_properties() { }
indexed_edge_properties(std::size_t) { }
+ std::size_t size() const {return 0;}
void resize(std::size_t) { }
void reserve(std::size_t) { }
public:
void push_back(const edge_push_back_type&) { }
+ void move_range(std::size_t src_begin, std::size_t src_end, std::size_t dest_begin) {}
+
};
}
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-24 16:44:53 EDT (Wed, 24 Jun 2009)
@@ -294,6 +294,14 @@
template<typename InputIterator, typename Graph>
void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g);
+<b>(new interface only)</b>
+template<typename BidirectionalIterator, typename Graph>
+void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph& g);
+
+<b>(new interface only)</b>
+template<typename BidirectionalIterator, typename EPIter, typename Graph>
+void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, EPIter ep_iter, compressed_sparse_row_graph& g);
+
} <i>// end namespace boost</i>
</pre>
@@ -918,7 +926,7 @@
<pre><a name="add_edges"></a>
template<typename InputIterator>
-edge_descriptor add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g)
+void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g)
</pre>
<p class="indent">
@@ -932,6 +940,47 @@
</p>
<hr></hr>
+
+ <pre><a name="add_edges_sorted"></a>
+template<typename BidirectionalIterator>
+void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph& g)
+ </pre>
+
+ <p class="indent">
+ Add a range of edges (from <tt>first</tt> to <tt>last</tt>) to the graph.
+ The <tt>BidirectionalIterator</tt> must be a model of <a
+ href="http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>
+ whose <code>value_type</code> is an <code>std::pair</code> of integer
+ values. These integer values are the source and target vertices of the
+ new edges. The edges must be sorted in increasing order by source vertex
+ index.
+ <b>(This function is only provided by the new interface.)</b>
+ </p>
+
+ <hr></hr>
+
+ <pre><a name="add_edges_sorted_prop"></a>
+template<typename BidirectionalIterator, typename EPIter>
+void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, EPIter ep_iter, compressed_sparse_row_graph& g)
+ </pre>
+
+ <p class="indent">
+ Add a range of edges (from <tt>first</tt> to <tt>last</tt>) to the graph.
+ The <tt>BidirectionalIterator</tt> and <tt>EPIter</tt> must be models of
+ <a
+ href="http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>.
+ The <code>value_type</code> of the <tt>BidirectionalIterator</tt> must be
+ an <code>std::pair</code> of integer
+ values. These integer values are the source and target vertices of the
+ new edges.
+ The <code>value_type</code> of the <tt>EPIter</tt> must be the edge
+ property type of the graph.
+ The edges must be sorted in increasing order by source vertex
+ index.
+ <b>(This function is only provided by the new interface.)</b>
+ </p>
+
+ <hr></hr>
<a name="example"></a><h2>Example</h2>
<br>[<a