WeightedTreeTraversal< AStateRejecter, AState, AResult > Class Template Reference

General implementation of a tree search algorithm using a given classes as state and results and one strategy class to decide, which child states should be traversed next. More...

#include <WeightedTreeTraversal.h>

Inheritance diagram for WeightedTreeTraversal< AStateRejecter, AState, AResult >:

Public Types
using	IOTypes = std::tuple< AIOTypes... >
	Types that should be served to apply on invocation.
using	IOVectors = std::tuple< std::vector< AIOTypes >... >
	Vector types that should be served to apply on invocation.

Public Member Functions
	WeightedTreeTraversal ()
	Construct this findlet and add the subfindlet as listener.
void	exposeParameters (ModuleParamList *moduleParamList, const std::string &prefix) final
	Expose the parameters of the subfindlet.
void	apply (const std::vector< const AState * > &seededStates, const std::vector< WeightedRelation< AState > > &stateRelations, std::vector< AResult > &results) override
	Main function of this findlet: traverse a tree starting from a given seed states.
virtual std::string	getDescription ()
	Brief description of the purpose of the concrete findlet.
virtual void	apply (ToVector< AIOTypes > &... ioVectors)=0
	Main function executing the algorithm.
void	initialize () override
	Receive and dispatch signal before the start of the event processing.
void	beginRun () override
	Receive and dispatch signal for the beginning of a new run.
void	beginEvent () override
	Receive and dispatch signal for the start of a new event.
void	endRun () override
	Receive and dispatch signal for the end of the run.
void	terminate () override
	Receive and dispatch Signal for termination of the event processing.

Protected Types
template<class T >
using	ToVector = typename ToVectorImpl< T >::Type
	Short hand for ToRangeImpl.

Protected Member Functions
void	addProcessingSignalListener (ProcessingSignalListener *psl)
	Register a processing signal listener to be notified.
int	getNProcessingSignalListener ()
	Get the number of currently registered listeners.

Private Types
using	Super = Findlet< const AState *const, const WeightedRelation< AState >, AResult >
	Parent class.

Private Member Functions
void	traverseTree (std::vector< const AState * > &path, const std::vector< WeightedRelation< AState > > &stateRelations, std::vector< AResult > &results)
	Implementation of the traverseTree function.

Private Attributes
AStateRejecter	m_stateRejecter
	State rejecter to decide which available continuations should be traversed next.
std::vector< ProcessingSignalListener * >	m_subordinaryProcessingSignalListeners
	References to subordinary signal processing listener contained in this findlet.
bool	m_initialized = false
	Flag to keep track whether initialization happened before.
bool	m_terminated = false
	Flag to keep track whether termination happened before.
std::string	m_initializedAs
	Name of the type during initialisation.

Detailed Description

template<class AStateRejecter, class AState, class AResult = std::vector<const AState*>>
class Belle2::TrackFindingCDC::WeightedTreeTraversal< AStateRejecter, AState, AResult >

General implementation of a tree search algorithm using a given classes as state and results and one strategy class to decide, which child states should be traversed next.

Requirements for the template parameters:

• AState: No requirements
• AResult: Must be constructable from std::vector<const AState*>

• AStateRejecter: Should be roughly of type Findlet<const AState* const, WithWeight<AState*> > with an apply method like:

  apply(const std::vector<const AState*>& currentPath, std::vector<WithWeight<AState*> >& nextStates);

  Therefore it receives the current path and a list of potential next states with an apriori Weight, that it should sort out for viable continuations to traverse next.

  The StateRejecter is allowed to adjust the nextStates for book keeping purposes, but should generally avoid to adjust the states in the currentPath to not interfere with the traversal of earlier siblings.

Definition at line 52 of file WeightedTreeTraversal.h.

Member Typedef Documentation

IOTypes

using IOTypes = std::tuple<AIOTypes...>

inherited

Types that should be served to apply on invocation.

