GreedyKCenters.h
1 /*********************************************************************
2 * Software License Agreement (BSD License)
3 *
4 * Copyright (c) 2011, Rice University
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
17 * * Neither the name of the Rice University nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
33 *********************************************************************/
34 
35 /* Author: Mark Moll */
36 
37 #ifndef OMPL_DATASTRUCTURES_GREEDY_K_CENTERS_
38 #define OMPL_DATASTRUCTURES_GREEDY_K_CENTERS_
39 
40 #include "ompl/util/RandomNumbers.h"
41 #include <functional>
42 #include <boost/numeric/ublas/matrix.hpp>
43 
44 namespace ompl
45 {
49  template <typename _T>
51  {
52  public:
54  using DistanceFunction = std::function<double(const _T &, const _T &)>;
56  using Matrix = boost::numeric::ublas::matrix<double>;
57 
58  GreedyKCenters() = default;
59 
60  virtual ~GreedyKCenters() = default;
61 
64  {
65  distFun_ = distFun;
66  }
67 
70  {
71  return distFun_;
72  }
73 
82  void kcenters(const std::vector<_T> &data, unsigned int k, std::vector<unsigned int> &centers, Matrix &dists)
83  {
84  // array containing the minimum distance between each data point
85  // and the centers computed so far
86  std::vector<double> minDist(data.size(), std::numeric_limits<double>::infinity());
87 
88  centers.clear();
89  centers.reserve(k);
90  if (dists.size1() < data.size() || dists.size2() < k)
91  dists.resize(std::max(2 * dists.size1() + 1, data.size()), k, false);
92  // first center is picked randomly
93  centers.push_back(rng_.uniformInt(0, data.size() - 1));
94  for (unsigned i = 1; i < k; ++i)
95  {
96  unsigned ind;
97  const _T &center = data[centers[i - 1]];
98  double maxDist = -std::numeric_limits<double>::infinity();
99  for (unsigned j = 0; j < data.size(); ++j)
100  {
101  if ((dists(j, i - 1) = distFun_(data[j], center)) < minDist[j])
102  minDist[j] = dists(j, i - 1);
103  // the j-th center is the one furthest away from center 0,..,j-1
104  if (minDist[j] > maxDist)
105  {
106  ind = j;
107  maxDist = minDist[j];
108  }
109  }
110  // no more centers available
111  if (maxDist < std::numeric_limits<double>::epsilon())
112  break;
113  centers.push_back(ind);
114  }
115 
116  const _T &center = data[centers.back()];
117  unsigned i = centers.size() - 1;
118  for (unsigned j = 0; j < data.size(); ++j)
119  dists(j, i) = distFun_(data[j], center);
120  }
121 
122  protected:
125 
128  };
129 }
130 
131 #endif
DistanceFunction distFun_
The used distance function.
An instance of this class can be used to greedily select a given number of representatives from a set...
Main namespace. Contains everything in this library.
Definition: AppBase.h:21
Random number generation. An instance of this class cannot be used by multiple threads at once (membe...
Definition: RandomNumbers.h:58
const DistanceFunction & getDistanceFunction() const
Get the distance function used.
void kcenters(const std::vector< _T > &data, unsigned int k, std::vector< unsigned int > &centers, Matrix &dists)
Greedy algorithm for selecting k centers.
void setDistanceFunction(const DistanceFunction &distFun)
Set the distance function to use.
int uniformInt(int lower_bound, int upper_bound)
Generate a random integer within given bounds: [lower_bound, upper_bound].
Definition: RandomNumbers.h:81
boost::numeric::ublas::matrix< double > Matrix
A matrix type for storing distances between points and centers.
std::function< double(const _T &, const _T &)> DistanceFunction
The definition of a distance function.