OpenMS
GridBasedClustering.h
Go to the documentation of this file.
1 // Copyright (c) 2002-present, OpenMS Inc. -- EKU Tuebingen, ETH Zurich, and FU Berlin
2 // SPDX-License-Identifier: BSD-3-Clause
3 //
4 // --------------------------------------------------------------------------
5 // $Maintainer: Lars Nilse $
6 // $Authors: Lars Nilse, Johannes Veit $
7 // --------------------------------------------------------------------------
8 
9 #pragma once
10 
17 
18 #include <cmath>
19 #include <limits>
20 #include <map>
21 #include <set>
22 #include <queue>
23 #include <vector>
24 #include <algorithm>
25 #include <iostream>
26 #include <unordered_map>
27 
28 namespace OpenMS
29 {
30 
34  class OPENMS_DLLAPI MinimumDistance
35  {
36 public:
37 
41  MinimumDistance(const int& cluster_index, const int& nearest_neighbour_index, const double& distance);
42 
46  int getClusterIndex() const;
47 
52 
57  bool operator<(const MinimumDistance& other) const;
58  bool operator>(const MinimumDistance& other) const;
59  bool operator==(const MinimumDistance& other) const;
60 
61 private:
62 
65 
70 
75 
79  double distance_;
80 
81  };
82 
98  template <typename Metric>
100  public ProgressLogger
101  {
102 public:
106  typedef GridBasedCluster::Point Point; // DPosition<2>
107  typedef GridBasedCluster::Rectangle Rectangle; // DBoundingBox<2>
108  typedef ClusteringGrid::CellIndex CellIndex; // std::pair<int,int>
109  typedef std::multiset<MinimumDistance>::const_iterator MultisetIterator;
110  typedef std::unordered_multimap<int, MultisetIterator>::const_iterator NNIterator;
111 
123  GridBasedClustering(Metric metric, const std::vector<double>& data_x,
124  const std::vector<double>& data_y, const std::vector<int>& properties_A,
125  const std::vector<int>& properties_B, std::vector<double> grid_spacing_x,
126  std::vector<double> grid_spacing_y) :
127  metric_(metric),
128  grid_(grid_spacing_x, grid_spacing_y)
129  {
130  init_(data_x, data_y, properties_A, properties_B);
131  }
132 
142  GridBasedClustering(Metric metric, const std::vector<double>& data_x,
143  const std::vector<double>& data_y, std::vector<double> grid_spacing_x,
144  std::vector<double> grid_spacing_y) :
145  metric_(metric),
146  grid_(grid_spacing_x, grid_spacing_y)
147  {
148  // set properties A and B to -1, i.e. ignore properties when clustering
149  std::vector<int> properties_A(data_x.size(), -1);
150  std::vector<int> properties_B(data_x.size(), -1);
151  init_(data_x, data_y, properties_A, properties_B);
152  }
153 
158  void cluster()
159  {
160  // progress logger
161  // NOTE: for some reason, gcc7 chokes if we remove the OpenMS::String
162  // below, so lets just not change it.
163  Size clusters_start = clusters_.size();
164  startProgress(0, clusters_start, OpenMS::String("clustering"));
165 
166  MinimumDistance zero_distance(-1, -1, 0);
167 
168  // combine clusters until all have been moved to the final list
169  while (!clusters_.empty())
170  {
171  setProgress(clusters_start - clusters_.size());
172 
173  MultisetIterator smallest_distance_it = distances_.lower_bound(zero_distance);
174 
175  int cluster_index1 = smallest_distance_it->getClusterIndex();
176  int cluster_index2 = smallest_distance_it->getNearestNeighbourIndex();
177 
178  eraseMinDistance_(smallest_distance_it);
179 
180  // update cluster list
181  std::map<int, GridBasedCluster>::iterator cluster1_it = clusters_.find(cluster_index1);
182  std::map<int, GridBasedCluster>::iterator cluster2_it = clusters_.find(cluster_index2);
183  const GridBasedCluster& cluster1 = cluster1_it->second;
184  const GridBasedCluster& cluster2 = cluster2_it->second;
185  const std::vector<int>& points1 = cluster1.getPoints();
186  const std::vector<int>& points2 = cluster2.getPoints();
187  std::vector<int> new_points;
188  new_points.reserve(points1.size() + points2.size());
189  new_points.insert(new_points.end(), points1.begin(), points1.end());
190  new_points.insert(new_points.end(), points2.begin(), points2.end());
191 
192  double new_x = (cluster1.getCentre().getX() * points1.size() + cluster2.getCentre().getX() * points2.size()) / (points1.size() + points2.size());
193  double new_y = (cluster1.getCentre().getY() * points1.size() + cluster2.getCentre().getY() * points2.size()) / (points1.size() + points2.size());
194 
195  // update grid
196  CellIndex cell_for_cluster1 = grid_.getIndex(cluster1.getCentre());
197  CellIndex cell_for_cluster2 = grid_.getIndex(cluster2.getCentre());
198  CellIndex cell_for_new_cluster = grid_.getIndex(DPosition<2>(new_x, new_y));
199  grid_.removeCluster(cell_for_cluster1, cluster_index1);
200  grid_.removeCluster(cell_for_cluster2, cluster_index2);
201  grid_.addCluster(cell_for_new_cluster, cluster_index1);
202 
203  // merge clusters
204  const Rectangle& box1 = cluster1.getBoundingBox();
205  const Rectangle& box2 = cluster2.getBoundingBox();
206  Rectangle new_box(box1);
207  new_box.enlarge(box2.minPosition());
208  new_box.enlarge(box2.maxPosition());
209 
210  // Properties A of both clusters should by now be the same. The merge veto has been checked
211  // when a new entry to the minimum distance list was added, @see findNearestNeighbour_.
212  if (cluster1.getPropertyA() != cluster2.getPropertyA())
213  {
214  throw Exception::InvalidValue(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION, "Property A of both clusters not the same. ", "A");
215  }
216  int new_A = cluster1.getPropertyA();
217 
218  const std::vector<int>& B1 = cluster1.getPropertiesB();
219  const std::vector<int>& B2 = cluster2.getPropertiesB();
220  std::vector<int> new_B;
221  new_B.reserve(B1.size() + B2.size());
222  new_B.insert(new_B.end(), B1.begin(), B1.end());
223  new_B.insert(new_B.end(), B2.begin(), B2.end());
224 
225  GridBasedCluster new_cluster(DPosition<2>(new_x, new_y), new_box, new_points, new_A, new_B);
226 
227  clusters_.erase(cluster1_it);
228  clusters_.erase(cluster2_it);
229  clusters_.insert(std::make_pair(cluster_index1, new_cluster));
230 
231  std::set<int> clusters_to_be_updated;
232  clusters_to_be_updated.insert(cluster_index1);
233 
234  // erase distance object of cluster with cluster_index2 without updating (does not exist anymore!)
235  // (the one with cluster_index1 has already been erased at the top of the while loop)
237 
238  // find out which clusters need to be updated
239  std::pair<NNIterator, NNIterator> nn_range = reverse_nns_.equal_range(cluster_index1);
240  for (NNIterator nn_it = nn_range.first; nn_it != nn_range.second;)
241  {
242  clusters_to_be_updated.insert(nn_it->second->getClusterIndex());
243  eraseMinDistance_((nn_it++)->second);
244  }
245  nn_range = reverse_nns_.equal_range(cluster_index2);
246  for (NNIterator nn_it = nn_range.first; nn_it != nn_range.second;)
247  {
248  clusters_to_be_updated.insert(nn_it->second->getClusterIndex());
249  eraseMinDistance_((nn_it++)->second);
250  }
251 
252  // update clusters
253  for (std::set<int>::const_iterator cluster_index = clusters_to_be_updated.begin(); cluster_index != clusters_to_be_updated.end(); ++cluster_index)
254  {
255  std::map<int, GridBasedCluster>::iterator c_it = clusters_.find(*cluster_index);
256  const GridBasedCluster& c = c_it->second;
257  if (findNearestNeighbour_(c, *cluster_index))
258  {
259  grid_.removeCluster(grid_.getIndex(c.getCentre()), *cluster_index); // remove from grid
260  clusters_.erase(c_it); // remove from cluster list
261  }
262  }
263  }
264 
265  endProgress();
266  }
267 
273  {
274 
275  // construct new grid (grid only in x-direction, single cell in y-direction)
276  std::vector<double> grid_spacing_x = grid_.getGridSpacingX();
277  std::vector<double> grid_spacing_y = grid_.getGridSpacingY();
278  std::vector<double> grid_spacing_y_new;
279  grid_spacing_y_new.push_back(grid_spacing_y.front());
280  grid_spacing_y_new.push_back(grid_spacing_y.back());
281  ClusteringGrid grid_x_only(grid_spacing_x, grid_spacing_y_new);
282 
283  // register final clusters on the new grid
284  for (std::map<int, GridBasedCluster>::const_iterator it = clusters_final_.begin(); it != clusters_final_.end(); ++it)
285  {
286  int cluster_index = it->first;
287  GridBasedCluster cluster = it->second;
288  grid_x_only.addCluster(grid_x_only.getIndex(cluster.getCentre()), cluster_index);
289  }
290 
291 
292  // scan through x on the grid
293  for (unsigned cell = 0; cell < grid_spacing_x.size(); ++cell)
294  {
295  CellIndex grid_index(cell, 1);
296  if (grid_x_only.isNonEmptyCell(grid_index))
297  {
298  std::list<int> cluster_indices = grid_x_only.getClusters(grid_index); // indices of clusters in this x-range
299  if (cluster_indices.size() > 1)
300  {
301  // First, order the clusters in ascending y.
302  std::list<GridBasedCluster> cluster_list; // list to order clusters in y
303  std::map<GridBasedCluster, int> index_list; // allows us to keep track of cluster indices after sorting
304  for (std::list<int>::const_iterator it = cluster_indices.begin(); it != cluster_indices.end(); ++it)
305  {
306  cluster_list.push_back(clusters_final_.find(*it)->second);
307  index_list.insert(std::make_pair(clusters_final_.find(*it)->second, *it));
308  }
309  cluster_list.sort();
310 
311  // Now check if two adjacent clusters c1 and c2 can be merged.
312  std::list<GridBasedCluster>::const_iterator c1 = cluster_list.begin();
313  std::list<GridBasedCluster>::const_iterator c2 = cluster_list.begin();
314  ++c1;
315  while (c1 != cluster_list.end())
316  {
317  double centre1x = (*c1).getCentre().getX();
318  double centre1y = (*c1).getCentre().getY();
319  double centre2x = (*c2).getCentre().getX();
320  double centre2y = (*c2).getCentre().getY();
321 
322  double box1x_min = (*c1).getBoundingBox().minX();
323  double box1x_max = (*c1).getBoundingBox().maxX();
324  double box1y_min = (*c1).getBoundingBox().minY();
325  double box1y_max = (*c1).getBoundingBox().maxY();
326  double box2x_min = (*c2).getBoundingBox().minX();
327  double box2x_max = (*c2).getBoundingBox().maxX();
328  double box2y_min = (*c2).getBoundingBox().minY();
329  double box2y_max = (*c2).getBoundingBox().maxY();
330 
331  //double y_range1 = box1y_max - box1y_min;
332  //double y_range2 = box2y_max - box2y_min;
333  //double y_gap = box1y_min - box2y_max;
334 
335  // Is there an overlap of the two clusters in x?
336  bool overlap = (box1x_min <= box2x_max && box1x_min >= box2x_min) || (box1x_max >= box2x_min && box1x_max <= box2x_max);
337 
338  // Is the x-centre of one cluster in the x-range of the other?
339  //bool centre_in_range1 = (box2x_min <= centre1x && centre1x <= box2x_max);
340  //bool centre_in_range2 = (box1x_min <= centre2x && centre2x <= box1x_max);
341 
342  // Is the y-gap between the two clusters smaller than 1/s of their average y-range?
343  //double s = 6; // scaling factor
344  //bool clusters_close = (y_gap * s <= (y_range1 - y_range2)/2);
345 
346  // Shall we merge the two adjacent clusters?
347  //if ((centre_in_range1 || centre_in_range2) && clusters_close)
348  if (overlap)
349  {
350  std::vector<int> points1 = (*c1).getPoints();
351  std::vector<int> points2 = (*c2).getPoints();
352  std::vector<int> new_points;
353  new_points.reserve(points1.size() + points2.size());
354  new_points.insert(new_points.end(), points1.begin(), points1.end());
355  new_points.insert(new_points.end(), points2.begin(), points2.end());
356 
357  double new_x = (centre1x * points1.size() + centre2x * points2.size()) / (points1.size() + points2.size());
358  double new_y = (centre1y * points1.size() + centre2y * points2.size()) / (points1.size() + points2.size());
359 
360  double min_x = std::min(box1x_min, box2x_min);
361  double min_y = std::min(box1y_min, box2y_min);
362  double max_x = std::max(box1x_max, box2x_max);
363  double max_y = std::max(box1y_max, box2y_max);
364 
365  Point new_centre(new_x, new_y);
366  Point position_min(min_x, min_y);
367  Point position_max(max_x, max_y);
368  Rectangle new_bounding_box(position_min, position_max);
369 
370  GridBasedCluster new_cluster(new_centre, new_bounding_box, new_points);
371 
372  // update final cluster list
373  clusters_final_.erase(clusters_final_.find(index_list.find(*c1)->second));
374  clusters_final_.erase(clusters_final_.find(index_list.find(*c2)->second));
375  clusters_final_.insert(std::make_pair(index_list.find(*c1)->second, new_cluster));
376 
377  // update grid
378  CellIndex cell_for_cluster1 = grid_x_only.getIndex((*c1).getCentre());
379  CellIndex cell_for_cluster2 = grid_x_only.getIndex((*c2).getCentre());
380  CellIndex cell_for_new_cluster = grid_x_only.getIndex(new_centre);
381 
382  grid_x_only.removeCluster(cell_for_cluster1, index_list.find(*c1)->second);
383  grid_x_only.removeCluster(cell_for_cluster2, index_list.find(*c2)->second);
384  grid_x_only.addCluster(cell_for_new_cluster, index_list.find(*c1)->second);
385  }
386  ++c1;
387  ++c2;
388  }
389  }
390  }
391  }
392 
393  }
394 
399  void removeSmallClustersY(double threshold_y)
400  {
401  std::map<int, GridBasedCluster>::iterator it = clusters_final_.begin();
402  while (it != clusters_final_.end())
403  {
404  Rectangle box = it->second.getBoundingBox();
405  if (box.maxY() - box.minY() < threshold_y)
406  {
407  clusters_final_.erase(it++);
408  }
409  else
410  {
411  ++it;
412  }
413  }
414  }
415 
419  std::map<int, GridBasedCluster> getResults() const
420  {
421  return clusters_final_;
422  }
423 
424 private:
425 
429  Metric metric_;
430 
436 
441  std::map<int, GridBasedCluster> clusters_;
442 
447  std::map<int, GridBasedCluster> clusters_final_;
448 
453  std::multiset<MinimumDistance> distances_;
454 
459  std::unordered_multimap<int, std::multiset<MinimumDistance>::const_iterator> reverse_nns_;
460 
465  std::unordered_map<int, std::multiset<MinimumDistance>::const_iterator> distance_it_for_cluster_idx_;
466 
475  void init_(const std::vector<double>& data_x, const std::vector<double>& data_y,
476  const std::vector<int>& properties_A, const std::vector<int>& properties_B)
477  {
478  // fill the grid with points to be clustered (initially each cluster contains a single point)
479  for (unsigned i = 0; i < data_x.size(); ++i)
480  {
481  Point position(data_x[i], data_y[i]);
482  Rectangle box(position, position);
483 
484  std::vector<int> pi; // point indices
485  pi.push_back(i);
486  std::vector<int> pb; // properties B
487  pb.push_back(properties_B[i]);
488 
489  // add to cluster list
490  GridBasedCluster cluster(position, box, pi, properties_A[i], pb);
491  clusters_.insert(std::make_pair(i, cluster));
492 
493  // register on grid
494  grid_.addCluster(grid_.getIndex(position), i);
495  }
496 
497  // fill list of minimum distances
498  std::map<int, GridBasedCluster>::iterator iterator = clusters_.begin();
499  while (iterator != clusters_.end())
500  {
501  int cluster_index = iterator->first;
502  const GridBasedCluster& cluster = iterator->second;
503 
504  if (findNearestNeighbour_(cluster, cluster_index))
505  {
506  // remove from grid
507  grid_.removeCluster(grid_.getIndex(cluster.getCentre()), cluster_index);
508  // remove from cluster list
509  clusters_.erase(iterator++);
510  }
511  else
512  {
513  ++iterator;
514  }
515  }
516  }
517 
531  bool mergeVeto_(const GridBasedCluster& c1, const GridBasedCluster& c2) const
532  {
533  int A1 = c1.getPropertyA();
534  int A2 = c2.getPropertyA();
535 
536  // check if properties A of both clusters is set or not (not set := -1)
537  if (A1 == -1 || A2 == -1)
538  {
539  return false;
540  }
541 
542  // Will the merged cluster have the same properties A?
543  if (A1 != A2) return true;
544 
545  std::vector<int> B1 = c1.getPropertiesB();
546  std::vector<int> B2 = c2.getPropertiesB();
547 
548  // check if properties B of both clusters is set or not (not set := -1)
549  if (std::find(B1.begin(), B1.end(), -1) != B1.end() || std::find(B2.begin(), B2.end(), -1) != B2.end())
550  {
551  return false;
552  }
553 
554  // Will the merged cluster have different properties B?
555  // (Hence the intersection of properties B of cluster 1 and cluster 2 should be empty.)
556  std::vector<int> B_intersection;
557  sort(B1.begin(), B1.end());
558  sort(B2.begin(), B2.end());
559  set_intersection(B1.begin(), B1.end(), B2.begin(), B2.end(), back_inserter(B_intersection));
560 
561  return !B_intersection.empty();
562  }
563 
577  bool findNearestNeighbour_(const GridBasedCluster& cluster, int cluster_index)
578  {
579  const Point& centre = cluster.getCentre();
580  const CellIndex& cell_index = grid_.getIndex(centre);
581  double min_dist = 0;
582  int nearest_neighbour = -1;
583 
584  // search in the grid cell and its 8 neighbouring cells for the nearest neighbouring cluster
585  for (int i = -1; i <= 1; ++i)
586  {
587  for (int j = -1; j <= 1; ++j)
588  {
589  CellIndex cell_index2(cell_index);
590  cell_index2.first += i;
591  cell_index2.second += j;
592  if (grid_.isNonEmptyCell(cell_index2))
593  {
594  const std::list<int>& cluster_indices = grid_.getClusters(cell_index2);
595  for (std::list<int>::const_iterator cluster_index2 = cluster_indices.begin(); cluster_index2 != cluster_indices.end(); ++cluster_index2)
596  {
597  if (*cluster_index2 != cluster_index)
598  {
599  const GridBasedCluster& cluster2 = clusters_.find(*cluster_index2)->second;
600  const Point& centre2 = cluster2.getCentre();
601  double distance = metric_(centre, centre2);
602 
603  if (distance < min_dist || nearest_neighbour == -1)
604  {
605  bool veto = mergeVeto_(cluster, cluster2); // If clusters cannot be merged anyhow, they are no nearest neighbours.
606  if (!veto)
607  {
608  min_dist = distance;
609  nearest_neighbour = *cluster_index2;
610  }
611  }
612  }
613  }
614  }
615  }
616  }
617 
618  if (nearest_neighbour == -1)
619  {
620  // no other cluster nearby, hence move the cluster to the final results
621  clusters_final_.insert(std::make_pair(cluster_index, clusters_.find(cluster_index)->second));
622  return true;
623  }
624 
625  // add to the list of minimal distances
626  std::multiset<MinimumDistance>::const_iterator it = distances_.insert(MinimumDistance(cluster_index, nearest_neighbour, min_dist));
627  // add to reverse nearest neighbor lookup table
628  reverse_nns_.insert(std::make_pair(nearest_neighbour, it));
629  // add to cluster index -> distance lookup table
630  distance_it_for_cluster_idx_[cluster_index] = it;
631 
632  return false;
633  }
634 
644  void eraseMinDistance_(const std::multiset<MinimumDistance>::const_iterator it)
645  {
646  // remove corresponding entries from nearest neighbor lookup table
647  std::pair<NNIterator, NNIterator> nn_range = reverse_nns_.equal_range(it->getNearestNeighbourIndex());
648  for (NNIterator nn_it = nn_range.first; nn_it != nn_range.second; ++nn_it)
649  {
650  if (nn_it->second == it)
651  {
652  reverse_nns_.erase(nn_it);
653  break;
654  }
655  }
656 
657  // remove corresponding entry from cluster index -> distance lookup table
658  distance_it_for_cluster_idx_.erase(it->getClusterIndex());
659 
660  // remove from distances_
661  distances_.erase(it);
662  }
663  };
664 }
data structure to store 2D data to be clustered e.g. (m/z, retention time) coordinates from multiplex...
Definition: ClusteringGrid.h:30
std::vector< double > getGridSpacingX() const
returns grid spacing in x direction
CellIndex getIndex(const Point &position) const
returns grid cell index (i,j) for the positions (x,y)
void removeCluster(const CellIndex &cell_index, const int &cluster_index)
removes a cluster from this grid cell and removes the cell if no other cluster left
std::list< int > getClusters(const CellIndex &cell_index) const
returns clusters in this grid cell
std::pair< int, int > CellIndex
Definition: ClusteringGrid.h:35
std::vector< double > getGridSpacingY() const
returns grid spacing in y direction
bool isNonEmptyCell(const CellIndex &cell_index) const
checks if there are clusters at this cell index
void addCluster(const CellIndex &cell_index, const int &cluster_index)
adds a cluster to this grid cell
void enlarge(const PositionType &p)
Enlarges the bounding box such that it contains a position.
Definition: DBoundingBox.h:95
CoordinateType getY() const
Name accessor for the second dimension. Only for DPosition<2>, for visualization.
Definition: DPosition.h:149
CoordinateType getX() const
Name accessor for the first dimension. Only for DPosition<2>, for visualization.
Definition: DPosition.h:142
Invalid value exception.
Definition: Exception.h:305
basic data structure for clustering
Definition: GridBasedCluster.h:24
const Point & getCentre() const
returns cluster centre
const std::vector< int > & getPoints() const
returns indices of points in cluster
const std::vector< int > & getPropertiesB() const
returns properties B of all points
const Rectangle & getBoundingBox() const
returns bounding box
int getPropertyA() const
returns property A
2D hierarchical clustering implementation optimized for large data sets containing many small cluster...
Definition: GridBasedClustering.h:101
void removeSmallClustersY(double threshold_y)
removes clusters with bounding box dimension in y-direction below certain threshold
Definition: GridBasedClustering.h:399
bool findNearestNeighbour_(const GridBasedCluster &cluster, int cluster_index)
determines the nearest neighbour for each cluster
Definition: GridBasedClustering.h:577
std::unordered_map< int, std::multiset< MinimumDistance >::const_iterator > distance_it_for_cluster_idx_
cluster index to distance iterator lookup table for finding out which clusters need to be updated fas...
Definition: GridBasedClustering.h:465
bool mergeVeto_(const GridBasedCluster &c1, const GridBasedCluster &c2) const
checks if two clusters can be merged Each point in a cluster can (optionally) have two properties A a...
Definition: GridBasedClustering.h:531
void init_(const std::vector< double > &data_x, const std::vector< double > &data_y, const std::vector< int > &properties_A, const std::vector< int > &properties_B)
initialises all data structures
Definition: GridBasedClustering.h:475
ClusteringGrid grid_
grid on which the position of the clusters are registered used in cluster method
Definition: GridBasedClustering.h:435
void extendClustersY()
extends clusters in y-direction if possible (merges clusters further in y-direction,...
Definition: GridBasedClustering.h:272
Metric metric_
metric for measuring the distance between points in the 2D plane
Definition: GridBasedClustering.h:429
GridBasedClustering(Metric metric, const std::vector< double > &data_x, const std::vector< double > &data_y, std::vector< double > grid_spacing_x, std::vector< double > grid_spacing_y)
initialises all data structures
Definition: GridBasedClustering.h:142
GridBasedCluster::Rectangle Rectangle
Definition: GridBasedClustering.h:107
std::multiset< MinimumDistance > distances_
list of minimum distances stores the smallest of the distances in the head
Definition: GridBasedClustering.h:453
GridBasedClustering(Metric metric, const std::vector< double > &data_x, const std::vector< double > &data_y, const std::vector< int > &properties_A, const std::vector< int > &properties_B, std::vector< double > grid_spacing_x, std::vector< double > grid_spacing_y)
initialises all data structures
Definition: GridBasedClustering.h:123
void cluster()
performs the hierarchical clustering (merges clusters until their dimension exceeds that of cell)
Definition: GridBasedClustering.h:158
GridBasedCluster::Point Point
cluster centre, cluster bounding box, grid index
Definition: GridBasedClustering.h:106
std::unordered_multimap< int, std::multiset< MinimumDistance >::const_iterator > reverse_nns_
reverse nearest neighbor lookup table for finding out which clusters need to be updated faster
Definition: GridBasedClustering.h:459
std::multiset< MinimumDistance >::const_iterator MultisetIterator
Definition: GridBasedClustering.h:109
std::map< int, GridBasedCluster > clusters_
list of clusters maps cluster indices to clusters
Definition: GridBasedClustering.h:441
std::unordered_multimap< int, MultisetIterator >::const_iterator NNIterator
Definition: GridBasedClustering.h:110
std::map< int, GridBasedCluster > clusters_final_
list of final clusters i.e. clusters that are no longer merged
Definition: GridBasedClustering.h:447
void eraseMinDistance_(const std::multiset< MinimumDistance >::const_iterator it)
remove minimum distance object and its related data
Definition: GridBasedClustering.h:644
ClusteringGrid::CellIndex CellIndex
Definition: GridBasedClustering.h:108
std::map< int, GridBasedCluster > getResults() const
returns final results (mapping of cluster indices to clusters)
Definition: GridBasedClustering.h:419
PositionType const & maxPosition() const
Accessor to maximum position.
Definition: DIntervalBase.h:104
CoordinateType maxY() const
Accessor for max_ coordinate maximum.
Definition: DIntervalBase.h:286
CoordinateType minY() const
Accessor for max_ coordinate minimum.
Definition: DIntervalBase.h:274
PositionType const & minPosition() const
Accessor to minimum position.
Definition: DIntervalBase.h:98
basic data structure for distances between clusters
Definition: GridBasedClustering.h:35
MinimumDistance()
hide default constructor
bool operator>(const MinimumDistance &other) const
int getClusterIndex() const
returns cluster index
MinimumDistance(const int &cluster_index, const int &nearest_neighbour_index, const double &distance)
constructor
int nearest_neighbour_index_
index of the nearest neighbour of the above cluster
Definition: GridBasedClustering.h:74
int getNearestNeighbourIndex() const
returns index of nearest cluster
double distance_
distance between cluster and its nearest neighbour
Definition: GridBasedClustering.h:79
bool operator==(const MinimumDistance &other) const
int cluster_index_
index in the cluster list
Definition: GridBasedClustering.h:69
bool operator<(const MinimumDistance &other) const
operators for comparisons (for multiset)
Base class for all classes that want to report their progress.
Definition: ProgressLogger.h:27
void setProgress(SignedSize value) const
Sets the current progress.
void startProgress(SignedSize begin, SignedSize end, const String &label) const
Initializes the progress display.
void endProgress(UInt64 bytes_processed=0) const
A more convenient string class.
Definition: String.h:34
size_t Size
Size type e.g. used as variable which can hold result of size()
Definition: Types.h:97
const double c
Definition: Constants.h:188
Main OpenMS namespace.
Definition: openswathalgo/include/OpenMS/OPENSWATHALGO/DATAACCESS/ISpectrumAccess.h:19