Definition at line 30 of file Findlet.h.

IOVectors

using IOVectors = std::tuple< std::vector<AIOTypes>... >

inherited

Vector types that should be served to apply on invocation.

Definition at line 53 of file Findlet.h.

Super

using Super = Findlet<const AState* const, const WeightedRelation<AState>, AResult>

private

Parent class.

Definition at line 56 of file WeightedTreeTraversal.h.

ToVector

using ToVector = typename ToVectorImpl<T>::Type

protectedinherited

Short hand for ToRangeImpl.

Definition at line 49 of file Findlet.h.

Constructor & Destructor Documentation

WeightedTreeTraversal()

WeightedTreeTraversal ( )

inline

Construct this findlet and add the subfindlet as listener.

Definition at line 60 of file WeightedTreeTraversal.h.

        : Super()
      {
        Super::addProcessingSignalListener(&m_stateRejecter);
      }

Member Function Documentation

addProcessingSignalListener()

void addProcessingSignalListener ( ProcessingSignalListener *  psl )

protectedinherited

Register a processing signal listener to be notified.

Definition at line 55 of file CompositeProcessingSignalListener.cc.

{
  m_subordinaryProcessingSignalListeners.push_back(psl);
}

apply()

void apply ( const std::vector< const AState * > &  seededStates, const std::vector< WeightedRelation< AState > > &  stateRelations, std::vector< AResult > &  results  )

override

Main function of this findlet: traverse a tree starting from a given seed states.

ATTENTION: As described above, the states themselves can be altered during the tree traversal.

Definition at line 94 of file WeightedTreeTraversal.h.

    {
      std::vector<const AState*> path;
      for (const AState* state : seededStates) {
        B2DEBUG(25, "Starting with new seed...");
        path.push_back(state);
        traverseTree(path, stateRelations, results);
        path.pop_back();
        B2DEBUG(25, "... finished with seed");
      }
      assert(path.empty());
    }

beginEvent()

void beginEvent ( )

overridevirtualinherited

Receive and dispatch signal for the start of a new event.

Reimplemented from ProcessingSignalListener.

Reimplemented in SpacePointTagger< Belle2::CKFToPXDResult, Belle2::PXDCluster >, SpacePointTagger< Belle2::CKFToSVDResult, Belle2::SVDCluster >, BaseEventTimeExtractor< RecoTrack * >, BaseEventTimeExtractor< TrackFindingCDC::CDCWireHit & >, SharingHitsMatcher< Belle2::TrackFindingCDC::CDCTrack, Belle2::TrackFindingCDC::CDCSegment2D >, MCSymmetric< BaseAxialSegmentPairFilter >, MCSymmetric< BaseFacetFilter >, MCSymmetric< BaseFacetRelationFilter >, MCSymmetric< BaseSegmentPairFilter >, MCSymmetric< BaseSegmentPairRelationFilter >, MCSymmetric< BaseSegmentRelationFilter >, MCSymmetric< BaseSegmentTripleFilter >, MCSymmetric< BaseSegmentTripleRelationFilter >, MCSymmetric< BaseTrackRelationFilter >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCFacet >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCWireHit, true >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCSegment2D >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCTrack >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCSegmentPair >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCSegmentTriple >, RecoTrackStorer, ROIFinder, and SVDHoughTracking.

Definition at line 31 of file CompositeProcessingSignalListener.cc.

{
  Super::beginEvent();
  for (ProcessingSignalListener* psl : m_subordinaryProcessingSignalListeners) {
    psl->beginEvent();
  }
}

beginRun()

void beginRun ( )

overridevirtualinherited

Receive and dispatch signal for the beginning of a new run.

Reimplemented from ProcessingSignalListener.

Reimplemented in LayerRelationFilter< AFilter >, FourHitFilter, QualityIndicatorFilter, ThreeHitFilter, TwoHitVirtualIPFilter, TwoHitVirtualIPQIFilter, RecoTrackStorer, ROIFinder, SpacePointLoaderAndPreparer, and TrackCandidateResultRefiner.

