Developer Documentation
DBSCAN_test.cc
1 /*===========================================================================*\
2  * *
3  * OpenFlipper *
4  * Copyright (c) 2001-2015, RWTH-Aachen University *
5  * Department of Computer Graphics and Multimedia *
6  * All rights reserved. *
7  * www.openflipper.org *
8  * *
9  *---------------------------------------------------------------------------*
10  * This file is part of OpenFlipper. *
11  *---------------------------------------------------------------------------*
12  * *
13  * Redistribution and use in source and binary forms, with or without *
14  * modification, are permitted provided that the following conditions *
15  * are met: *
16  * *
17  * 1. Redistributions of source code must retain the above copyright notice, *
18  * this list of conditions and the following disclaimer. *
19  * *
20  * 2. Redistributions in binary form must reproduce the above copyright *
21  * notice, this list of conditions and the following disclaimer in the *
22  * documentation and/or other materials provided with the distribution. *
23  * *
24  * 3. Neither the name of the copyright holder nor the names of its *
25  * contributors may be used to endorse or promote products derived from *
26  * this software without specific prior written permission. *
27  * *
28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
30  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
31  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
32  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, *
33  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, *
34  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR *
35  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF *
36  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING *
37  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS *
38  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
39  * *
40 \*===========================================================================*/
41 
42 
43 #include <gtest/gtest.h>
44 
45 #include <vector>
46 #include <map>
47 
48 #include <cmath>
49 #include <cstring>
50 
51 #include "../../Algorithm/DBSCANT.hh"
52 
53 namespace {
54 const char * const test1_map[] = {
55  " ",
56  " . b b . ",
57  " ",
58  " a b ",
59  " ",
60  " ",
61  " a b b b ",
62  " aa b b b ",
63  " aaaa . . b b b bbb b ",
64  " aa b b ",
65  " a a a a ",
66  " a a a a a a ",
67  " a a a ",
68  " ",
69  " aaa ",
70  " ",
71  " ",
72  " ",
73  " . a a a . cc ",
74  " cc ",
75  " .. ",
76  " . ",
77  " ",
78  0 };
79 
80 const char * const test2_map[] = { "aaaaAAaaaa", 0 };
81 
82 class Point {
83  public:
84  Point(double x, double y, char classifier, double weight = 1.0) : x(x), y(y), weight(weight), classifier(classifier) {}
85 
86  double length() const {
87  return std::sqrt(x*x + y*y);
88  }
89 
90  Point operator- (const Point &rhs) const {
91  return Point(x-rhs.x, y-rhs.y, classifier, weight);
92  }
93 
94  double dist(const Point &rhs) const {
95  return operator-(rhs).length();
96  }
97 
98  class DistanceFunc {
99  public:
100  double operator() (const Point &a, const Point &b) const {
101  return a.dist(b);
102  }
103  };
104 
105  class WeightFunc {
106  public:
107  double operator() (const Point &a) const {
108  return a.weight;
109  }
110  };
111 
112  double x, y, weight;
113  char classifier;
114 };
115 
116 template<class OSTREAM>
117 OSTREAM &operator<< (OSTREAM &stream, Point* point) {
118  return stream << "(" << point->x << ", " << point->y << ", " << point->weight << ", " << "'" << point->classifier << "'" << ")";
119 }
120 
121 template<class OUTPUT_ITERATOR>
122 void parse_points(const char * const * input, OUTPUT_ITERATOR points_out, double uc_weight = 1.0, double lc_weight = 1.0) {
123  int y = 0;
124  for (; *input != 0; ++input, ++y) {
125  int x = 0;
126  for (const char *it = *input; *it != 0; ++it, ++x) {
127  if (!isspace(*it)) {
128  const double weight = islower(*it) ? lc_weight : uc_weight;
129  *points_out++ = Point(x, y, *it, weight);
130  }
131  }
132  }
133 }
134 
135 testing::AssertionResult checkClusterConsistency(const std::vector<Point> &points, const std::vector<int> &cluster_map) {
136  std::map<int, char> cluster_2_classifier;
137 
138  std::vector<int>::const_iterator cluster_it = cluster_map.begin();
139  for (std::vector<Point>::const_iterator point_it = points.begin(), point_it_end = points.end();
140  point_it != point_it_end; ++point_it, ++cluster_it) {
141 
142  std::map<int, char>::const_iterator map_it = cluster_2_classifier.find(*cluster_it);
143  if (map_it == cluster_2_classifier.end()) {
144  cluster_2_classifier[*cluster_it] = point_it->classifier;
145 
146  if (point_it->classifier == '.' && *cluster_it != 0) {
147  return testing::AssertionFailure() << "Noise point " << &(*point_it) << " was mapped to non-noise cluster " << *cluster_it << ".";
148  }
149 
150  if (*cluster_it == 0 && point_it->classifier != '.') {
151  return testing::AssertionFailure() << "Non-noise point " << &(*point_it) << " was mapped to noise cluster (0).";
152  }
153  } else {
154  if (map_it->second != point_it->classifier) {
155  return testing::AssertionFailure() << "Point " << &(*point_it) << " was mapped to cluster '" << map_it->second << "'.";
156  }
157  }
158  }
159 
160  return testing::AssertionSuccess() << "All points were mapped to clusters as expected.";
161 }
162 
163 template<class II_1, class II_2>
164 testing::AssertionResult checkCollectionEquivalence(II_1 first1, II_1 last1, II_2 first2, II_2 last2) {
165  for (int index = 0; first1 != last1 && first2 != last2; ++first1, ++first2, ++index) {
166  if (*first1 != *first2)
167  return testing::AssertionFailure() << "Mismatch in element " << index << ".";
168  }
169 
170  if (first1 != last1)
171  return testing::AssertionFailure() << "Second collection longer than first one.";
172 
173  if (first2 != last2)
174  return testing::AssertionFailure() << "First collection longer than second one.";
175 
176  return testing::AssertionSuccess() << "Collections are equivalent.";
177 }
178 
179 TEST(DBSCAN, manual_test_1) {
180  std::vector<Point> points;
181  parse_points(test1_map, std::back_inserter(points));
182  std::vector<int> clusters;
183 
184  EXPECT_EQ(3,
185  ACG::Algorithm::DBSCAN(points.begin(), points.end(), Point::DistanceFunc(),
186  std::back_inserter(clusters), 4.0001, 3.0));
187  EXPECT_TRUE(checkClusterConsistency(points, clusters));
188 
189  // Call both versions of DBSCAN.
190  EXPECT_EQ(3,
191  ACG::Algorithm::DBSCAN(points.begin(), points.end(), Point::DistanceFunc(),
192  std::back_inserter(clusters), 4.0001, 3.0,
193  ACG::Algorithm::_DBSCAN_PRIVATE::constant_1<std::vector<Point>::iterator::value_type>()));
194  EXPECT_TRUE(checkClusterConsistency(points, clusters));
195 }
196 
197 TEST(DBSCAN, manual_test_2_a) {
198  std::vector<Point> points;
199  parse_points(test2_map, std::back_inserter(points), 1.0, 1.0);
200  std::vector<int> clusters;
201  EXPECT_EQ(1,
202  ACG::Algorithm::DBSCAN(points.begin(), points.end(), Point::DistanceFunc(),
203  std::back_inserter(clusters), 1.01, 1.2, Point::WeightFunc()));
204 
205  const int expected[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
206  EXPECT_TRUE(checkCollectionEquivalence(clusters.begin(), clusters.end(), expected, expected + 10));
207 }
208 
209 TEST(DBSCAN, manual_test_2_b) {
210  std::vector<Point> points;
211  parse_points(test2_map, std::back_inserter(points), 1.0, .5);
212  std::vector<int> clusters;
213  EXPECT_EQ(1,
214  ACG::Algorithm::DBSCAN(points.begin(), points.end(), Point::DistanceFunc(),
215  std::back_inserter(clusters), 1.01, 1.2, Point::WeightFunc()));
216 
217  const int expected[] = { 0, 0, 1, 1, 1, 1, 1, 1, 0, 0 };
218  EXPECT_TRUE(checkCollectionEquivalence(clusters.begin(), clusters.end(), expected, expected + 10));
219 }
220 
221 }