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   /// Configuration parameters for greedy ambiguity resolution.
0037   struct Config {
0038     /// Maximum amount of shared hits per track.
0039     std::uint32_t maximumSharedHits = 1;
0040     /// Maximum number of iterations
0041     std::uint32_t maximumIterations = 1000;
0042
0043     /// Minimum number of measurement to form a track.
0044     std::size_t nMeasurementsMin = 7;
0045   };
0046
0047   /// Mutable state used by the greedy ambiguity resolution.
0048   struct State {
0049     /// Total number of tracks
0050     std::size_t numberOfTracks{};
0051
0052     /// Track tips for each track
0053     std::vector<int> trackTips;
0054     /// Chi-squared value for each track
0055     std::vector<float> trackChi2;
0056     /// Measurement indices for each track
0057     std::vector<std::vector<std::size_t>> measurementsPerTrack;
0058
0059     // TODO consider boost 1.81 unordered_flat_map
0060     /// Map from measurement index to set of track indices using it
0061     boost::container::flat_map<std::size_t,
0062                                boost::container::flat_set<std::size_t>>
0063         tracksPerMeasurement;
0064     /// Number of shared measurements for each track
0065     std::vector<std::size_t> sharedMeasurementsPerTrack;
0066
0067     // TODO consider boost 1.81 unordered_flat_map
0068     /// Set of track indices selected as good tracks
0069     boost::container::flat_set<std::size_t> selectedTracks;
0070   };
0071
0072   /// Constructor with configuration and logger
0073   /// @param cfg Configuration for ambiguity resolution
0074   /// @param logger Logger for diagnostic output
0075   explicit GreedyAmbiguityResolution(
0076       const Config& cfg,
0077       std::unique_ptr<const Logger> logger =
0078           getDefaultLogger("GreedyAmbiguityResolution", Logging::INFO))
0079       : m_cfg{cfg}, m_logger{std::move(logger)} {}
0080
0081   /// Computes the initial state for the input data. This function accumulates
0082   /// information that will later be used to accelerate the ambiguity
0083   /// resolution.
0084   ///
0085   /// @param tracks The input track container.
0086   /// @param state An empty state object which is expected to be default constructed.
0087   /// @param sourceLinkHash A functor to acquire a hash from a given source link.
0088   /// @param sourceLinkEquality A functor to check equality of two source links.
0089   template <TrackContainerFrontend track_container_t,
0090             typename source_link_hash_t, typename source_link_equality_t>
0091   void computeInitialState(const track_container_t& tracks, State& state,
0092                            source_link_hash_t&& sourceLinkHash,
0093                            source_link_equality_t&& sourceLinkEquality) const;
0094
0095   /// Updates the state iteratively by evicting one track after the other until
0096   /// the final state conditions are met.
0097   ///
0098   /// @param state A state object that was previously filled by the initialization.
0099   void resolve(State& state) const;
0100
0101  private:
0102   Config m_cfg;
0103
0104   /// Logging instance
0105   std::unique_ptr<const Logger> m_logger;
0106
0107   /// Private access to logging instance
0108   const Logger& logger() const { return *m_logger; }
0109 };
0110
0111 }  // namespace Acts
0112
0113 #include "Acts/AmbiguityResolution/GreedyAmbiguityResolution.ipp"