Definition at line 23 of file CompositeProcessingSignalListener.cc.

{
  Super::beginRun();
  for (ProcessingSignalListener* psl : m_subordinaryProcessingSignalListeners) {
    psl->beginRun();
  }
}

endRun()

void endRun ( )

overridevirtualinherited

Receive and dispatch signal for the end of the run.

Reimplemented from ProcessingSignalListener.

Definition at line 39 of file CompositeProcessingSignalListener.cc.

{
  for (ProcessingSignalListener* psl : reversedRange(m_subordinaryProcessingSignalListeners)) {
    psl->endRun();
  }
  Super::endRun();
}

exposeParameters()

void exposeParameters ( ModuleParamList *  moduleParamList, const std::string &  prefix  )

inlinefinalvirtual

Expose the parameters of the subfindlet.

Reimplemented from Findlet< AIOTypes >.

Definition at line 67 of file WeightedTreeTraversal.h.

      {
        m_stateRejecter.exposeParameters(moduleParamList, prefix);
      }

getDescription()

virtual std::string getDescription ( )

inlinevirtualinherited

Brief description of the purpose of the concrete findlet.

Reimplemented in CosmicsTrackMergerFindlet, CDCTrackingEventLevelMdstInfoFillerFromHitsFindlet, CDCTrackingEventLevelMdstInfoFillerFromSegmentsFindlet, AxialStraightTrackFinder, AxialTrackFinderHough, AxialTrackFinderLegendre, ClusterPreparer, MonopoleAxialTrackFinderLegendre, MonopoleStereoHitFinder, MonopoleStereoHitFinderQuadratic, SegmentFinderFacetAutomaton, SegmentTrackCombiner, StereoHitFinder, TrackFinderSegmentPairAutomaton, TrackFinderSegmentTripleAutomaton, TrackQualityEstimator, WireHitPreparer, AsicBackgroundLibraryCreator, TrackFinderCosmics, AsicBackgroundDetector, AxialSegmentPairCreator, AxialStraightTrackCreator, AxialTrackCreatorHitHough, AxialTrackCreatorHitLegendre, AxialTrackCreatorMCTruth, AxialTrackCreatorSegmentHough, AxialTrackHitMigrator, AxialTrackMerger, CDCMCCloneLookUpFiller, ClusterBackgroundDetector, ClusterCreator< AWireHitRelationFilter >, ClusterRefiner< AWireHitRelationFilter >, ClusterRefiner< BridgingWireHitRelationFilter >, ClusterRefiner< Belle2::TrackFindingCDC::BridgingWireHitRelationFilter >, FacetCreator, HitReclaimer, RLTaggedWireHitCreator, SegmentAliasResolver, SegmentCreatorFacetAutomaton, SegmentCreatorMCTruth, SegmentLinker, SegmentOrienter, SegmentPairCreator, SegmentRejecter, SegmentTripleCreator, SuperClusterCreator, TrackCombiner, TrackCreatorSegmentPairAutomaton, TrackCreatorSegmentTripleAutomaton, TrackCreatorSingleSegments, TrackExporter, TrackFlightTimeAdjuster, TrackInspector, TrackLinker, TrackNormalizer, TrackOrienter, TrackRejecter, TrackSZFitter, WeightedRelationCreator< AObject, ARelationFilter >, WeightedRelationCreator< const Belle2::TrackFindingCDC::WithAutomatonCell, Belle2::PhiRecoTrackRelationFilter >, WeightedRelationCreator< const Belle2::TrackFindingCDC::CDCFacet, Belle2::TrackFindingCDC::ChooseableFilter >, WeightedRelationCreator< const Belle2::TrackFindingCDC::CDCSegment2D, Belle2::TrackFindingCDC::ChooseableFilter >, WeightedRelationCreator< const Belle2::TrackFindingCDC::CDCSegmentPair, Belle2::TrackFindingCDC::ChooseableFilter >, WeightedRelationCreator< const Belle2::TrackFindingCDC::CDCSegmentTriple, Belle2::TrackFindingCDC::ChooseableFilter >, WeightedRelationCreator< const Belle2::TrackFindingCDC::CDCTrack, Belle2::TrackFindingCDC::ChooseableFilter >, WireHitBackgroundBlocker, WireHitBackgroundDetector, WireHitCreator, WireHitMCMultiLoopBlocker, StoreArrayLoader< IOType >, StoreArrayLoader< const Belle2::SpacePoint >, StoreArrayLoader< DataStoreInputTypeRefType >, StoreVectorSwapper< IOType, a_alwaysWrite >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCFacet >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCWireHit, true >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCSegment2D >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCTrack >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCSegmentPair >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCSegmentTriple >, TrackFinder, TrackFinderAutomaton, SegmentFitter, SegmentTrackAdderWithNormalization, TrackQualityAsserter, HitBasedT0Extractor, and FindletStoreArrayInput< TWrappedFindlet >.

