Subject: [Boost-commit] svn:boost r54738 - in branches/release: boost/graph libs/graph/doc libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-07-06 20:32:11
Author: jewillco
Date: 2009-07-06 20:32:10 EDT (Mon, 06 Jul 2009)
New Revision: 54738
URL: http://svn.boost.org/trac/boost/changeset/54738
Log:
Merged patches from messages 55-57 of #3134, plus r54737; refs #3134
Text files modified:
branches/release/boost/graph/compressed_sparse_row_graph.hpp | 193 ++++++++++++++++++++++++++++++++++++++-
branches/release/libs/graph/doc/compressed_sparse_row.html | 25 +++++
branches/release/libs/graph/test/csr_graph_test.cpp | 3
3 files changed, 212 insertions(+), 9 deletions(-)
Modified: branches/release/boost/graph/compressed_sparse_row_graph.hpp
==============================================================================
--- branches/release/boost/graph/compressed_sparse_row_graph.hpp (original)
+++ branches/release/boost/graph/compressed_sparse_row_graph.hpp 2009-07-06 20:32:10 EDT (Mon, 06 Jul 2009)
@@ -28,6 +28,9 @@
#include <boost/graph/detail/indexed_properties.hpp>
#include <boost/iterator/counting_iterator.hpp>
#include <boost/iterator/reverse_iterator.hpp>
+#include <boost/iterator/zip_iterator.hpp>
+#include <boost/iterator/transform_iterator.hpp>
+#include <boost/tuple/tuple.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/integer.hpp>
#include <boost/iterator/iterator_facade.hpp>
@@ -175,6 +178,25 @@
void advance(typename base_type::difference_type) {}
typename base_type::difference_type distance_to(default_construct_iterator) const {return 0;}
};
+
+ template <typename Less>
+ struct compare_first {
+ Less less;
+ compare_first(Less less = Less()): less(less) {}
+ template <typename Tuple>
+ bool operator()(const Tuple& a, const Tuple& b) const {
+ return less(a.template get<0>(), b.template get<0>());
+ }
+ };
+
+ template <int N, typename Result>
+ struct my_tuple_get_class {
+ typedef const Result& result_type;
+ template <typename Tuple>
+ result_type operator()(const Tuple& t) const {
+ return t.template get<N>();
+ }
+ };
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
}
@@ -983,12 +1005,14 @@
#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>
+ template <typename BidirectionalIteratorOrig, typename EPIterOrig,
+ typename GlobalToLocal>
void
add_edges_sorted_internal(
BidirectionalIteratorOrig first_sorted,
BidirectionalIteratorOrig last_sorted,
- EPIterOrig ep_iter_sorted) {
+ EPIterOrig ep_iter_sorted,
+ const GlobalToLocal& global_to_local) {
typedef boost::reverse_iterator<BidirectionalIteratorOrig> BidirectionalIterator;
typedef boost::reverse_iterator<EPIterOrig> EPIter;
// Flip sequence
@@ -999,6 +1023,7 @@
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
@@ -1012,7 +1037,7 @@
// 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;
+ if (get(global_to_local, current_new_edge->first) != i) break;
++current_new_edge;
++current_new_edge_prop;
++edges_added_to_this_vertex;
@@ -1049,6 +1074,16 @@
}
}
+ template <typename BidirectionalIteratorOrig, typename EPIterOrig>
+ void
+ add_edges_sorted_internal(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ EPIterOrig ep_iter_sorted) {
+ add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted,
+ identity_property_map());
+ }
+
// Add edges from a sorted (smallest sources first) range of pairs
template <typename BidirectionalIteratorOrig>
void
@@ -1058,10 +1093,33 @@
add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<typename inherited_edge_properties::edge_bundled>());
}
+ template <typename BidirectionalIteratorOrig, typename GlobalToLocal>
+ void
+ add_edges_sorted_internal_global(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ const GlobalToLocal& global_to_local) {
+ add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<typename inherited_edge_properties::edge_bundled>(),
+ global_to_local);
+ }
+
+ template <typename BidirectionalIteratorOrig, typename EPIterOrig,
+ typename GlobalToLocal>
+ void
+ add_edges_sorted_internal_global(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ EPIterOrig ep_iter_sorted,
+ const GlobalToLocal& global_to_local) {
+ add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted,
+ global_to_local);
+ }
+
// Add edges from a range of (source, target) pairs that are unsorted
- template <typename InputIterator>
+ template <typename InputIterator, typename GlobalToLocal>
inline void
- add_edges_internal(InputIterator first, InputIterator last) {
+ add_edges_internal(InputIterator first, InputIterator last,
+ const GlobalToLocal& global_to_local) {
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;
@@ -1070,7 +1128,59 @@
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());
+ add_edges_sorted_internal_global(new_edges.begin(), new_edges.end(), global_to_local);
+ }
+
+ template <typename InputIterator>
+ inline void
+ add_edges_internal(InputIterator first, InputIterator last) {
+ add_edges_internal(first, last, identity_property_map());
+ }
+
+ // Add edges from a range of (source, target) pairs and edge properties that
+ // are unsorted
+ template <typename InputIterator, typename EPIterator, typename GlobalToLocal>
+ inline void
+ add_edges_internal(InputIterator first, InputIterator last,
+ EPIterator ep_iter, EPIterator ep_iter_end,
+ const GlobalToLocal& global_to_local) {
+ 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::pair<vertex_t, vertex_t> vertex_pair;
+ typedef std::vector<
+ boost::tuple<vertex_pair,
+ typename inherited_edge_properties::edge_bundled> >
+ edge_vector_t;
+ edge_vector_t new_edges
+ (boost::make_zip_iterator(boost::make_tuple(first, ep_iter)),
+ boost::make_zip_iterator(boost::make_tuple(last, ep_iter_end)));
+ if (new_edges.empty()) return;
+ std::sort(new_edges.begin(), new_edges.end(),
+ boost::detail::compare_first<
+ std::less<vertex_pair> >());
+ add_edges_sorted_internal
+ (boost::make_transform_iterator(
+ new_edges.begin(),
+ boost::detail::my_tuple_get_class<0, vertex_pair>()),
+ boost::make_transform_iterator(
+ new_edges.end(),
+ boost::detail::my_tuple_get_class<0, vertex_pair>()),
+ boost::make_transform_iterator(
+ new_edges.begin(),
+ boost::detail::my_tuple_get_class
+ <1, typename inherited_edge_properties::edge_bundled>()),
+ global_to_local);
+ }
+
+ // Add edges from a range of (source, target) pairs and edge properties that
+ // are unsorted
+ template <typename InputIterator, typename EPIterator>
+ inline void
+ add_edges_internal(InputIterator first, InputIterator last,
+ EPIterator ep_iter, EPIterator ep_iter_end) {
+ add_edges_internal(first, last, ep_iter, ep_iter_end, identity_property_map());
}
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
@@ -1133,16 +1243,28 @@
inline Vertex
add_vertex(BOOST_CSR_GRAPH_TYPE& g) {
Vertex old_num_verts_plus_one = g.m_rowstart.size();
- g.m_rowstart.push_back(EdgeIndex(0));
+ EdgeIndex numedges = g.m_rowstart.back();
+ g.m_rowstart.push_back(numedges);
g.vertex_properties().resize(num_vertices(g));
return old_num_verts_plus_one - 1;
}
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
inline Vertex
+add_vertex(BOOST_CSR_GRAPH_TYPE& g,
+ typename BOOST_CSR_GRAPH_TYPE::vertex_bundled const& p) {
+ Vertex old_num_verts_plus_one = g.m_rowstart.size();
+ g.m_rowstart.push_back(EdgeIndex(0));
+ g.vertex_properties().push_back(p);
+ return old_num_verts_plus_one - 1;
+}
+
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+inline Vertex
add_vertices(typename BOOST_CSR_GRAPH_TYPE::vertices_size_type count, BOOST_CSR_GRAPH_TYPE& g) {
Vertex old_num_verts_plus_one = g.m_rowstart.size();
- g.m_rowstart.resize(old_num_verts_plus_one + count, EdgeIndex(0));
+ EdgeIndex numedges = g.m_rowstart.back();
+ g.m_rowstart.resize(old_num_verts_plus_one + count, numedges);
g.vertex_properties().resize(num_vertices(g));
return old_num_verts_plus_one - 1;
}
@@ -1208,12 +1330,67 @@
g.add_edges_sorted_internal(first_sorted, last_sorted);
}
+ template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
+ typename EPIterOrig, typename GlobalToLocal>
+ void
+ add_edges_sorted_global(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ EPIterOrig ep_iter_sorted,
+ const GlobalToLocal& global_to_local,
+ BOOST_CSR_GRAPH_TYPE& g) {
+ g.add_edges_sorted_internal_global(first_sorted, last_sorted, ep_iter_sorted,
+ global_to_local);
+ }
+
+ // Add edges from a sorted (smallest sources first) range of pairs
+ template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
+ typename GlobalToLocal>
+ void
+ add_edges_sorted_global(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ const GlobalToLocal& global_to_local,
+ BOOST_CSR_GRAPH_TYPE& g) {
+ g.add_edges_sorted_internal_global(first_sorted, last_sorted, global_to_local);
+ }
+
+ // Add edges from a range of (source, target) pairs that are unsorted
+ template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator,
+ typename GlobalToLocal>
+ inline void
+ add_edges_global(InputIterator first, InputIterator last,
+ const GlobalToLocal& global_to_local, BOOST_CSR_GRAPH_TYPE& g) {
+ g.add_edges_internal(first, last, global_to_local);
+ }
+
// 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);
}
+
+ // Add edges from a range of (source, target) pairs and edge properties that
+ // are unsorted
+ template <BOOST_CSR_GRAPH_TEMPLATE_PARMS,
+ typename InputIterator, typename EPIterator>
+ inline void
+ add_edges(InputIterator first, InputIterator last,
+ EPIterator ep_iter, EPIterator ep_iter_end,
+ BOOST_CSR_GRAPH_TYPE& g) {
+ g.add_edges_internal(first, last, ep_iter, ep_iter_end);
+ }
+
+ template <BOOST_CSR_GRAPH_TEMPLATE_PARMS,
+ typename InputIterator, typename EPIterator, typename GlobalToLocal>
+ inline void
+ add_edges_global(InputIterator first, InputIterator last,
+ EPIterator ep_iter, EPIterator ep_iter_end,
+ const GlobalToLocal& global_to_local,
+ BOOST_CSR_GRAPH_TYPE& g) {
+ g.add_edges_internal(first, last, ep_iter, ep_iter_end, global_to_local);
+ }
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// From VertexListGraph
Modified: branches/release/libs/graph/doc/compressed_sparse_row.html
==============================================================================
--- branches/release/libs/graph/doc/compressed_sparse_row.html (original)
+++ branches/release/libs/graph/doc/compressed_sparse_row.html 2009-07-06 20:32:10 EDT (Mon, 06 Jul 2009)
@@ -295,6 +295,10 @@
void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g);
<b>(new interface only)</b>
+template<typename InputIterator, typename EPIter, typename Graph>
+void add_edges(InputIterator first, InputIterator last, EPIter ep_first, EPIter ep_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);
@@ -941,6 +945,27 @@
<hr></hr>
+ <pre><a name="add_edges_prop"></a>
+template<typename InputIterator, typename EPIter>
+void add_edges(InputIterator first, InputIterator last, EPIter ep_first, EPIter ep_last, compressed_sparse_row_graph& g)
+ </pre>
+
+ <p class="indent">
+ Add a range of edges (from <tt>first</tt> to <tt>last</tt>) with
+ corresponding edge properties (from <tt>ep_first</tt> to
+ <tt>ep_last</tt>) to the graph. The <tt>InputIterator</tt> and
+ <tt>EPIter</tt> must be models of <a
+ href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>;
+ the <code>value_type</code> of <tt>InputIterator</tt> must be an
+ <code>std::pair</code> of integer values, and the <code>value_type</code>
+ of <tt>EPIter</tt> must be the edge property type of the graph. The
+ integer values produced by the <tt>InputIterator</tt> 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>
+
<pre><a name="add_edges_sorted"></a>
template<typename BidirectionalIterator>
void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph& g)
Modified: branches/release/libs/graph/test/csr_graph_test.cpp
==============================================================================
--- branches/release/libs/graph/test/csr_graph_test.cpp (original)
+++ branches/release/libs/graph/test/csr_graph_test.cpp 2009-07-06 20:32:10 EDT (Mon, 06 Jul 2009)
@@ -492,7 +492,8 @@
// 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);
+ boost::no_property edge_data[3];
+ add_edges(unsorted_edges + 3, unsorted_edges + 6, edge_data, edge_data + 3, g3);
graph_test(g3);
assert_graphs_equal(g, boost::identity_property_map(),
g3, boost::identity_property_map(),