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  * DBSCAN_test.cpp
44  *
45  * Created on: May 18, 2012
46  * Author: ebke
47  */
48 
49 #include <gtest/gtest.h>
50 
51 #include <vector>
52 #include <map>
53 
54 #include <cmath>
55 #include <cstring>
56 
57 #include "../../Algorithm/DBSCANT.hh"
58 
59 namespace {
60 const char * const test1_map[] = {
61  " ",
62  " . b b . ",
63  " ",
64  " a b ",
65  " ",
66  " ",
67  " a b b b ",
68  " aa b b b ",
69  " aaaa . . b b b bbb b ",
70  " aa b b ",
71  " a a a a ",
72  " a a a a a a ",
73  " a a a ",
74  " ",
75  " aaa ",
76  " ",
77  " ",
78  " ",
79  " . a a a . cc ",
80  " cc ",
81  " .. ",
82  " . ",
83  " ",
84  0 };
85 
86 const char * const test2_map[] = { "aaaaAAaaaa", 0 };
87 
88 class Point {
89  public:
90  Point(double x, double y, char classifier, double weight = 1.0) : x(x), y(y), weight(weight), classifier(classifier) {}
91 
92  double length() const {
93  return std::sqrt(x*x + y*y);
94  }
95 
96  Point operator- (const Point &rhs) const {
97  return Point(x-rhs.x, y-rhs.y, classifier, weight);
98  }
99 
100  double dist(const Point &rhs) const {
101  return operator-(rhs).length();
102  }
103 
104  class DistanceFunc {
105  public:
106  double operator() (const Point &a, const Point &b) const {
107  return a.dist(b);
108  }
109  };
110 
111  class WeightFunc {
112  public:
113  double operator() (const Point &a) const {
114  return a.weight;
115  }
116  };
117 
118  double x, y, weight;
119  char classifier;
120 };
121 
122 template<class OSTREAM>
123 OSTREAM &operator<< (OSTREAM &stream, Point* point) {
124  return stream << "(" << point->x << ", " << point->y << ", " << point->weight << ", " << "'" << point->classifier << "'" << ")";
125 }
126 
127 template<class OUTPUT_ITERATOR>
128 void parse_points(const char * const * input, OUTPUT_ITERATOR points_out, double uc_weight = 1.0, double lc_weight = 1.0) {
129  int y = 0;
130  for (; *input != 0; ++input, ++y) {
131  int x = 0;
132  for (const char *it = *input; *it != 0; ++it, ++x) {
133  if (!isspace(*it)) {
134  const double weight = islower(*it) ? lc_weight : uc_weight;
135  *points_out++ = Point(x, y, *it, weight);
136  }
137  }
138  }
139 }
140 
141 testing::AssertionResult checkClusterConsistency(const std::vector<Point> &points, const std::vector<int> &cluster_map) {
142  std::map<int, char> cluster_2_classifier;
143 
144  std::vector<int>::const_iterator cluster_it = cluster_map.begin();
145  for (std::vector<Point>::const_iterator point_it = points.begin(), point_it_end = points.end();
146  point_it != point_it_end; ++point_it, ++cluster_it) {
147 
148  std::map<int, char>::const_iterator map_it = cluster_2_classifier.find(*cluster_it);
149  if (map_it == cluster_2_classifier.end()) {
150  cluster_2_classifier[*cluster_it] = point_it->classifier;
151 
152  if (point_it->classifier == '.' && *cluster_it != 0) {
153  return testing::AssertionFailure() << "Noise point " << &(*point_it) << " was mapped to non-noise cluster " << *cluster_it << ".";
154  }
155 
156  if (*cluster_it == 0 && point_it->classifier != '.') {
157  return testing::AssertionFailure() << "Non-noise point " << &(*point_it) << " was mapped to noise cluster (0).";
158  }
159  } else {
160  if (map_it->second != point_it->classifier) {
161  return testing::AssertionFailure() << "Point " << &(*point_it) << " was mapped to cluster '" << map_it->second << "'.";
162  }
163  }
164  }
165 
166  return testing::AssertionSuccess() << "All points were mapped to clusters as expected.";
167 }
168 
169 template<class II_1, class II_2>
170 testing::AssertionResult checkCollectionEquivalence(II_1 first1, II_1 last1, II_2 first2, II_2 last2) {
171  for (int index = 0; first1 != last1 && first2 != last2; ++first1, ++first2, ++index) {
172  if (*first1 != *first2)
173  return testing::AssertionFailure() << "Mismatch in element " << index << ".";
174  }
175 
176  if (first1 != last1)
177  return testing::AssertionFailure() << "Second collection longer than first one.";
178 
179  if (first2 != last2)
180  return testing::AssertionFailure() << "First collection longer than second one.";
181 
182  return testing::AssertionSuccess() << "Collections are equivalent.";
183 }
184 
185 TEST(DBSCAN, manual_test_1) {
186  std::vector<Point> points;
187  parse_points(test1_map, std::back_inserter(points));
188  std::vector<int> clusters;
189 
190  EXPECT_EQ(3,
191  ACG::Algorithm::DBSCAN(points.begin(), points.end(), Point::DistanceFunc(),
192  std::back_inserter(clusters), 4.0001, 3.0));
193  EXPECT_TRUE(checkClusterConsistency(points, clusters));
194 
195  // Call both versions of DBSCAN.
196  EXPECT_EQ(3,
197  ACG::Algorithm::DBSCAN(points.begin(), points.end(), Point::DistanceFunc(),
198  std::back_inserter(clusters), 4.0001, 3.0,
199  ACG::Algorithm::_DBSCAN_PRIVATE::constant_1<std::vector<Point>::iterator::value_type>()));
200  EXPECT_TRUE(checkClusterConsistency(points, clusters));
201 }
202 
203 TEST(DBSCAN, manual_test_2_a) {
204  std::vector<Point> points;
205  parse_points(test2_map, std::back_inserter(points), 1.0, 1.0);
206  std::vector<int> clusters;
207  EXPECT_EQ(1,
208  ACG::Algorithm::DBSCAN(points.begin(), points.end(), Point::DistanceFunc(),
209  std::back_inserter(clusters), 1.01, 1.2, Point::WeightFunc()));
210 
211  const int expected[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
212  EXPECT_TRUE(checkCollectionEquivalence(clusters.begin(), clusters.end(), expected, expected + 10));
213 }
214 
215 TEST(DBSCAN, manual_test_2_b) {
216  std::vector<Point> points;
217  parse_points(test2_map, std::back_inserter(points), 1.0, .5);
218  std::vector<int> clusters;
219  EXPECT_EQ(1,
220  ACG::Algorithm::DBSCAN(points.begin(), points.end(), Point::DistanceFunc(),
221  std::back_inserter(clusters), 1.01, 1.2, Point::WeightFunc()));
222 
223  const int expected[] = { 0, 0, 1, 1, 1, 1, 1, 1, 0, 0 };
224  EXPECT_TRUE(checkCollectionEquivalence(clusters.begin(), clusters.end(), expected, expected + 10));
225 }
226 
227 }