123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293 |
- // Copyright 2009 The Trustees of Indiana University.
- // Distributed under the Boost Software License, Version 1.0.
- // (See accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- // Authors: Jeremiah Willcock
- // Andrew Lumsdaine
- #ifndef BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP
- #define BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP
- #include <boost/assert.hpp>
- namespace boost {
- namespace graph {
- namespace detail {
- template<typename InputIterator>
- size_t
- reserve_count_for_single_pass_helper(InputIterator, InputIterator,
- std::input_iterator_tag)
- {
- // Do nothing: we have no idea how much storage to reserve.
- return 0;
- }
- template<typename InputIterator>
- size_t
- reserve_count_for_single_pass_helper(InputIterator first, InputIterator last,
- std::random_access_iterator_tag)
- {
- using std::distance;
- typename std::iterator_traits<InputIterator>::difference_type n =
- distance(first, last);
- return (size_t)n;
- }
- template<typename InputIterator>
- size_t
- reserve_count_for_single_pass(InputIterator first, InputIterator last) {
- typedef typename std::iterator_traits<InputIterator>::iterator_category
- category;
- return reserve_count_for_single_pass_helper(first, last, category());
- }
- template <typename KeyIterator, typename RowstartIterator,
- typename VerticesSize, typename KeyFilter, typename KeyTransform>
- void
- count_starts
- (KeyIterator begin, KeyIterator end,
- RowstartIterator starts, // Must support numverts + 1 elements
- VerticesSize numkeys,
- KeyFilter key_filter,
- KeyTransform key_transform) {
- typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;
- // Put the degree of each vertex v into m_rowstart[v + 1]
- for (KeyIterator i = begin; i != end; ++i) {
- if (key_filter(*i)) {
- BOOST_ASSERT (key_transform(*i) < numkeys);
- ++starts[key_transform(*i) + 1];
- }
- }
- // Compute the partial sum of the degrees to get the actual values of
- // m_rowstart
- EdgeIndex start_of_this_row = 0;
- starts[0] = start_of_this_row;
- for (VerticesSize i = 1; i < numkeys + 1; ++i) {
- start_of_this_row += starts[i];
- starts[i] = start_of_this_row;
- }
- }
- template <typename KeyIterator, typename RowstartIterator,
- typename NumKeys,
- typename Value1InputIter,
- typename Value1OutputIter, typename KeyFilter, typename KeyTransform>
- void
- histogram_sort(KeyIterator key_begin, KeyIterator key_end,
- RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed
- NumKeys numkeys,
- Value1InputIter values1_begin,
- Value1OutputIter values1_out,
- KeyFilter key_filter,
- KeyTransform key_transform) {
- typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;
- // Histogram sort the edges by their source vertices, putting the targets
- // into m_column. The index current_insert_positions[v] contains the next
- // location to insert out edges for vertex v.
- std::vector<EdgeIndex>
- current_insert_positions(rowstart, rowstart + numkeys);
- Value1InputIter v1i = values1_begin;
- for (KeyIterator i = key_begin; i != key_end; ++i, ++v1i) {
- if (key_filter(*i)) {
- NumKeys source = key_transform(*i);
- BOOST_ASSERT (source < numkeys);
- EdgeIndex insert_pos = current_insert_positions[source];
- ++current_insert_positions[source];
- values1_out[insert_pos] = *v1i;
- }
- }
- }
- template <typename KeyIterator, typename RowstartIterator,
- typename NumKeys,
- typename Value1InputIter,
- typename Value1OutputIter,
- typename Value2InputIter,
- typename Value2OutputIter,
- typename KeyFilter, typename KeyTransform>
- void
- histogram_sort(KeyIterator key_begin, KeyIterator key_end,
- RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed
- NumKeys numkeys,
- Value1InputIter values1_begin,
- Value1OutputIter values1_out,
- Value2InputIter values2_begin,
- Value2OutputIter values2_out,
- KeyFilter key_filter,
- KeyTransform key_transform) {
- typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;
- // Histogram sort the edges by their source vertices, putting the targets
- // into m_column. The index current_insert_positions[v] contains the next
- // location to insert out edges for vertex v.
- std::vector<EdgeIndex>
- current_insert_positions(rowstart, rowstart + numkeys);
- Value1InputIter v1i = values1_begin;
- Value2InputIter v2i = values2_begin;
- for (KeyIterator i = key_begin; i != key_end; ++i, ++v1i, ++v2i) {
- if (key_filter(*i)) {
- NumKeys source = key_transform(*i);
- BOOST_ASSERT (source < numkeys);
- EdgeIndex insert_pos = current_insert_positions[source];
- ++current_insert_positions[source];
- values1_out[insert_pos] = *v1i;
- values2_out[insert_pos] = *v2i;
- }
- }
- }
- template <typename KeyIterator, typename RowstartIterator,
- typename NumKeys,
- typename Value1Iter,
- typename KeyTransform>
- void
- histogram_sort_inplace(KeyIterator key_begin,
- RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed
- NumKeys numkeys,
- Value1Iter values1,
- KeyTransform key_transform) {
- typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;
- // 1. Copy m_rowstart (except last element) to get insert positions
- std::vector<EdgeIndex> insert_positions(rowstart, rowstart + numkeys);
- // 2. Swap the sources and targets into place
- for (size_t i = 0; i < rowstart[numkeys]; ++i) {
- BOOST_ASSERT (key_transform(key_begin[i]) < numkeys);
- // While edge i is not in the right bucket:
- while (!(i >= rowstart[key_transform(key_begin[i])] && i < insert_positions[key_transform(key_begin[i])])) {
- // Add a slot in the right bucket
- size_t target_pos = insert_positions[key_transform(key_begin[i])]++;
- BOOST_ASSERT (target_pos < rowstart[key_transform(key_begin[i]) + 1]);
- if (target_pos == i) continue;
- // Swap this edge into place
- using std::swap;
- swap(key_begin[i], key_begin[target_pos]);
- swap(values1[i], values1[target_pos]);
- }
- }
- }
- template <typename KeyIterator, typename RowstartIterator,
- typename NumKeys,
- typename Value1Iter,
- typename Value2Iter,
- typename KeyTransform>
- void
- histogram_sort_inplace(KeyIterator key_begin,
- RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed
- NumKeys numkeys,
- Value1Iter values1,
- Value2Iter values2,
- KeyTransform key_transform) {
- typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;
- // 1. Copy m_rowstart (except last element) to get insert positions
- std::vector<EdgeIndex> insert_positions(rowstart, rowstart + numkeys);
- // 2. Swap the sources and targets into place
- for (size_t i = 0; i < rowstart[numkeys]; ++i) {
- BOOST_ASSERT (key_transform(key_begin[i]) < numkeys);
- // While edge i is not in the right bucket:
- while (!(i >= rowstart[key_transform(key_begin[i])] && i < insert_positions[key_transform(key_begin[i])])) {
- // Add a slot in the right bucket
- size_t target_pos = insert_positions[key_transform(key_begin[i])]++;
- BOOST_ASSERT (target_pos < rowstart[key_transform(key_begin[i]) + 1]);
- if (target_pos == i) continue;
- // Swap this edge into place
- using std::swap;
- swap(key_begin[i], key_begin[target_pos]);
- swap(values1[i], values1[target_pos]);
- swap(values2[i], values2[target_pos]);
- }
- }
- }
- template <typename InputIterator, typename VerticesSize>
- void split_into_separate_coords(InputIterator begin, InputIterator end,
- std::vector<VerticesSize>& firsts,
- std::vector<VerticesSize>& seconds) {
- firsts.clear();
- seconds.clear();
- size_t reserve_size
- = detail::reserve_count_for_single_pass(begin, end);
- firsts.reserve(reserve_size);
- seconds.reserve(reserve_size);
- for (; begin != end; ++begin) {
- std::pair<VerticesSize, VerticesSize> edge = *begin;
- firsts.push_back(edge.first);
- seconds.push_back(edge.second);
- }
- }
- template <typename InputIterator, typename VerticesSize, typename SourceFilter>
- void split_into_separate_coords_filtered
- (InputIterator begin, InputIterator end,
- std::vector<VerticesSize>& firsts,
- std::vector<VerticesSize>& seconds,
- const SourceFilter& filter) {
- firsts.clear();
- seconds.clear();
- for (; begin != end; ++begin) {
- std::pair<VerticesSize, VerticesSize> edge = *begin;
- if (filter(edge.first)) {
- firsts.push_back(edge.first);
- seconds.push_back(edge.second);
- }
- }
- }
- template <typename InputIterator, typename PropInputIterator,
- typename VerticesSize, typename PropType, typename SourceFilter>
- void split_into_separate_coords_filtered
- (InputIterator begin, InputIterator end,
- PropInputIterator props,
- std::vector<VerticesSize>& firsts,
- std::vector<VerticesSize>& seconds,
- std::vector<PropType>& props_out,
- const SourceFilter& filter) {
- firsts.clear();
- seconds.clear();
- props_out.clear();
- for (; begin != end; ++begin) {
- std::pair<VerticesSize, VerticesSize> edge = *begin;
- if (filter(edge.first)) {
- firsts.push_back(edge.first);
- seconds.push_back(edge.second);
- props_out.push_back(*props);
- }
- ++props;
- }
- }
- // The versions of operator()() here can't return by reference because the
- // actual type passed in may not match Pair, in which case the reference
- // parameter is bound to a temporary that could end up dangling after the
- // operator returns.
- template <typename Pair>
- struct project1st {
- typedef typename Pair::first_type result_type;
- result_type operator()(const Pair& p) const {return p.first;}
- };
- template <typename Pair>
- struct project2nd {
- typedef typename Pair::second_type result_type;
- result_type operator()(const Pair& p) const {return p.second;}
- };
- }
- }
- }
- #endif // BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP
|