Core/Clusterization/TimedClusterizationTests.cpp

0001 // This file is part of the ACTS project.
0002 //
0003 // Copyright (C) 2016 CERN for the benefit of the ACTS project
0004 //
0005 // This Source Code Form is subject to the terms of the Mozilla Public
0006 // License, v. 2.0. If a copy of the MPL was not distributed with this
0007 // file, You can obtain one at https://mozilla.org/MPL/2.0/.
0008
0009 #include <boost/test/unit_test.hpp>
0010
0011 #include "Acts/Clusterization/TimedClusterization.hpp"
0012
0013 #include <algorithm>
0014
0015 using namespace Acts;
0016
0017 // Define objects
0018 using Identifier = std::size_t;
0019 struct Cell {
0020   Cell(Identifier identifier, int c, int r, double t)
0021       : id(identifier), column(c), row(r), time(t) {}
0022
0023   Identifier id{};
0024   int column{0};
0025   int row{0};
0026   int label{-1};
0027   double time{0.};
0028 };
0029
0030 struct Cluster {
0031   std::vector<Identifier> ids{};
0032 };
0033
0034 using CellCollection = std::vector<Cell>;
0035 using ClusterCollection = std::vector<Cluster>;
0036
0037 // Define functions
0038 static inline int getCellRow(const Cell& cell) {
0039   return cell.row;
0040 }
0041
0042 static inline int getCellColumn(const Cell& cell) {
0043   return cell.column;
0044 }
0045
0046 static inline double getCellTime(const Cell& cell) {
0047   return cell.time;
0048 }
0049
0050 static void clusterAddCell(Cluster& cl, const Cell& cell) {
0051   cl.ids.push_back(cell.id);
0052 }
0053
0054 BOOST_AUTO_TEST_SUITE(ClusterizationSuite)
0055
0056 BOOST_AUTO_TEST_CASE(TimedGrid_1D_withtime) {
0057   // 1x10 matrix
0058   /*
0059     X X X Y O X Y Y X X
0060   */
0061   // 6 + 3 cells -> 3 + 2 clusters in total
0062
0063   std::vector<Cell> cells;
0064   // X
0065   cells.emplace_back(0ul, 0, -1, 0);
0066   cells.emplace_back(1ul, 1, -1, 0);
0067   cells.emplace_back(2ul, 2, -1, 0);
0068   cells.emplace_back(3ul, 5, -1, 0);
0069   cells.emplace_back(4ul, 8, -1, 0);
0070   cells.emplace_back(5ul, 9, -1, 0);
0071   // Y
0072   cells.emplace_back(6ul, 3, 0, 1);
0073   cells.emplace_back(7ul, 6, 1, 1);
0074   cells.emplace_back(8ul, 7, 1, 1);
0075
0076   std::vector<std::vector<Identifier>> expectedResults;
0077   expectedResults.push_back({0ul, 1ul, 2ul});
0078   expectedResults.push_back({6ul});
0079   expectedResults.push_back({3ul});
0080   expectedResults.push_back({7ul, 8ul});
0081   expectedResults.push_back({4ul, 5ul});
0082
0083   Acts::Ccl::ClusteringData data;
0084   ClusterCollection clusters;
0085   Acts::Ccl::createClusters<CellCollection, ClusterCollection, 1>(
0086       data, cells, clusters, Acts::Ccl::TimedConnect<Cell, 1>(0.5));
0087
0088   BOOST_CHECK_EQUAL(5ul, clusters.size());
0089
0090   for (std::size_t i(0); i < clusters.size(); ++i) {
0091     std::vector<Identifier>& timedIds = clusters[i].ids;
0092     const std::vector<Identifier>& expected = expectedResults[i];
0093     std::ranges::sort(timedIds);
0094     BOOST_CHECK_EQUAL(timedIds.size(), expected.size());
0095
0096     for (std::size_t j(0); j < timedIds.size(); ++j) {
0097       BOOST_CHECK_EQUAL(timedIds[j], expected[j]);
0098     }
0099   }
0100 }
0101
0102 BOOST_AUTO_TEST_CASE(TimedGrid_1D_duplicate_cells) {
0103   // Cells with same position but time difference larger than tolerance should
0104   // not be considered duplicates
0105   CellCollection cells = {Cell(0ul, 0, 0, 0.0), Cell(1ul, 0, 0, 1.0)};
0106   ClusterCollection clusters;
0107   Ccl::ClusteringData data;
0108
0109   Ccl::createClusters<CellCollection, ClusterCollection, 1>(
0110       data, cells, clusters, Ccl::TimedConnect<Cell, 1>(0.5));
0111   BOOST_CHECK_EQUAL(2ul, clusters.size());
0112
0113   // Cells with same position and time difference within tolerance should be
0114   // considered duplicates
0115   cells = {Cell(0ul, 0, 0, 0.0), Cell(1ul, 0, 0, 0.4)};
0116   clusters.clear();
0117   data.clear();
0118
0119   BOOST_CHECK_THROW(
0120       (Ccl::createClusters<CellCollection, ClusterCollection, 1>(
0121           data, cells, clusters, Ccl::TimedConnect<Cell, 1>(0.5))),
0122       std::invalid_argument);
0123 }
0124
0125 BOOST_AUTO_TEST_CASE(TimedGrid_1D_space_and_time) {
0126   // Cells with the same position but large time differences are not duplicates.
0127   // However, they can still be clustered through a neighboring cell if it is
0128   // within the time tolerance for both.
0129   CellCollection cells = {Cell(0ul, 0, 0, 0.0), Cell(1ul, 1, 0, 0.4),
0130                           Cell(2ul, 0, 0, 0.8)};
0131   ClusterCollection clusters;
0132   Ccl::ClusteringData data;
0133
0134   Ccl::createClusters<CellCollection, ClusterCollection, 1>(
0135       data, cells, clusters, Ccl::TimedConnect<Cell, 1>(0.5));
0136   BOOST_CHECK_EQUAL(1ul, clusters.size());
0137   BOOST_CHECK_EQUAL(clusters[0].ids.size(), 3ul);
0138 }
0139
0140 BOOST_AUTO_TEST_CASE(TimedGrid_2D_notime) {
0141   // 4x4 matrix
0142   /*
0143     X O O X
0144     O O O X
0145     X X O O
0146     X O O X
0147   */
0148   // 7 cells -> 4 clusters in total
0149
0150   std::vector<Cell> cells;
0151   cells.emplace_back(0ul, 0, 0, 0);
0152   cells.emplace_back(1ul, 3, 0, 0);
0153   cells.emplace_back(2ul, 3, 1, 0);
0154   cells.emplace_back(3ul, 0, 2, 0);
0155   cells.emplace_back(4ul, 1, 2, 0);
0156   cells.emplace_back(5ul, 0, 3, 0);
0157   cells.emplace_back(6ul, 3, 3, 0);
0158
0159   std::vector<std::vector<Identifier>> expectedResults;
0160   expectedResults.push_back({0ul});
0161   expectedResults.push_back({3ul, 4ul, 5ul});
0162   expectedResults.push_back({1ul, 2ul});
0163   expectedResults.push_back({6ul});
0164
0165   Acts::Ccl::ClusteringData data;
0166   ClusterCollection clusters;
0167   Acts::Ccl::createClusters<CellCollection, ClusterCollection, 2>(
0168       data, cells, clusters,
0169       Acts::Ccl::TimedConnect<Cell, 2>(std::numeric_limits<double>::max()));
0170
0171   BOOST_CHECK_EQUAL(4ul, clusters.size());
0172
0173   // Compare against default connect (only space)
0174   data.clear();
0175   ClusterCollection defaultClusters;
0176   Acts::Ccl::createClusters<CellCollection, ClusterCollection, 2>(
0177       data, cells, defaultClusters, Acts::Ccl::DefaultConnect<Cell, 2>());
0178
0179   BOOST_CHECK_EQUAL(4ul, defaultClusters.size());
0180   BOOST_CHECK_EQUAL(defaultClusters.size(), expectedResults.size());
0181
0182   std::vector<std::size_t> sizes{1, 3, 2, 1};
0183   for (std::size_t i(0); i < clusters.size(); ++i) {
0184     std::vector<Identifier>& timedIds = clusters[i].ids;
0185     std::vector<Identifier>& defaultIds = defaultClusters[i].ids;
0186     const std::vector<Identifier>& expected = expectedResults[i];
0187     BOOST_CHECK_EQUAL(timedIds.size(), defaultIds.size());
0188     BOOST_CHECK_EQUAL(timedIds.size(), sizes[i]);
0189     BOOST_CHECK_EQUAL(timedIds.size(), expected.size());
0190
0191     std::ranges::sort(timedIds);
0192     std::ranges::sort(defaultIds);
0193     for (std::size_t j(0); j < timedIds.size(); ++j) {
0194       BOOST_CHECK_EQUAL(timedIds[j], defaultIds[j]);
0195       BOOST_CHECK_EQUAL(timedIds[j], expected[j]);
0196     }
0197   }
0198 }
0199
0200 BOOST_AUTO_TEST_CASE(TimedGrid_2D_withtime) {
0201   // 4x4 matrix
0202   /*
0203     X Y O X
0204     O Y Y X
0205     X X Z Z
0206     X O O X
0207   */
0208   // 7 + 3 + 2 cells -> 4 + 1 + 1 clusters in total
0209
0210   std::vector<Cell> cells;
0211   // X
0212   cells.emplace_back(0ul, 0, 0, 0);
0213   cells.emplace_back(1ul, 3, 0, 0);
0214   cells.emplace_back(2ul, 3, 1, 0);
0215   cells.emplace_back(3ul, 0, 2, 0);
0216   cells.emplace_back(4ul, 1, 2, 0);
0217   cells.emplace_back(5ul, 0, 3, 0);
0218   cells.emplace_back(6ul, 3, 3, 0);
0219   // Y
0220   cells.emplace_back(7ul, 1, 0, 1);
0221   cells.emplace_back(8ul, 1, 1, 1);
0222   cells.emplace_back(9ul, 2, 1, 1);
0223   // Z
0224   cells.emplace_back(10ul, 2, 2, 2);
0225   cells.emplace_back(11ul, 3, 2, 2);
0226
0227   std::vector<std::vector<Identifier>> expectedResults;
0228   expectedResults.push_back({0ul});
0229   expectedResults.push_back({3ul, 4ul, 5ul});
0230   expectedResults.push_back({7ul, 8ul, 9ul});
0231   expectedResults.push_back({10ul, 11ul});
0232   expectedResults.push_back({1ul, 2ul});
0233   expectedResults.push_back({6ul});
0234
0235   Acts::Ccl::ClusteringData data;
0236   ClusterCollection clusters;
0237   Acts::Ccl::createClusters<CellCollection, ClusterCollection, 2>(
0238       data, cells, clusters, Acts::Ccl::TimedConnect<Cell, 2>(0.5));
0239
0240   BOOST_CHECK_EQUAL(6ul, clusters.size());
0241
0242   std::vector<std::size_t> sizes{1, 3, 3, 2, 2, 1};
0243   for (std::size_t i(0); i < clusters.size(); ++i) {
0244     std::vector<Identifier>& timedIds = clusters[i].ids;
0245     BOOST_CHECK_EQUAL(timedIds.size(), sizes[i]);
0246     std::ranges::sort(timedIds);
0247
0248     const std::vector<Identifier>& expected = expectedResults[i];
0249     BOOST_CHECK_EQUAL(timedIds.size(), expected.size());
0250
0251     for (std::size_t j(0); j < timedIds.size(); ++j) {
0252       BOOST_CHECK_EQUAL(timedIds[j], expected[j]);
0253     }
0254   }
0255 }
0256
0257 BOOST_AUTO_TEST_CASE(TimedGrid_2D_noTollerance) {
0258   // 4x4 matrix
0259   /*
0260     X O O X
0261     O O O X
0262     X X O O
0263     X O O X
0264    */
0265   // 7 cells -> 7 clusters in total
0266   // since time requirement will never be satisfied
0267
0268   std::vector<Cell> cells;
0269   cells.emplace_back(0ul, 0, 0, 0);
0270   cells.emplace_back(1ul, 3, 0, 0);
0271   cells.emplace_back(2ul, 3, 1, 0);
0272   cells.emplace_back(3ul, 0, 2, 0);
0273   cells.emplace_back(4ul, 1, 2, 0);
0274   cells.emplace_back(5ul, 0, 3, 0);
0275   cells.emplace_back(6ul, 3, 3, 0);
0276
0277   std::vector<std::vector<Identifier>> expectedResults;
0278   expectedResults.push_back({0ul});
0279   expectedResults.push_back({3ul});
0280   expectedResults.push_back({5ul});
0281   expectedResults.push_back({4ul});
0282   expectedResults.push_back({1ul});
0283   expectedResults.push_back({2ul});
0284   expectedResults.push_back({6ul});
0285
0286   Acts::Ccl::ClusteringData data;
0287   ClusterCollection clusters;
0288   Acts::Ccl::createClusters<CellCollection, ClusterCollection, 2>(
0289       data, cells, clusters, Acts::Ccl::TimedConnect<Cell, 2>(0.));
0290
0291   BOOST_CHECK_EQUAL(7ul, clusters.size());
0292
0293   for (std::size_t i(0); i < clusters.size(); ++i) {
0294     std::vector<Identifier>& timedIds = clusters[i].ids;
0295     const std::vector<Identifier>& expected = expectedResults[i];
0296
0297     BOOST_CHECK_EQUAL(timedIds.size(), 1);
0298     BOOST_CHECK_EQUAL(timedIds.size(), expected.size());
0299     BOOST_CHECK_EQUAL(timedIds[0], expected[0]);
0300   }
0301 }
0302
0303 BOOST_AUTO_TEST_CASE(TimedGrid_2D_duplicate_cells) {
0304   // Cells with same position but time difference larger than tolerance should
0305   // not be considered duplicates
0306   CellCollection cells = {Cell(0ul, 0, 0, 0.0), Cell(1ul, 0, 0, 1.0)};
0307   ClusterCollection clusters;
0308   Ccl::ClusteringData data;
0309
0310   Ccl::createClusters<CellCollection, ClusterCollection, 2>(
0311       data, cells, clusters, Ccl::TimedConnect<Cell, 2>(0.5));
0312   BOOST_CHECK_EQUAL(2ul, clusters.size());
0313
0314   // Cells with same position and time difference within tolerance should be
0315   // considered duplicates
0316   cells = {Cell(0ul, 0, 0, 0.0), Cell(1ul, 0, 0, 0.4)};
0317   clusters.clear();
0318   data.clear();
0319
0320   BOOST_CHECK_THROW(
0321       (Ccl::createClusters<CellCollection, ClusterCollection, 2>(
0322           data, cells, clusters, Ccl::TimedConnect<Cell, 2>(0.5))),
0323       std::invalid_argument);
0324 }
0325
0326 BOOST_AUTO_TEST_CASE(TimedGrid_2D_space_and_time_conn4) {
0327   // Cells with the same position but large time differences are not duplicates.
0328   // However, they can still be clustered through a neighboring cell if it is
0329   // within the time tolerance for both:
0330   // 3x3 matrix
0331   /*
0332     O  X/Z  O
0333    X/Z  Y  X/Z
0334     O  X/Z  O
0335   */
0336   CellCollection cells = {
0337       Cell(0ul, 1, 0, 0.0), Cell(1ul, 0, 1, 0.0), Cell(2ul, 2, 1, 0.0),
0338       Cell(3ul, 1, 2, 0.0), Cell(4ul, 1, 0, 0.8), Cell(5ul, 0, 1, 0.8),
0339       Cell(6ul, 2, 1, 0.8), Cell(7ul, 1, 2, 0.8), Cell(8ul, 1, 1, 0.4)};
0340   ClusterCollection clusters;
0341   Ccl::ClusteringData data;
0342
0343   Ccl::createClusters<CellCollection, ClusterCollection, 2>(
0344       data, cells, clusters, Ccl::TimedConnect<Cell, 2>(0.5, false));
0345   BOOST_CHECK_EQUAL(1ul, clusters.size());
0346   BOOST_CHECK_EQUAL(clusters[0].ids.size(), 9ul);
0347 }
0348
0349 BOOST_AUTO_TEST_CASE(TimedGrid_2D_space_and_time_conn8) {
0350   // Cells with the same position but large time differences are not duplicates.
0351   // However, they can still be clustered through a neighboring cell if it is
0352   // within the time tolerance for both:
0353   // 3x3 matrix
0354   /*
0355     Z   X   O
0356     X   Y   O
0357    X/Z  O   O
0358   */
0359   CellCollection cells = {Cell(0ul, 0, 0, 0.0), Cell(1ul, 0, 2, 0.0),
0360                           Cell(2ul, 1, 0, 0.8), Cell(3ul, 0, 1, 0.8),
0361                           Cell(4ul, 0, 2, 0.8), Cell(5ul, 1, 1, 0.4)};
0362   ClusterCollection clusters;
0363   Ccl::ClusteringData data;
0364
0365   Ccl::createClusters<CellCollection, ClusterCollection, 2>(
0366       data, cells, clusters, Ccl::TimedConnect<Cell, 2>(0.5, true));
0367   BOOST_CHECK_EQUAL(1ul, clusters.size());
0368   BOOST_CHECK_EQUAL(clusters[0].ids.size(), 6ul);
0369 }
0370
0371 BOOST_AUTO_TEST_SUITE_END()