boost/graph/detail/histogram_sort.hpp
// 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