Definition at line 60 of file Findlet.h.

      {
        return "(no description)";
      }

getNProcessingSignalListener()

int getNProcessingSignalListener ( )

protectedinherited

Get the number of currently registered listeners.

Definition at line 60 of file CompositeProcessingSignalListener.cc.

{
  return m_subordinaryProcessingSignalListeners.size();
}

initialize()

void initialize ( )

overridevirtualinherited

Receive and dispatch signal before the start of the event processing.

Reimplemented from ProcessingSignalListener.

Reimplemented in UnionVarSet< AObject >, UnionVarSet< Object >, VariadicUnionVarSet< AVarSets >, ResultStorer< Belle2::CKFToPXDResult >, ResultStorer< Belle2::CKFToSVDResult >, BaseEventTimeExtractor< RecoTrack * >, BaseEventTimeExtractor< TrackFindingCDC::CDCWireHit & >, StereoHitTrackQuadTreeMatcher< Belle2::TrackFindingCDC::HyperHough >, StereoHitTrackQuadTreeMatcher< Belle2::TrackFindingCDC::QuadraticLegendre >, StereoHitTrackQuadTreeMatcher< Belle2::TrackFindingCDC::Z0TanLambdaLegendre >, OnVarSet< Filter< ATruthVarSet::Object > >, OnVarSet< Filter< AVarSet::Object > >, OnVarSet< BaseFacetFilter >, OnVarSet< BaseFacetRelationFilter >, OnVarSet< BaseAxialSegmentPairFilter >, OnVarSet< BaseSegmentRelationFilter >, OnVarSet< BaseTrackRelationFilter >, OnVarSet< BaseSegmentPairRelationFilter >, MCSymmetric< BaseAxialSegmentPairFilter >, MCSymmetric< BaseFacetFilter >, MCSymmetric< BaseFacetRelationFilter >, MCSymmetric< BaseSegmentPairFilter >, MCSymmetric< BaseSegmentPairRelationFilter >, MCSymmetric< BaseSegmentRelationFilter >, MCSymmetric< BaseSegmentTripleFilter >, MCSymmetric< BaseSegmentTripleRelationFilter >, MCSymmetric< BaseTrackRelationFilter >, StoreArrayLoader< const Belle2::SpacePoint >, StoreArrayLoader< DataStoreInputTypeRefType >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCFacet >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCWireHit, true >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCSegment2D >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCTrack >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCSegmentPair >, StoreVectorSwapper< Belle2::TrackFindingCDC::CDCSegmentTriple >, RelationVarSet< ABaseVarSet >, QualityIndicatorFilter, TwoHitVirtualIPQIFilter, MultiHoughSpaceFastInterceptFinder, RawTrackCandCleaner< AHit >, RawTrackCandCleaner< Belle2::vxdHoughTracking::VXDHoughState >, RecoTrackStorer, ROIFinder, SingleHoughSpaceFastInterceptFinder, SpacePointLoaderAndPreparer, TrackCandidateOverlapResolver, and TrackCandidateResultRefiner.

