OpenMS
FeatureGroupingAlgorithmKD.h
Go to the documentation of this file.
1 // --------------------------------------------------------------------------
2 // OpenMS -- Open-Source Mass Spectrometry
3 // --------------------------------------------------------------------------
4 // Copyright The OpenMS Team -- Eberhard Karls University Tuebingen,
5 // ETH Zurich, and Freie Universitaet Berlin 2002-2023.
6 //
7 // This software is released under a three-clause BSD license:
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above copyright
11 // notice, this list of conditions and the following disclaimer in the
12 // documentation and/or other materials provided with the distribution.
13 // * Neither the name of any author or any participating institution
14 // may be used to endorse or promote products derived from this software
15 // without specific prior written permission.
16 // For a full list of authors, refer to the file AUTHORS.
17 // --------------------------------------------------------------------------
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 // ARE DISCLAIMED. IN NO EVENT SHALL ANY OF THE AUTHORS OR THE CONTRIBUTING
22 // INSTITUTIONS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
25 // OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
26 // WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
27 // OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
28 // ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // --------------------------------------------------------------------------
31 // $Maintainer: Johannes Veit $
32 // $Authors: Johannes Veit $
33 // --------------------------------------------------------------------------
34 
35 #pragma once
36 
41 
42 namespace OpenMS
43 {
44 
46 
58 class OPENMS_DLLAPI ClusterProxyKD
59 {
60 
61 public:
62 
65  size_(0), // => isValid() returns false
66  avg_distance_(0),
67  center_index_(0)
68  {
69  }
70 
72  ClusterProxyKD(Size size, double avg_distance, Size center_index) :
73  size_(size),
74  avg_distance_(avg_distance),
75  center_index_(center_index)
76  {
77  }
78 
81  size_(rhs.size_),
82  avg_distance_(rhs.avg_distance_),
83  center_index_(rhs.center_index_)
84  {
85  }
86 
89  {
90  }
91 
94  {
95  size_ = rhs.size_;
96  avg_distance_ = rhs.avg_distance_;
97  center_index_ = rhs.center_index_;
98 
99  return *this;
100  }
101 
103  bool operator<(const ClusterProxyKD& rhs) const
104  {
105  if (size_ > rhs.size_) return true;
106  if (size_ < rhs.size_) return false;
107 
108  if (avg_distance_ < rhs.avg_distance_) return true;
109  if (avg_distance_ > rhs.avg_distance_) return false;
110 
111  // arbitrary, but required for finding unambiguous elements in std::set
112  if (center_index_ > rhs.center_index_) return true;
113  if (center_index_ < rhs.center_index_) return false;
114 
115  // they are equal
116  return false;
117  }
118 
120  bool operator!=(const ClusterProxyKD& rhs) const
121  {
122  return *this < rhs || rhs < *this;
123  }
124 
126  bool operator==(const ClusterProxyKD& rhs) const
127  {
128  return !(*this != rhs);
129  }
130 
132  Size getSize() const
133  {
134  return size_;
135  }
136 
138  bool isValid() const
139  {
140  return size_;
141  }
142 
144  double getAvgDistance() const
145  {
146  return avg_distance_;
147  }
148 
151  {
152  return center_index_;
153  }
154 
155 private:
156 
159 
162 
165 };
166 
167 
178  class OPENMS_DLLAPI FeatureGroupingAlgorithmKD :
180  public ProgressLogger
181  {
182 
183 public:
184 
187 
190 
196  void group(const std::vector<FeatureMap>& maps, ConsensusMap& out) override;
197 
203  void group(const std::vector<ConsensusMap>& maps,
204  ConsensusMap& out) override;
205 
208  {
209  return new FeatureGroupingAlgorithmKD();
210  }
211 
214  {
215  return "unlabeled_kd";
216  }
217 
218 private:
219 
222 
225 
231  template <typename MapType>
232  void group_(const std::vector<MapType>& input_maps, ConsensusMap& out);
233 
235  void runClustering_(const KDTreeFeatureMaps& kd_data, ConsensusMap& out);
236 
238  void updateClusterProxies_(std::set<ClusterProxyKD>& potential_clusters, std::vector<ClusterProxyKD>& cluster_for_idx, const std::set<Size>& update_these, const std::vector<Int>& assigned, const KDTreeFeatureMaps& kd_data);
239 
241  ClusterProxyKD computeBestClusterForCenter_(Size i, std::vector<Size>& cf_indices, const std::vector<Int>& assigned, const KDTreeFeatureMaps& kd_data) const;
242 
244  void addConsensusFeature_(const std::vector<Size>& indices, const KDTreeFeatureMaps& kd_data, ConsensusMap& out) const;
245 
248 
250  double rt_tol_secs_;
251 
253  double mz_tol_;
254 
256  bool mz_ppm_;
257 
260  };
261 
262 } // namespace OpenMS
263 
Proxy for a (potential) cluster.
Definition: FeatureGroupingAlgorithmKD.h:59
double avg_distance_
Average distance to center.
Definition: FeatureGroupingAlgorithmKD.h:161
~ClusterProxyKD()
Destructor (non-virtual to save memory)
Definition: FeatureGroupingAlgorithmKD.h:88
Size getSize() const
Cluster size.
Definition: FeatureGroupingAlgorithmKD.h:132
Size getCenterIndex() const
Index of center point.
Definition: FeatureGroupingAlgorithmKD.h:150
bool isValid() const
Valid?
Definition: FeatureGroupingAlgorithmKD.h:138
double getAvgDistance() const
Average distance to center.
Definition: FeatureGroupingAlgorithmKD.h:144
ClusterProxyKD(const ClusterProxyKD &rhs)
Copy constructor.
Definition: FeatureGroupingAlgorithmKD.h:80
bool operator!=(const ClusterProxyKD &rhs) const
Inequality operator.
Definition: FeatureGroupingAlgorithmKD.h:120
bool operator==(const ClusterProxyKD &rhs) const
Equality operator.
Definition: FeatureGroupingAlgorithmKD.h:126
ClusterProxyKD()
Default constructor.
Definition: FeatureGroupingAlgorithmKD.h:64
ClusterProxyKD & operator=(const ClusterProxyKD &rhs)
Assignment operator.
Definition: FeatureGroupingAlgorithmKD.h:93
Size size_
Cluster size.
Definition: FeatureGroupingAlgorithmKD.h:158
ClusterProxyKD(Size size, double avg_distance, Size center_index)
Constructor.
Definition: FeatureGroupingAlgorithmKD.h:72
bool operator<(const ClusterProxyKD &rhs) const
Less-than operator for sorting / equality check in std::set. We use the ordering in std::set as a "pr...
Definition: FeatureGroupingAlgorithmKD.h:103
Size center_index_
Index of center point.
Definition: FeatureGroupingAlgorithmKD.h:164
A container for consensus elements.
Definition: ConsensusMap.h:92
A functor class for the calculation of distances between features or consensus features.
Definition: FeatureDistance.h:91
A feature grouping algorithm for unlabeled data.
Definition: FeatureGroupingAlgorithmKD.h:181
double mz_tol_
m/z tolerance
Definition: FeatureGroupingAlgorithmKD.h:253
ClusterProxyKD computeBestClusterForCenter_(Size i, std::vector< Size > &cf_indices, const std::vector< Int > &assigned, const KDTreeFeatureMaps &kd_data) const
Compute the current best cluster with center index i (mutates proxy and cf_indices)
FeatureGroupingAlgorithmKD(const FeatureGroupingAlgorithmKD &)
Copy constructor intentionally not implemented -> private.
FeatureGroupingAlgorithmKD()
Default constructor.
void runClustering_(const KDTreeFeatureMaps &kd_data, ConsensusMap &out)
Run the actual clustering algorithm.
double rt_tol_secs_
RT tolerance.
Definition: FeatureGroupingAlgorithmKD.h:250
static String getProductName()
Returns the product name (for the Factory)
Definition: FeatureGroupingAlgorithmKD.h:213
~FeatureGroupingAlgorithmKD() override
Destructor.
bool mz_ppm_
m/z unit ppm?
Definition: FeatureGroupingAlgorithmKD.h:256
FeatureDistance feature_distance_
Feature distance functor.
Definition: FeatureGroupingAlgorithmKD.h:259
FeatureGroupingAlgorithmKD & operator=(const FeatureGroupingAlgorithmKD &)
Assignment operator intentionally not implemented -> private.
void group(const std::vector< ConsensusMap > &maps, ConsensusMap &out) override
Applies the algorithm to consensus maps.
void group_(const std::vector< MapType > &input_maps, ConsensusMap &out)
Applies the algorithm to feature or consensus maps.
static FeatureGroupingAlgorithm * create()
Creates a new instance of this class (for Factory)
Definition: FeatureGroupingAlgorithmKD.h:207
void updateClusterProxies_(std::set< ClusterProxyKD > &potential_clusters, std::vector< ClusterProxyKD > &cluster_for_idx, const std::set< Size > &update_these, const std::vector< Int > &assigned, const KDTreeFeatureMaps &kd_data)
Update maximum possible sizes of potential consensus features for indices specified in update_these.
SignedSize progress_
Current progress for logging.
Definition: FeatureGroupingAlgorithmKD.h:247
void group(const std::vector< FeatureMap > &maps, ConsensusMap &out) override
Applies the algorithm to feature maps.
void addConsensusFeature_(const std::vector< Size > &indices, const KDTreeFeatureMaps &kd_data, ConsensusMap &out) const
Construct consensus feature and add to out map.
Base class for all feature grouping algorithms.
Definition: FeatureGroupingAlgorithm.h:51
Stores a set of features, together with a 2D tree for fast search.
Definition: KDTreeFeatureMaps.h:50
Base class for all classes that want to report their progress.
Definition: ProgressLogger.h:53
A more convenient string class.
Definition: String.h:60
ptrdiff_t SignedSize
Signed Size type e.g. used as pointer difference.
Definition: Types.h:134
size_t Size
Size type e.g. used as variable which can hold result of size()
Definition: Types.h:127
Main OpenMS namespace.
Definition: FeatureDeconvolution.h:48