Acts/AmbiguityResolution/GreedyAmbiguityResolution.hpp

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