Acts/AmbiguityResolution/GreedyAmbiguityResolution.hpp

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 #pragma once
0010
0011 #include "Acts/EventData/MultiTrajectoryHelpers.hpp"
0012 #include "Acts/EventData/SourceLink.hpp"
0013 #include "Acts/EventData/TrackContainer.hpp"
0014 #include "Acts/EventData/TrackContainerFrontendConcept.hpp"
0015 #include "Acts/Utilities/Delegate.hpp"
0016 #include "Acts/Utilities/Logger.hpp"
0017
0018 #include <memory>
0019
0020 #include <boost/container/flat_map.hpp>
0021 #include <boost/container/flat_set.hpp>
0022
0023 namespace Acts {
0024
0025 /// Evicts tracks that seem to be duplicates or fakes. This algorithm takes a
0026 /// greedy approach in the sense that it will remove the track which looks "most
0027 /// duplicate/fake" first and continues the same process with the rest. That
0028 /// process continues until the final state conditions are met.
0029 ///
0030 /// The implementation works as follows:
0031 ///  1) Calculate shared hits per track.
0032 ///  2) If the maximum shared hits criteria is met, we are done.
0033 ///     This is the configurable amount of shared hits we are ok with
0034 ///     in our experiment.
0035 ///  3) Else, remove the track with the highest relative shared hits (i.e.
0036 ///     shared hits / hits).
0037 ///  4) Back to square 1.
0038 class GreedyAmbiguityResolution {
0039  public:
0040   struct Config {
0041     /// Maximum amount of shared hits per track.
0042     std::uint32_t maximumSharedHits = 1;
0043     /// Maximum number of iterations
0044     std::uint32_t maximumIterations = 1000;
0045
0046     /// Minimum number of measurement to form a track.
0047     std::size_t nMeasurementsMin = 7;
0048   };
0049
0050   struct State {
0051     std::size_t numberOfTracks{};
0052
0053     std::vector<int> trackTips;
0054     std::vector<float> trackChi2;
0055     std::vector<std::vector<std::size_t>> measurementsPerTrack;
0056
0057     // TODO consider boost 1.81 unordered_flat_map
0058     boost::container::flat_map<std::size_t,
0059                                boost::container::flat_set<std::size_t>>
0060         tracksPerMeasurement;
0061     std::vector<std::size_t> sharedMeasurementsPerTrack;
0062
0063     // TODO consider boost 1.81 unordered_flat_map
0064     boost::container::flat_set<std::size_t> selectedTracks;
0065   };
0066
0067   GreedyAmbiguityResolution(const Config& cfg,
0068                             std::unique_ptr<const Logger> logger =
0069                                 getDefaultLogger("GreedyAmbiguityResolution",
0070                                                  Logging::INFO))
0071       : m_cfg{cfg}, m_logger{std::move(logger)} {}
0072
0073   /// Computes the initial state for the input data. This function accumulates
0074   /// information that will later be used to accelerate the ambiguity
0075   /// resolution.
0076   ///
0077   /// @param tracks The input track container.
0078   /// @param state An empty state object which is expected to be default constructed.
0079   /// @param sourceLinkHash A functor to acquire a hash from a given source link.
0080   /// @param sourceLinkEquality A functor to check equality of two source links.
0081   template <TrackContainerFrontend track_container_t,
0082             typename source_link_hash_t, typename source_link_equality_t>
0083   void computeInitialState(const track_container_t& tracks, State& state,
0084                            source_link_hash_t&& sourceLinkHash,
0085                            source_link_equality_t&& sourceLinkEquality) const;
0086
0087   /// Updates the state iteratively by evicting one track after the other until
0088   /// the final state conditions are met.
0089   ///
0090   /// @param state A state object that was previously filled by the initialization.
0091   void resolve(State& state) const;
0092
0093  private:
0094   Config m_cfg;
0095
0096   /// Logging instance
0097   std::unique_ptr<const Logger> m_logger;
0098
0099   /// Private access to logging instance
0100   const Logger& logger() const { return *m_logger; }
0101 };
0102
0103 }  // namespace Acts
0104
0105 #include "Acts/AmbiguityResolution/GreedyAmbiguityResolution.ipp"