Changeset 54684


Ignore:
Timestamp:
Jul 5, 2009, 8:35:44 PM (9 years ago)
Author:
Jeremiah Willcock
Message:

Added add_edges() function with edge properties; refs #3134

Location:
trunk
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/boost/graph/compressed_sparse_row_graph.hpp

    r54596 r54684  
    2929#include <boost/iterator/counting_iterator.hpp>
    3030#include <boost/iterator/reverse_iterator.hpp>
     31#include <boost/iterator/zip_iterator.hpp>
     32#include <boost/iterator/transform_iterator.hpp>
     33#include <boost/tuple/tuple.hpp>
    3134#include <boost/property_map/property_map.hpp>
    3235#include <boost/integer.hpp>
     
    175178    void advance(typename base_type::difference_type) {}
    176179    typename base_type::difference_type distance_to(default_construct_iterator) const {return 0;}
     180  };
     181
     182  template <typename Less>
     183  struct compare_first {
     184    Less less;
     185    compare_first(Less less = Less()): less(less) {}
     186    template <typename Tuple>
     187    bool operator()(const Tuple& a, const Tuple& b) const {
     188      return less(a.template get<0>(), b.template get<0>());
     189    }
     190  };
     191
     192  template <int N, typename Result>
     193  struct my_tuple_get_class {
     194    typedef Result result_type;
     195    template <typename Tuple>
     196    result_type operator()(const Tuple& t) const {
     197      return t.template get<N>();
     198    }
    177199  };
    178200#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
     
    11031125    add_edges_sorted_internal(new_edges.begin(), new_edges.end());
    11041126  }
     1127
     1128  // Add edges from a range of (source, target) pairs and edge properties that
     1129  // are unsorted
     1130  template <typename InputIterator, typename EPIterator>
     1131  inline void
     1132  add_edges_internal(InputIterator first, InputIterator last,
     1133                     EPIterator ep_iter, EPIterator ep_iter_end) {
     1134    typedef compressed_sparse_row_graph Graph;
     1135    typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
     1136    typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num;
     1137    typedef typename boost::graph_traits<Graph>::edges_size_type edge_num;
     1138    typedef std::pair<vertex_t, vertex_t> vertex_pair;
     1139    typedef std::vector<
     1140              boost::tuple<vertex_pair,
     1141                           typename inherited_edge_properties::edge_bundled> >
     1142      edge_vector_t;
     1143    edge_vector_t new_edges
     1144      (boost::make_zip_iterator(boost::make_tuple(first, ep_iter)),
     1145       boost::make_zip_iterator(boost::make_tuple(last, ep_iter_end)));
     1146    if (new_edges.empty()) return;
     1147    std::sort(new_edges.begin(), new_edges.end(),
     1148              boost::detail::compare_first<
     1149                std::less<vertex_pair> >());
     1150    add_edges_sorted_internal
     1151      (boost::make_transform_iterator(
     1152         new_edges.begin(),
     1153         boost::detail::my_tuple_get_class<0, vertex_pair>()),
     1154       boost::make_transform_iterator(
     1155         new_edges.end(),
     1156         boost::detail::my_tuple_get_class<0, vertex_pair>()),
     1157       boost::make_transform_iterator(
     1158         new_edges.begin(),
     1159         boost::detail::my_tuple_get_class
     1160           <1, typename inherited_edge_properties::edge_bundled>()));
     1161  }
    11051162#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
    11061163
     
    12441301  add_edges(InputIterator first, InputIterator last, BOOST_CSR_GRAPH_TYPE& g) {
    12451302    g.add_edges_internal(first, last);
     1303  }
     1304
     1305  // Add edges from a range of (source, target) pairs and edge properties that
     1306  // are unsorted
     1307  template <BOOST_CSR_GRAPH_TEMPLATE_PARMS,
     1308            typename InputIterator, typename EPIterator>
     1309  inline void
     1310  add_edges(InputIterator first, InputIterator last,
     1311            EPIterator ep_iter, EPIterator ep_iter_end,
     1312            BOOST_CSR_GRAPH_TYPE& g) {
     1313    g.add_edges_internal(first, last, ep_iter, ep_iter_end);
    12461314  }
    12471315#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
  • trunk/libs/graph/doc/compressed_sparse_row.html

    r54316 r54684  
    296296
    297297<b>(new interface only)</b>
     298template&lt;typename InputIterator, typename EPIter, typename Graph&gt;
     299void <a href="#add_edges_prop">add_edges</a>(InputIterator first, InputIterator last, EPIter ep_first, EPIter ep_last, compressed_sparse_row_graph&amp; g);
     300
     301<b>(new interface only)</b>
    298302template&lt;typename BidirectionalIterator, typename Graph&gt;
    299303void <a href="#add_edges_sorted">add_edges_sorted</a>(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph&amp; g);
     
    942946    <hr></hr>
    943947
     948    <pre><a name="add_edges_prop"></a>
     949template&lt;typename InputIterator, typename EPIter&gt;
     950void add_edges(InputIterator first, InputIterator last, EPIter ep_first, EPIter ep_last, compressed_sparse_row_graph&amp; g)
     951    </pre>
     952   
     953    <p class="indent">
     954      Add a range of edges (from <tt>first</tt> to <tt>last</tt>) with
     955      corresponding edge properties (from <tt>ep_first</tt> to
     956      <tt>ep_last</tt>) to the graph.  The <tt>InputIterator</tt> and
     957      <tt>EPIter</tt> must be models of <a
     958      href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>;
     959      the <code>value_type</code> of <tt>InputIterator</tt> must be an
     960      <code>std::pair</code> of integer values, and the <code>value_type</code>
     961      of <tt>EPIter</tt> must be the edge property type of the graph. The
     962      integer values produced by the <tt>InputIterator</tt> are the source and
     963      target vertices of the new edges.  The edges do not need to be sorted.
     964      <b>(This function is only provided by the new interface.)</b>
     965    </p>
     966
     967    <hr></hr>
     968
    944969    <pre><a name="add_edges_sorted"></a>
    945970template&lt;typename BidirectionalIterator&gt;
  • trunk/libs/graph/test/csr_graph_test.cpp

    r54023 r54684  
    493493    CSRGraphT g3(boost::edges_are_unsorted, unsorted_edges, unsorted_edges, 6); // Empty range
    494494    add_edges(unsorted_edges, unsorted_edges + 3, g3);
    495     add_edges(unsorted_edges + 3, unsorted_edges + 6, g3);
     495    boost::no_property edge_data[3];
     496    add_edges(unsorted_edges + 3, unsorted_edges + 6, edge_data, edge_data + 3, g3);
    496497    graph_test(g3);
    497498    assert_graphs_equal(g, boost::identity_property_map(),
Note: See TracChangeset for help on using the changeset viewer.