Definition at line 15 of file CompositeProcessingSignalListener.cc.

{
  Super::initialize();
  for (ProcessingSignalListener* psl : m_subordinaryProcessingSignalListeners) {
    psl->initialize();
  }
}

terminate()

void terminate ( )

overridevirtualinherited

Receive and dispatch Signal for termination of the event processing.

Reimplemented from ProcessingSignalListener.

Reimplemented in StereoHitTrackQuadTreeMatcher< Belle2::TrackFindingCDC::HyperHough >, StereoHitTrackQuadTreeMatcher< Belle2::TrackFindingCDC::QuadraticLegendre >, and StereoHitTrackQuadTreeMatcher< Belle2::TrackFindingCDC::Z0TanLambdaLegendre >.

Definition at line 47 of file CompositeProcessingSignalListener.cc.

{
  for (ProcessingSignalListener* psl : reversedRange(m_subordinaryProcessingSignalListeners)) {
    psl->terminate();
  }
  Super::terminate();
}

traverseTree()

void traverseTree ( std::vector< const AState * > &  path, const std::vector< WeightedRelation< AState > > &  stateRelations, std::vector< AResult > &  results  )

private

Implementation of the traverseTree function.

Definition at line 111 of file WeightedTreeTraversal.h.

    {
      // Implement only graph traversal logic and leave the extrapolation and selection to the
      // rejecter.
      const AState* currentState = path.back();
      auto continuations =
        std::equal_range(stateRelations.begin(), stateRelations.end(), currentState);
 
      std::vector<WithWeight<AState*>> childStates;
      for (const WeightedRelation<AState>& continuation : asRange(continuations)) {
        AState* childState = continuation.getTo();
        Weight weight = continuation.getWeight();
        childStates.push_back({childState, weight});
      }
 
      // Do everything with child states, linking, extrapolation, teaching, discarding, what have
      // you.
      const std::vector<const AState*>& constPath = path;
      m_stateRejecter.apply(constPath, childStates);
 
      if (childStates.empty()) {
        B2DEBUG(25, "Terminating this route, as there are no possible child states.");
        results.emplace_back(path);
        return;
      }
 
      // Traverse the tree from each new state on
      B2DEBUG(25, "Having found " << childStates.size() << " child states.");
      for (WithWeight<AState*> childState : childStates) {
        if (std::count(path.begin(), path.end(), childState)) {
          // Cycle detected -- is this the best handling?
          // Other options: Raise and exception and bail out of this seed
          continue;
        }
        path.push_back(childState);
        traverseTree(path, stateRelations, results);
        path.pop_back();
      }
    }

Member Data Documentation

m_initialized

bool m_initialized = false

privateinherited

Flag to keep track whether initialization happened before.

Definition at line 52 of file ProcessingSignalListener.h.

m_initializedAs

std::string m_initializedAs

privateinherited

Name of the type during initialisation.

Definition at line 58 of file ProcessingSignalListener.h.

m_stateRejecter

AStateRejecter m_stateRejecter

private

State rejecter to decide which available continuations should be traversed next.

Definition at line 90 of file WeightedTreeTraversal.h.

m_subordinaryProcessingSignalListeners

std::vector<ProcessingSignalListener*> m_subordinaryProcessingSignalListeners

privateinherited

References to subordinary signal processing listener contained in this findlet.

Definition at line 52 of file CompositeProcessingSignalListener.h.

m_terminated

bool m_terminated = false

privateinherited

Flag to keep track whether termination happened before.

Definition at line 55 of file ProcessingSignalListener.h.

---

The documentation for this class was generated from the following file:

• tracking/trackFindingCDC/findlets/generic/include/WeightedTreeTraversal.h