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