LCOV - code coverage report
Current view: top level - neighbors - neighbors.hpp (source / functions) Hit Total Coverage
Test: clean.info Lines: 63 78 80.8 %
Date: 2013-05-24 Functions: 29 65 44.6 %
Branches: 226 1426 15.8 %

           Branch data     Line data    Source code
       1                 :            : /* This software is distributed under BSD 3-clause license (see LICENSE file).
       2                 :            :  *
       3                 :            :  * Copyright (c) 2012-2013 Sergey Lisitsyn, Fernando J. Iglesias Garcia
       4                 :            :  */
       5                 :            : 
       6                 :            : #ifndef TAPKEE_NEIGHBORS_H_
       7                 :            : #define TAPKEE_NEIGHBORS_H_
       8                 :            : 
       9                 :            : /* Tapkee includes */
      10                 :            : #include <tapkee/defines.hpp>
      11                 :            : #ifdef TAPKEE_USE_LGPL_COVERTREE
      12                 :            :         #include <tapkee/neighbors/covertree.hpp>
      13                 :            : #endif
      14                 :            : #include <tapkee/neighbors/connected.hpp>
      15                 :            : #include <tapkee/neighbors/vptree.hpp>
      16                 :            : /* End of Tapkee includes */
      17                 :            : 
      18                 :            : #include <vector>
      19                 :            : #include <utility>
      20                 :            : #include <algorithm>
      21                 :            : 
      22                 :            : namespace tapkee
      23                 :            : {
      24                 :            : namespace tapkee_internal
      25                 :            : {
      26                 :            : 
      27                 :            : template <class DistanceRecord>
      28                 :            : struct distances_comparator
      29                 :            : {
      30                 :      94602 :         inline bool operator()(const DistanceRecord& l, const DistanceRecord& r) const
      31                 :            :         {
      32                 :      94602 :                 return (l.second < r.second);
      33                 :            :         }
      34                 :            : };
      35                 :            : 
      36                 :            : struct KernelType 
      37                 :            : {
      38                 :            : };
      39                 :            : 
      40                 :            : template <class RandomAccessIterator, class Callback>
      41                 :            : struct KernelDistance
      42                 :            : {
      43                 :         41 :         KernelDistance(const Callback& cb) : callback(cb) {  } 
      44                 :      10157 :         inline ScalarType operator()(const RandomAccessIterator& l, const RandomAccessIterator& r)
      45                 :            :         {
      46                 :      10157 :                 return callback.kernel(*l,*r);
      47                 :            :         }
      48                 :      10000 :         inline ScalarType distance(const RandomAccessIterator& l, const RandomAccessIterator& r)
      49                 :            :         {
      50                 :      10000 :                 return sqrt(callback.kernel(*l,*l) - 2*callback.kernel(*l,*r) + callback.kernel(*r,*r));
      51                 :            :         }
      52                 :            :         typedef KernelType type;
      53                 :            :         Callback callback;
      54                 :            : };
      55                 :            : 
      56                 :            : struct DistanceType
      57                 :            : {
      58                 :            : };
      59                 :            : 
      60                 :            : template <class RandomAccessIterator, class Callback>
      61                 :            : struct PlainDistance
      62                 :            : {
      63                 :         41 :         PlainDistance(const Callback& cb) : callback(cb) {  }
      64                 :       8969 :         inline ScalarType operator()(const RandomAccessIterator& l, const RandomAccessIterator& r)
      65                 :            :         {
      66                 :       8969 :                 return callback.distance(*l,*r);
      67                 :            :         }
      68                 :      10000 :         inline ScalarType distance(const RandomAccessIterator& l, const RandomAccessIterator& r)
      69                 :            :         {
      70                 :      10000 :                 return callback.distance(*l,*r);
      71                 :            :         }
      72                 :            :         typedef DistanceType type;
      73                 :            :         Callback callback;
      74                 :            : };
      75                 :            : 
      76                 :            : #ifdef TAPKEE_USE_LGPL_COVERTREE
      77                 :            : template <class RandomAccessIterator, class Callback>
      78                 :         12 : Neighbors find_neighbors_covertree_impl(RandomAccessIterator begin, RandomAccessIterator end, 
      79                 :            :                          Callback callback, IndexType k)
      80                 :            : {
      81 [ +  - ][ +  - ]:         12 :         timed_context context("Covertree-based neighbors search");
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
      82                 :            : 
      83                 :            :         typedef CoverTreePoint<RandomAccessIterator> TreePoint;
      84                 :         12 :         v_array<TreePoint> points;
      85 [ +  + ][ +  + ]:        682 :         for (RandomAccessIterator iter=begin; iter!=end; ++iter)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
      86 [ +  - ][ -  # ]:        670 :                 push(points, TreePoint(iter, callback(iter,iter)));
         [ #  # ][ +  - ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ +  - ]
            [ +  - ][ + ]
         [ +  - ][ +  - ]
      87                 :            : 
      88 [ +  - ][ +  - ]:         12 :         node<TreePoint> ct = batch_create(callback, points);
         [ +  - ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
      89                 :            : 
      90                 :         12 :         v_array< v_array<TreePoint> > res;
      91                 :         12 :         ++k; // because one of the neighbors will be the actual query point
      92   [ +  -  +  -  :         12 :         k_nearest_neighbor(callback,ct,ct,res,k);
          +  -  #  #  #  
             #  #  #  #  
                      # ]
      93                 :            : 
      94 [ +  - ][ +  - ]:         12 :         Neighbors neighbors;
         [ +  - ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
      95 [ +  - ][ +  - ]:         12 :         neighbors.resize(end-begin);
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
            [ #  # ][ + ]
            [ + ][ +  - ]
         [ +  - ][ +  - ]
                 [ +  - ]
      96 [ -  + ][ -  + ]:         12 :         assert(end-begin==res.index);
         [ -  + ][ #  # ]
         [ #  # ][ #  # ]
            [ #  # ][ + ]
         [ -  + ][ +  - ]
      97 [ +  + ][ +  + ]:        682 :         for (int i=0; i<res.index; ++i)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
      98                 :            :         {
      99 [ +  - ][ +  - ]:        670 :                 LocalNeighbors local_neighbors;
         [ +  - ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     100 [ +  - ][ +  - ]:        670 :                 local_neighbors.reserve(k);
         [ +  - ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     101                 :            :                 
     102 [ +  + ][ +  + ]:       7940 :                 for (IndexType j=1; j<=k; ++j) // j=0 is the query point
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     103                 :            :                 {
     104                 :            :                         // The actual query point is found as a neighbor, just ignore it
     105 [ +  + ][ +  + ]:       7270 :                         if (res[i][j].iter_-begin==res[i][0].iter_-begin)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ +  - ]
         [ +  - ][ +  + ]
         [ +  - ][ +  - ]
                 [ +  + ]
     106                 :        669 :                                 continue;
     107 [ +  - ][ +  - ]:       6601 :                         local_neighbors.push_back(res[i][j].iter_-begin);
         [ +  - ][ #  # ]
         [ #  # ][ #  # ]
            [ #  # ][ + ]
         [ +  - ][ +  - ]
                 [ +  - ]
     108                 :            :                 }
     109 [ +  - ][ +  - ]:        670 :                 neighbors[res[i][0].iter_-begin] = local_neighbors;
         [ +  - ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ +  - ]
         [ +  - ][ +  - ]
                 [ +  - ]
     110 [ +  - ][ +  - ]:        670 :                 free(res[i].elements);
         [ +  - ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     111                 :            :         };
     112                 :         12 :         free(res.elements);
     113 [ +  - ][ +  - ]:         12 :         free_children(ct);
         [ +  - ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     114                 :         12 :         free(points.elements);
     115                 :         12 :         return neighbors;
     116                 :            : }
     117                 :            : #endif
     118                 :            : 
     119                 :            : template <class RandomAccessIterator, class Callback>
     120                 :          2 : Neighbors find_neighbors_bruteforce_impl(const RandomAccessIterator& begin, const RandomAccessIterator& end, 
     121                 :            :                                          Callback callback, IndexType k)
     122                 :            : {
     123 [ +  - ][ +  - ]:          2 :         timed_context context("Distance sorting based neighbors search");
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     124                 :            :         typedef std::pair<RandomAccessIterator, ScalarType> DistanceRecord;
     125                 :            :         typedef std::vector<DistanceRecord> Distances;
     126                 :            : 
     127   [ +  -  +  -  :          2 :         Neighbors neighbors;
          #  #  #  #  #  
             #  #  #  #  
                      # ]
     128 [ -  # ][ #  # ]:          2 :         neighbors.reserve(end-begin);
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
            [ #  # ][ + ]
         [ +  - ][ +  - ]
                 [ +  - ]
     129 [ +  + ][ +  + ]:        202 :         for (RandomAccessIterator iter=begin; iter!=end; ++iter)
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     130                 :            :         {
     131 [ +  - ][ +  - ]:        200 :                 Distances distances;
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     132 [ +  + ][ +  + ]:      20200 :                 for (RandomAccessIterator around_iter=begin; around_iter!=end; ++around_iter)
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     133 [ +  - ][ +  - ]:      20000 :                         distances.push_back(std::make_pair(around_iter, callback.distance(iter,around_iter)));
         [ #  + ][ #  + ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
          [ - ][ - ][ # ]
          [ # ][ # ][ # ]
            [ # ][ #  # ]
     134                 :            : 
     135 [ +  - ][ +  - ]:        200 :                 std::nth_element(distances.begin(),distances.begin()+k+1,distances.end(),
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     136                 :            :                                  distances_comparator<DistanceRecord>());
     137                 :            : 
     138 [ +  - ][ +  - ]:        200 :                 LocalNeighbors local_neighbors;
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     139 [ +  - ][ +  - ]:        200 :                 local_neighbors.reserve(k);
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     140 [ +  - ][ +  - ]:       2400 :                 for (typename Distances::const_iterator neighbors_iter=distances.begin(); 
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  + ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  + ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     141                 :            :                                 neighbors_iter!=distances.begin()+k+1; ++neighbors_iter)
     142                 :            :                 {
     143 [ +  + ][ +  + ]:       2200 :                         if (neighbors_iter->first != iter) 
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     144 [ -  # ][ #  # ]:       2000 :                                 local_neighbors.push_back(neighbors_iter->first - begin);
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
            [ #  # ][ + ]
         [ +  - ][ +  - ]
                 [ +  - ]
     145                 :            :                 }
     146 [ +  - ][ +  - ]:        200 :                 neighbors.push_back(local_neighbors);
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     147                 :            :         }
     148                 :          2 :         return neighbors;
     149                 :            : }
     150                 :            : 
     151                 :            : template <class RandomAccessIterator, class Callback>
     152                 :          0 : Neighbors find_neighbors_vptree_impl(const RandomAccessIterator& begin, const RandomAccessIterator& end, 
     153                 :            :                                      Callback callback, IndexType k)
     154                 :            : {
     155 [ #  # ][ #  # ]:          0 :         timed_context context("VP-Tree based neighbors search");
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     156                 :            : 
     157   [ #  #  #  #  :          0 :         Neighbors neighbors;
          #  #  #  #  #  
             #  #  #  #  
                      # ]
     158 [ #  # ][ #  # ]:          0 :         neighbors.reserve(end-begin);
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
            [ #  # ][ # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     159                 :            : 
     160 [ #  # ][ #  # ]:          0 :         VantagePointTree<RandomAccessIterator,Callback> tree(begin,end,callback);
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     161                 :            : 
     162 [ #  # ][ #  # ]:          0 :         for (RandomAccessIterator i=begin; i!=end; ++i)
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     163                 :            :         {
     164 [ #  # ][ #  # ]:          0 :                 LocalNeighbors local_neighbors = tree.search(i,k+1);
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     165 [ #  # ][ #  # ]:          0 :                 std::remove(local_neighbors.begin(),local_neighbors.end(),i-begin);
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
            [ #  # ][ # ]
               [ # ][ # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     166 [ #  # ][ #  # ]:          0 :                 neighbors.push_back(local_neighbors);
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     167                 :            :         }
     168                 :            : 
     169 [ #  # ][ #  # ]:          0 :         return neighbors;
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     170                 :            : }
     171                 :            : 
     172                 :            : template <class RandomAccessIterator, class Callback>
     173                 :         14 : Neighbors find_neighbors(NeighborsMethod method, const RandomAccessIterator& begin, 
     174                 :            :                          const RandomAccessIterator& end, const Callback& callback, 
     175                 :            :                          IndexType k, bool check_connectivity)
     176                 :            : {
     177 [ -  + ][ -  + ]:         14 :         if (k > static_cast<IndexType>(end-begin-1))
         [ -  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     178                 :            :         {
     179 [ #  # ][ #  # ]:          0 :                 LoggingSingleton::instance().message_warning("Number of neighbors is greater than number of objects to embed. "
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     180                 :            :                                                              "Using greatest possible number of neighbors.");
     181                 :          0 :                 k = static_cast<IndexType>(end-begin-1);
     182                 :            :         }
     183 [ +  - ][ +  - ]:         14 :         LoggingSingleton::instance().message_info("Using the " + get_neighbors_method_name(method) + " neighbors computation method.");
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     184                 :         14 :         Neighbors neighbors;
     185   [ +  -  +  -  :         14 :         switch (method)
          +  -  +  -  -  
          -  +  -  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
     186                 :            :         {
     187 [ +  - ][ +  - ]:          2 :                 case Brute: neighbors = find_neighbors_bruteforce_impl(begin,end,callback,k); break;
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     188 [ #  # ][ #  # ]:          0 :                 case VpTree: neighbors = find_neighbors_vptree_impl(begin,end,callback,k); break;
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     189                 :            : #ifdef TAPKEE_USE_LGPL_COVERTREE
     190 [ +  - ][ +  - ]:         12 :                 case CoverTree: neighbors = find_neighbors_covertree_impl(begin,end,callback,k); break;
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     191                 :            : #endif
     192                 :          0 :                 default: break;
     193                 :            :         }
     194                 :            : 
     195 [ +  - ][ +  - ]:         14 :         if (check_connectivity)
         [ +  - ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     196                 :            :         {
     197 [ +  - ][ -  + ]:         14 :                 if (!is_connected(begin,end,neighbors))
         [ +  - ][ -  + ]
         [ +  - ][ -  + ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     198 [ #  # ][ #  # ]:          0 :                         LoggingSingleton::instance().message_warning("The neighborhood graph is not connected.");
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     199                 :            :         }
     200                 :         14 :         return neighbors;
     201                 :            : }
     202                 :            : 
     203                 :            : } // End of namespace tapkee
     204                 :            : } // End of namespace tapkee_internal
     205                 :            : 
     206                 :            : #endif

Generated by: LCOV version 1.9