Core/TrackFinding/SeedDeduplicatorTests.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/TrackFinding/SeedDeduplicator.hpp"
0012
0013 #include <limits>
0014 #include <numeric>
0015 #include <span>
0016 #include <vector>
0017
0018 using namespace Acts;
0019
0020 namespace ActsTests {
0021
0022 using MeasurementKey = SeedDeduplicator::MeasurementKey;
0023
0024 /// Find the smallest number of seed keys that one track must hold to make a
0025 /// seed of `nKeys` keys a duplicate
0026 MeasurementKey requiredSharedKeys(const SeedDeduplicator::Config& config,
0027                                   MeasurementKey nMeasKeys) {
0028   std::vector<MeasurementKey> seed(nMeasKeys);
0029   std::iota(seed.begin(), seed.end(), MeasurementKey{0});
0030   for (MeasurementKey nShared = 1; nShared <= nMeasKeys; ++nShared) {
0031     SeedDeduplicator dedup(config);
0032     dedup.reset(nMeasKeys);
0033     dedup.addTrack(std::span(seed).first(nShared));
0034     if (dedup.isDuplicate(seed)) {
0035       return nShared;
0036     }
0037   }
0038   return nMeasKeys + 1;
0039 }
0040
0041 BOOST_AUTO_TEST_SUITE(TrackFindingSuite)
0042
0043 BOOST_AUTO_TEST_CASE(SeedDeduplicatorThreshold) {
0044   // all keys, the default
0045   BOOST_CHECK_EQUAL(requiredSharedKeys({}, 1), 1u);
0046   BOOST_CHECK_EQUAL(requiredSharedKeys({}, 3), 3u);
0047
0048   // N - 1, never below 1
0049   const SeedDeduplicator::Config relative{.minScore = 0, .maxMissingScore = 1};
0050   BOOST_CHECK_EQUAL(requiredSharedKeys(relative, 1), 1u);
0051   BOOST_CHECK_EQUAL(requiredSharedKeys(relative, 3), 2u);
0052   BOOST_CHECK_EQUAL(requiredSharedKeys(relative, 6), 5u);
0053
0054   // max(3, N - 2), never above N
0055   const SeedDeduplicator::Config both{.minScore = 3, .maxMissingScore = 2};
0056   BOOST_CHECK_EQUAL(requiredSharedKeys(both, 2), 2u);
0057   BOOST_CHECK_EQUAL(requiredSharedKeys(both, 3), 3u);
0058   BOOST_CHECK_EQUAL(requiredSharedKeys(both, 5), 3u);
0059   BOOST_CHECK_EQUAL(requiredSharedKeys(both, 6), 4u);
0060   BOOST_CHECK_EQUAL(requiredSharedKeys(both, 8), 6u);
0061 }
0062
0063 BOOST_AUTO_TEST_CASE(SeedDeduplicatorAllKeys) {
0064   SeedDeduplicator dedup({});
0065   dedup.reset(10);
0066
0067   BOOST_CHECK(!dedup.isDuplicate(std::vector<MeasurementKey>{0, 1, 2}));
0068
0069   dedup.addTrack(std::vector<MeasurementKey>{0, 1, 2, 3});
0070   BOOST_CHECK_EQUAL(dedup.nTracks(), 1u);
0071
0072   BOOST_CHECK(dedup.isDuplicate(std::vector<MeasurementKey>{0, 1, 2}));
0073   BOOST_CHECK(dedup.isDuplicate(std::vector<MeasurementKey>{3, 1, 0}));
0074   BOOST_CHECK(!dedup.isDuplicate(std::vector<MeasurementKey>{0, 1, 4}));
0075   BOOST_CHECK(!dedup.isDuplicate(std::vector<MeasurementKey>{}));
0076 }
0077
0078 BOOST_AUTO_TEST_CASE(SeedDeduplicatorTracksDoNotAdd) {
0079   SeedDeduplicator dedup({.minScore = 0, .maxMissingScore = 1});
0080   dedup.reset(10);
0081
0082   // each track holds one key of the seed, the union holds all three
0083   dedup.addTrack(std::vector<MeasurementKey>{0, 5});
0084   dedup.addTrack(std::vector<MeasurementKey>{1, 6});
0085   dedup.addTrack(std::vector<MeasurementKey>{2, 7});
0086   BOOST_CHECK(!dedup.isDuplicate(std::vector<MeasurementKey>{0, 1, 2}));
0087
0088   // a track with two of the three keys
0089   dedup.addTrack(std::vector<MeasurementKey>{1, 2, 8});
0090   BOOST_CHECK(dedup.isDuplicate(std::vector<MeasurementKey>{0, 1, 2}));
0091 }
0092
0093 BOOST_AUTO_TEST_CASE(SeedDeduplicatorSharedKeys) {
0094   SeedDeduplicator dedup({});
0095   dedup.reset(10);
0096
0097   // both tracks hold key 1
0098   dedup.addTrack(std::vector<MeasurementKey>{0, 1, 2});
0099   dedup.addTrack(std::vector<MeasurementKey>{1, 3, 4});
0100   BOOST_CHECK(dedup.isDuplicate(std::vector<MeasurementKey>{0, 1, 2}));
0101   BOOST_CHECK(dedup.isDuplicate(std::vector<MeasurementKey>{1, 3, 4}));
0102   BOOST_CHECK(!dedup.isDuplicate(std::vector<MeasurementKey>{0, 1, 3}));
0103 }
0104
0105 BOOST_AUTO_TEST_CASE(SeedDeduplicatorRepeatedTrackKey) {
0106   SeedDeduplicator dedup({});
0107   dedup.reset(10);
0108
0109   // a key that occurs twice on a track counts once
0110   dedup.addTrack(std::vector<MeasurementKey>{0, 0, 1});
0111   BOOST_CHECK(!dedup.isDuplicate(std::vector<MeasurementKey>{0, 1, 2}));
0112   BOOST_CHECK(dedup.isDuplicate(std::vector<MeasurementKey>{0, 1}));
0113 }
0114
0115 BOOST_AUTO_TEST_CASE(SeedDeduplicatorWeights) {
0116   // pixel weight 2, strip weight 1, at least 5 shared constraints
0117   SeedDeduplicator dedup(
0118       {.minScore = 5,
0119        .maxMissingScore = std::numeric_limits<SeedDeduplicator::Score>::max()});
0120   dedup.reset(10);
0121   for (MeasurementKey measKey : {0u, 1u, 2u}) {
0122     dedup.setWeight(measKey, 2);
0123   }
0124   BOOST_CHECK_EQUAL(dedup.weight(0), 2u);
0125   BOOST_CHECK_EQUAL(dedup.weight(3), 1u);
0126
0127   dedup.addTrack(std::vector<MeasurementKey>{0, 1, 3, 4, 5});
0128
0129   // pixel doublet on the track: score 4 of 6
0130   BOOST_CHECK(!dedup.isDuplicate(std::vector<MeasurementKey>{0, 1, 2}));
0131   // two pixels and one strip on the track: score 5 of 6
0132   BOOST_CHECK(dedup.isDuplicate(std::vector<MeasurementKey>{0, 1, 3, 9}));
0133   // strip seed, three of four strips on the track: score 3 of 4
0134   BOOST_CHECK(!dedup.isDuplicate(std::vector<MeasurementKey>{3, 4, 5, 9}));
0135   // strip triplet, five of six strips on one track
0136   dedup.addTrack(std::vector<MeasurementKey>{3, 4, 5, 6, 7});
0137   BOOST_CHECK(dedup.isDuplicate(std::vector<MeasurementKey>{3, 4, 5, 6, 7, 9}));
0138
0139   // a seed of zero weight is never a duplicate
0140   dedup.setWeight(8, 0);
0141   dedup.addTrack(std::vector<MeasurementKey>{8});
0142   BOOST_CHECK(!dedup.isDuplicate(std::vector<MeasurementKey>{8}));
0143 }
0144
0145 BOOST_AUTO_TEST_CASE(SeedDeduplicatorReset) {
0146   SeedDeduplicator dedup({});
0147   dedup.reset(5);
0148   dedup.setWeight(0, 3);
0149   dedup.addTrack(std::vector<MeasurementKey>{0, 1});
0150   BOOST_CHECK(dedup.isDuplicate(std::vector<MeasurementKey>{0, 1}));
0151
0152   dedup.reset(5);
0153   BOOST_CHECK_EQUAL(dedup.nTracks(), 0u);
0154   BOOST_CHECK_EQUAL(dedup.weight(0), 1u);
0155   BOOST_CHECK(!dedup.isDuplicate(std::vector<MeasurementKey>{0, 1}));
0156 }
0157
0158 BOOST_AUTO_TEST_SUITE_END()
0159
0160 }  // namespace ActsTests