graph/detail/histogram_sort.hpp

0001 // Copyright 2009 The Trustees of Indiana University.
0002
0003 // Distributed under the Boost Software License, Version 1.0.
0004 // (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Jeremiah Willcock
0008 //           Andrew Lumsdaine
0009
0010 #ifndef BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP
0011 #define BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP
0012
0013 #include <boost/assert.hpp>
0014
0015 namespace boost
0016 {
0017 namespace graph
0018 {
0019     namespace detail
0020     {
0021
0022         template < typename InputIterator >
0023         size_t reserve_count_for_single_pass_helper(
0024             InputIterator, InputIterator, std::input_iterator_tag)
0025         {
0026             // Do nothing: we have no idea how much storage to reserve.
0027             return 0;
0028         }
0029
0030         template < typename InputIterator >
0031         size_t reserve_count_for_single_pass_helper(InputIterator first,
0032             InputIterator last, std::random_access_iterator_tag)
0033         {
0034             using std::distance;
0035             typename std::iterator_traits< InputIterator >::difference_type n
0036                 = distance(first, last);
0037             return (size_t)n;
0038         }
0039
0040         template < typename InputIterator >
0041         size_t reserve_count_for_single_pass(
0042             InputIterator first, InputIterator last)
0043         {
0044             typedef typename std::iterator_traits<
0045                 InputIterator >::iterator_category category;
0046             return reserve_count_for_single_pass_helper(
0047                 first, last, category());
0048         }
0049
0050         template < typename KeyIterator, typename RowstartIterator,
0051             typename VerticesSize, typename KeyFilter, typename KeyTransform >
0052         void count_starts(KeyIterator begin, KeyIterator end,
0053             RowstartIterator starts, // Must support numverts + 1 elements
0054             VerticesSize numkeys, KeyFilter key_filter,
0055             KeyTransform key_transform)
0056         {
0057
0058             typedef
0059                 typename std::iterator_traits< RowstartIterator >::value_type
0060                     EdgeIndex;
0061
0062             // Put the degree of each vertex v into m_rowstart[v + 1]
0063             for (KeyIterator i = begin; i != end; ++i)
0064             {
0065                 if (key_filter(*i))
0066                 {
0067                     BOOST_ASSERT(key_transform(*i) < numkeys);
0068                     ++starts[key_transform(*i) + 1];
0069                 }
0070             }
0071
0072             // Compute the partial sum of the degrees to get the actual values
0073             // of m_rowstart
0074             EdgeIndex start_of_this_row = 0;
0075             starts[0] = start_of_this_row;
0076             for (VerticesSize i = 1; i < numkeys + 1; ++i)
0077             {
0078                 start_of_this_row += starts[i];
0079                 starts[i] = start_of_this_row;
0080             }
0081         }
0082
0083         template < typename KeyIterator, typename RowstartIterator,
0084             typename NumKeys, typename Value1InputIter,
0085             typename Value1OutputIter, typename KeyFilter,
0086             typename KeyTransform >
0087         void histogram_sort(KeyIterator key_begin, KeyIterator key_end,
0088             RowstartIterator rowstart, // Must support numkeys + 1 elements and
0089                                        // be precomputed
0090             NumKeys numkeys, Value1InputIter values1_begin,
0091             Value1OutputIter values1_out, KeyFilter key_filter,
0092             KeyTransform key_transform)
0093         {
0094
0095             typedef
0096                 typename std::iterator_traits< RowstartIterator >::value_type
0097                     EdgeIndex;
0098
0099             // Histogram sort the edges by their source vertices, putting the
0100             // targets into m_column.  The index current_insert_positions[v]
0101             // contains the next location to insert out edges for vertex v.
0102             std::vector< EdgeIndex > current_insert_positions(
0103                 rowstart, rowstart + numkeys);
0104             Value1InputIter v1i = values1_begin;
0105             for (KeyIterator i = key_begin; i != key_end; ++i, ++v1i)
0106             {
0107                 if (key_filter(*i))
0108                 {
0109                     NumKeys source = key_transform(*i);
0110                     BOOST_ASSERT(source < numkeys);
0111                     EdgeIndex insert_pos = current_insert_positions[source];
0112                     ++current_insert_positions[source];
0113                     values1_out[insert_pos] = *v1i;
0114                 }
0115             }
0116         }
0117
0118         template < typename KeyIterator, typename RowstartIterator,
0119             typename NumKeys, typename Value1InputIter,
0120             typename Value1OutputIter, typename Value2InputIter,
0121             typename Value2OutputIter, typename KeyFilter,
0122             typename KeyTransform >
0123         void histogram_sort(KeyIterator key_begin, KeyIterator key_end,
0124             RowstartIterator rowstart, // Must support numkeys + 1 elements and
0125                                        // be precomputed
0126             NumKeys numkeys, Value1InputIter values1_begin,
0127             Value1OutputIter values1_out, Value2InputIter values2_begin,
0128             Value2OutputIter values2_out, KeyFilter key_filter,
0129             KeyTransform key_transform)
0130         {
0131
0132             typedef
0133                 typename std::iterator_traits< RowstartIterator >::value_type
0134                     EdgeIndex;
0135
0136             // Histogram sort the edges by their source vertices, putting the
0137             // targets into m_column.  The index current_insert_positions[v]
0138             // contains the next location to insert out edges for vertex v.
0139             std::vector< EdgeIndex > current_insert_positions(
0140                 rowstart, rowstart + numkeys);
0141             Value1InputIter v1i = values1_begin;
0142             Value2InputIter v2i = values2_begin;
0143             for (KeyIterator i = key_begin; i != key_end; ++i, ++v1i, ++v2i)
0144             {
0145                 if (key_filter(*i))
0146                 {
0147                     NumKeys source = key_transform(*i);
0148                     BOOST_ASSERT(source < numkeys);
0149                     EdgeIndex insert_pos = current_insert_positions[source];
0150                     ++current_insert_positions[source];
0151                     values1_out[insert_pos] = *v1i;
0152                     values2_out[insert_pos] = *v2i;
0153                 }
0154             }
0155         }
0156
0157         template < typename KeyIterator, typename RowstartIterator,
0158             typename NumKeys, typename Value1Iter, typename KeyTransform >
0159         void histogram_sort_inplace(KeyIterator key_begin,
0160             RowstartIterator rowstart, // Must support numkeys + 1 elements and
0161                                        // be precomputed
0162             NumKeys numkeys, Value1Iter values1, KeyTransform key_transform)
0163         {
0164
0165             typedef
0166                 typename std::iterator_traits< RowstartIterator >::value_type
0167                     EdgeIndex;
0168
0169             // 1. Copy m_rowstart (except last element) to get insert positions
0170             std::vector< EdgeIndex > insert_positions(
0171                 rowstart, rowstart + numkeys);
0172             // 2. Swap the sources and targets into place
0173             for (size_t i = 0; i < rowstart[numkeys]; ++i)
0174             {
0175                 BOOST_ASSERT(key_transform(key_begin[i]) < numkeys);
0176                 // While edge i is not in the right bucket:
0177                 while (!(i >= rowstart[key_transform(key_begin[i])]
0178                     && i < insert_positions[key_transform(key_begin[i])]))
0179                 {
0180                     // Add a slot in the right bucket
0181                     size_t target_pos
0182                         = insert_positions[key_transform(key_begin[i])]++;
0183                     BOOST_ASSERT(
0184                         target_pos < rowstart[key_transform(key_begin[i]) + 1]);
0185                     if (target_pos == i)
0186                         continue;
0187                     // Swap this edge into place
0188                     using std::swap;
0189                     swap(key_begin[i], key_begin[target_pos]);
0190                     swap(values1[i], values1[target_pos]);
0191                 }
0192             }
0193         }
0194
0195         template < typename KeyIterator, typename RowstartIterator,
0196             typename NumKeys, typename Value1Iter, typename Value2Iter,
0197             typename KeyTransform >
0198         void histogram_sort_inplace(KeyIterator key_begin,
0199             RowstartIterator rowstart, // Must support numkeys + 1 elements and
0200                                        // be precomputed
0201             NumKeys numkeys, Value1Iter values1, Value2Iter values2,
0202             KeyTransform key_transform)
0203         {
0204
0205             typedef
0206                 typename std::iterator_traits< RowstartIterator >::value_type
0207                     EdgeIndex;
0208
0209             // 1. Copy m_rowstart (except last element) to get insert positions
0210             std::vector< EdgeIndex > insert_positions(
0211                 rowstart, rowstart + numkeys);
0212             // 2. Swap the sources and targets into place
0213             for (size_t i = 0; i < rowstart[numkeys]; ++i)
0214             {
0215                 BOOST_ASSERT(key_transform(key_begin[i]) < numkeys);
0216                 // While edge i is not in the right bucket:
0217                 while (!(i >= rowstart[key_transform(key_begin[i])]
0218                     && i < insert_positions[key_transform(key_begin[i])]))
0219                 {
0220                     // Add a slot in the right bucket
0221                     size_t target_pos
0222                         = insert_positions[key_transform(key_begin[i])]++;
0223                     BOOST_ASSERT(
0224                         target_pos < rowstart[key_transform(key_begin[i]) + 1]);
0225                     if (target_pos == i)
0226                         continue;
0227                     // Swap this edge into place
0228                     using std::swap;
0229                     swap(key_begin[i], key_begin[target_pos]);
0230                     swap(values1[i], values1[target_pos]);
0231                     swap(values2[i], values2[target_pos]);
0232                 }
0233             }
0234         }
0235
0236         template < typename InputIterator, typename VerticesSize >
0237         void split_into_separate_coords(InputIterator begin, InputIterator end,
0238             std::vector< VerticesSize >& firsts,
0239             std::vector< VerticesSize >& seconds)
0240         {
0241             firsts.clear();
0242             seconds.clear();
0243             size_t reserve_size
0244                 = detail::reserve_count_for_single_pass(begin, end);
0245             firsts.reserve(reserve_size);
0246             seconds.reserve(reserve_size);
0247             for (; begin != end; ++begin)
0248             {
0249                 std::pair< VerticesSize, VerticesSize > edge = *begin;
0250                 firsts.push_back(edge.first);
0251                 seconds.push_back(edge.second);
0252             }
0253         }
0254
0255         template < typename InputIterator, typename VerticesSize,
0256             typename SourceFilter >
0257         void split_into_separate_coords_filtered(InputIterator begin,
0258             InputIterator end, std::vector< VerticesSize >& firsts,
0259             std::vector< VerticesSize >& seconds, const SourceFilter& filter)
0260         {
0261             firsts.clear();
0262             seconds.clear();
0263             for (; begin != end; ++begin)
0264             {
0265                 std::pair< VerticesSize, VerticesSize > edge = *begin;
0266                 if (filter(edge.first))
0267                 {
0268                     firsts.push_back(edge.first);
0269                     seconds.push_back(edge.second);
0270                 }
0271             }
0272         }
0273
0274         template < typename InputIterator, typename PropInputIterator,
0275             typename VerticesSize, typename PropType, typename SourceFilter >
0276         void split_into_separate_coords_filtered(InputIterator begin,
0277             InputIterator end, PropInputIterator props,
0278             std::vector< VerticesSize >& firsts,
0279             std::vector< VerticesSize >& seconds,
0280             std::vector< PropType >& props_out, const SourceFilter& filter)
0281         {
0282             firsts.clear();
0283             seconds.clear();
0284             props_out.clear();
0285             for (; begin != end; ++begin)
0286             {
0287                 std::pair< VerticesSize, VerticesSize > edge = *begin;
0288                 if (filter(edge.first))
0289                 {
0290                     firsts.push_back(edge.first);
0291                     seconds.push_back(edge.second);
0292                     props_out.push_back(*props);
0293                 }
0294                 ++props;
0295             }
0296         }
0297
0298         // The versions of operator()() here can't return by reference because
0299         // the actual type passed in may not match Pair, in which case the
0300         // reference parameter is bound to a temporary that could end up
0301         // dangling after the operator returns.
0302
0303         template < typename Pair > struct project1st
0304         {
0305             typedef typename Pair::first_type result_type;
0306             result_type operator()(const Pair& p) const { return p.first; }
0307         };
0308
0309         template < typename Pair > struct project2nd
0310         {
0311             typedef typename Pair::second_type result_type;
0312             result_type operator()(const Pair& p) const { return p.second; }
0313         };
0314
0315     }
0316 }
0317 }
0318
0319 #endif // BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP