6 #ifndef TAPKEE_NEIGHBORS_H_ 7 #define TAPKEE_NEIGHBORS_H_ 11 #ifdef TAPKEE_USE_LGPL_COVERTREE 24 namespace tapkee_internal
27 template <
class DistanceRecord>
30 inline bool operator()(
const DistanceRecord& l,
const DistanceRecord& r)
const 32 return (l.second < r.second);
40 template <
class RandomAccessIterator,
class Callback>
46 return callback.kernel(*l,*r);
50 return sqrt(callback.kernel(*l,*l) - 2*callback.kernel(*l,*r) + callback.kernel(*r,*r));
60 template <
class RandomAccessIterator,
class Callback>
66 return callback.distance(*l,*r);
70 return callback.distance(*l,*r);
76 #ifdef TAPKEE_USE_LGPL_COVERTREE 77 template <
class RandomAccessIterator,
class Callback>
85 for (RandomAccessIterator iter=begin; iter!=end; ++iter)
86 push(points, TreePoint(iter, callback(iter,iter)));
95 neighbors.resize(end-begin);
96 assert(end-begin==res.
index);
97 for (
int i=0; i<res.
index; ++i)
100 local_neighbors.reserve(k);
105 if (res[i][j].iter_-begin==res[i][0].iter_-begin)
107 local_neighbors.push_back(res[i][j].iter_-begin);
109 neighbors[res[i][0].iter_-begin] = local_neighbors;
110 free(res[i].elements);
119 template <
class RandomAccessIterator,
class Callback>
123 timed_context context(
"Distance sorting based neighbors search");
124 typedef std::pair<RandomAccessIterator, ScalarType> DistanceRecord;
125 typedef std::vector<DistanceRecord> Distances;
128 neighbors.reserve(end-begin);
129 for (RandomAccessIterator iter=begin; iter!=end; ++iter)
132 for (RandomAccessIterator around_iter=begin; around_iter!=end; ++around_iter)
133 distances.push_back(std::make_pair(around_iter, callback.distance(iter,around_iter)));
135 std::nth_element(distances.begin(),distances.begin()+k+1,distances.end(),
139 local_neighbors.reserve(k);
140 for (
typename Distances::const_iterator neighbors_iter=distances.begin();
141 neighbors_iter!=distances.begin()+k+1; ++neighbors_iter)
143 if (neighbors_iter->first != iter)
144 local_neighbors.push_back(neighbors_iter->first - begin);
146 neighbors.push_back(local_neighbors);
151 template <
class RandomAccessIterator,
class Callback>
158 neighbors.reserve(end-begin);
162 for (RandomAccessIterator i=begin; i!=end; ++i)
165 std::remove(local_neighbors.begin(),local_neighbors.end(),i-begin);
166 neighbors.push_back(local_neighbors);
172 template <
class RandomAccessIterator,
class Callback>
174 const RandomAccessIterator& end,
const Callback& callback,
177 if (k > static_cast<IndexType>(end-begin-1))
180 "Using greatest possible number of neighbors.");
190 #ifdef TAPKEE_USE_LGPL_COVERTREE 195 if (check_connectivity)
ScalarType distance(const RandomAccessIterator &l, const RandomAccessIterator &r)
bool operator()(const DistanceRecord &l, const DistanceRecord &r) const
Neighbors find_neighbors(NeighborsMethod method, const RandomAccessIterator &begin, const RandomAccessIterator &end, const Callback &callback, IndexType k, bool check_connectivity)
void k_nearest_neighbor(DistanceCallback &dcb, const node< P > &top_node, const node< P > &query, v_array< v_array< P > > &results, int k)
ScalarType operator()(const RandomAccessIterator &l, const RandomAccessIterator &r)
node< P > batch_create(DistanceCallback &dcb, v_array< P > points)
ScalarType distance(const RandomAccessIterator &l, const RandomAccessIterator &r)
static const NeighborsMethod Brute("Brute-force")
Brute force method with not least than time complexity. Recommended to be used only in debug purpose...
Class v_array taken directly from JL's implementation.
Neighbors find_neighbors_covertree_impl(RandomAccessIterator begin, RandomAccessIterator end, Callback callback, IndexType k)
double ScalarType
default scalar value (can be overrided with TAPKEE_CUSTOM_INTERNAL_NUMTYPE define) ...
void free_children(const node< P > &n)
TAPKEE_INTERNAL_VECTOR< tapkee::IndexType > LocalNeighbors
int IndexType
indexing type (non-overridable) set to int for compatibility with OpenMP 2.0
ScalarType operator()(const RandomAccessIterator &l, const RandomAccessIterator &r)
void push(v_array< T > &v, const T &new_ele)
PlainDistance(const Callback &cb)
void message_info(const std::string &msg)
TAPKEE_INTERNAL_VECTOR< tapkee::tapkee_internal::LocalNeighbors > Neighbors
Neighbors find_neighbors_vptree_impl(const RandomAccessIterator &begin, const RandomAccessIterator &end, Callback callback, IndexType k)
bool is_connected(RandomAccessIterator begin, RandomAccessIterator end, const Neighbors &neighbors)
void message_warning(const std::string &msg)
static LoggingSingleton & instance()
std::vector< IndexType > search(const RandomAccessIterator &target, int k)
Class Point to use with John Langford's CoverTree. This class must have some associated functions def...
std::string get_neighbors_method_name(const NeighborsMethod &m)
static const NeighborsMethod VpTree("Vantage point tree")
Vantage point tree -based method.
KernelDistance(const Callback &cb)
bool is(const M &m) const
static const NeighborsMethod CoverTree("Cover tree")
Covertree-based method with approximate time complexity. Recommended to be used as a default method...
Neighbors find_neighbors_bruteforce_impl(const RandomAccessIterator &begin, const RandomAccessIterator &end, Callback callback, IndexType k)