Subject: [Boost-commit] svn:boost r54684 - in trunk: boost/graph libs/graph/doc libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-07-05 16:35:44
Author: jewillco
Date: 2009-07-05 16:35:44 EDT (Sun, 05 Jul 2009)
New Revision: 54684
URL: http://svn.boost.org/trac/boost/changeset/54684
Log:
Added add_edges() function with edge properties; refs #3134
Text files modified:
trunk/boost/graph/compressed_sparse_row_graph.hpp | 68 ++++++++++++++++++++++++++++++++++++++++
trunk/libs/graph/doc/compressed_sparse_row.html | 25 ++++++++++++++
trunk/libs/graph/test/csr_graph_test.cpp | 3 +
3 files changed, 95 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-07-05 16:35:44 EDT (Sun, 05 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 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
}
@@ -1102,6 +1124,41 @@
std::sort(new_edges.begin(), new_edges.end());
add_edges_sorted_internal(new_edges.begin(), new_edges.end());
}
+
+ // 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) {
+ 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>()));
+ }
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
using inherited_vertex_properties::operator[];
@@ -1244,6 +1301,17 @@
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);
+ }
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// From VertexListGraph
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-07-05 16:35:44 EDT (Sun, 05 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: 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-07-05 16:35:44 EDT (Sun, 05 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(),