6 #ifndef TAPKEE_Isomap_H_
7 #define TAPKEE_Isomap_H_
20 namespace tapkee_internal
23 #ifdef TAPKEE_USE_PRIORITY_QUEUE
24 typedef std::pair<IndexType,ScalarType> HeapElement;
26 struct HeapElementComparator
28 inline bool operator()(
const HeapElement& l,
const HeapElement& r)
const
30 return l.second > r.second;
43 template <
class RandomAccessIterator,
class DistanceCallback>
45 const Neighbors& neighbors, DistanceCallback callback)
48 const IndexType n_neighbors = neighbors[0].size();
53 #pragma omp parallel shared(shortest_distances,neighbors,begin,callback) default(none)
55 bool* f =
new bool[N];
56 bool* s =
new bool[N];
59 #ifdef TAPKEE_USE_PRIORITY_QUEUE
65 #pragma omp for nowait
71 shortest_distances(k,j) = std::numeric_limits<DenseMatrix::Scalar>::max();
76 shortest_distances(k,k) = 0.0;
79 #ifdef TAPKEE_USE_PRIORITY_QUEUE
80 HeapElement heap_element_of_self(k,0.0);
81 heap.push(heap_element_of_self);
91 #ifdef TAPKEE_USE_PRIORITY_QUEUE
92 int min_item = heap.top().first;
95 if (min_item_d > shortest_distances(k,min_item))
109 int w = neighbors[min_item][i];
114 ScalarType dist = shortest_distances(k,min_item) + callback.distance(begin[min_item],begin[w]);
116 if (dist < shortest_distances(k,w))
119 shortest_distances(k,w) = dist;
120 #ifdef TAPKEE_USE_PRIORITY_QUEUE
121 HeapElement relaxed_heap_element(w,dist);
122 heap.push(relaxed_heap_element);
148 return shortest_distances;
160 template <
class RandomAccessIterator,
class DistanceCallback>
165 const IndexType n_neighbors = neighbors[0].size();
167 const IndexType N_landmarks = landmarks.size();
169 DenseMatrix shortest_distances(landmarks.size(),N);
171 #pragma omp parallel shared(shortest_distances,begin,landmarks,neighbors,callback) default(none)
173 bool* f =
new bool[N];
174 bool* s =
new bool[N];
177 #ifdef TAPKEE_USE_PRIORITY_QUEUE
183 #pragma omp for nowait
184 for (k=0; k<N_landmarks; k++)
189 shortest_distances(k,j) = std::numeric_limits<DenseMatrix::Scalar>::max();
194 shortest_distances(k,landmarks[k]) = 0.0;
197 #ifdef TAPKEE_USE_PRIORITY_QUEUE
198 HeapElement heap_element_of_self(landmarks[k],0.0);
199 heap.push(heap_element_of_self);
201 heap.
insert(landmarks[k],0.0);
206 while (!heap.
empty())
209 #ifdef TAPKEE_USE_PRIORITY_QUEUE
210 int min_item = heap.top().first;
213 if (min_item_d > shortest_distances(k,min_item))
227 int w = neighbors[min_item][i];
232 ScalarType dist = shortest_distances(k,min_item) + callback.distance(begin[min_item],begin[w]);
234 if (dist < shortest_distances(k,w))
237 shortest_distances(k,w) = dist;
238 #ifdef TAPKEE_USE_PRIORITY_QUEUE
239 HeapElement relaxed_heap_element(w,dist);
240 heap.push(relaxed_heap_element);
266 return shortest_distances;
Eigen::Matrix< tapkee::ScalarType, Eigen::Dynamic, Eigen::Dynamic > DenseMatrix
dense matrix type (non-overridable)
int extract_min(ScalarType &ret_key)
double ScalarType
default scalar value (can be overrided with TAPKEE_CUSTOM_INTERNAL_NUMTYPE define) ...
DenseSymmetricMatrix compute_shortest_distances_matrix(const RandomAccessIterator &begin, const RandomAccessIterator &end, const Neighbors &neighbors, DistanceCallback callback)
Computes shortest distances (so-called geodesic distances) using Dijkstra algorithm.
int IndexType
indexing type (non-overridable) set to int for compatibility with OpenMP 2.0
void decrease_key(int index, ScalarType &key)
void insert(int index, ScalarType key)
TAPKEE_INTERNAL_VECTOR< tapkee::tapkee_internal::LocalNeighbors > Neighbors
the class fibonacci_heap, a fibonacci heap. Generally used by Isomap for Dijkstra heap algorithm ...
TAPKEE_INTERNAL_VECTOR< tapkee::IndexType > Landmarks
tapkee::DenseMatrix DenseSymmetricMatrix
dense symmetric matrix (non-overridable, currently just dense matrix, can be improved later) ...