Belle II Software  release-05-02-19
CellularPathFollower.h
1 /**************************************************************************
2  * BASF2 (Belle Analysis Framework 2) *
3  * Copyright(C) 2012 - Belle II Collaboration *
4  * *
5  * Author: The Belle II Collaboration *
6  * Contributors: Oliver Frost *
7  * *
8  * This software is provided "as is" without any warranty. *
9  **************************************************************************/
10 #pragma once
11 
12 #include <tracking/trackFindingCDC/ca/Path.h>
13 #include <tracking/trackFindingCDC/ca/AutomatonCell.h>
14 
15 #include <tracking/trackFindingCDC/utilities/WeightedRelation.h>
16 
17 #include <cassert>
18 #include <cmath>
19 #include <vector>
20 
21 namespace Belle2 {
27  namespace TrackFindingCDC {
28 
39  template<class ACellHolder>
40  class CellularPathFollower {
41 
42  public:
44  std::vector<Path<ACellHolder>> followAll(
45  const std::vector<ACellHolder*>& cellHolders,
46  const std::vector<WeightedRelation<ACellHolder>>& cellHolderRelations,
47  Weight minStateToFollow = -INFINITY) const
48  {
49  B2ASSERT("Expected the relations to be sorted",
50  std::is_sorted(cellHolderRelations.begin(), cellHolderRelations.end()));
51 
52  // Result
53  std::vector<Path<ACellHolder> > paths;
54 
55  // Stack for back tracking
56  Path<ACellHolder> path;
57 
58  for (ACellHolder* cellHolder : cellHolders) {
59  const AutomatonCell& automatonCell = cellHolder->getAutomatonCell();
60 
61  if (validStartCell(automatonCell, minStateToFollow)) {
62  // Cell marks a start point of a path
63 
64  // Start new path
65  path.clear();
66 
67  // Insert a pointer to the cell into the path
68  path.push_back(cellHolder);
69 
70  // Recursivly grow the path
71  growAllPaths(path, cellHolderRelations, paths);
72  path.pop_back();
73  }
74  }
75  return paths;
76  }
77 
83  Path<ACellHolder> followSingle(ACellHolder* startCellHolder,
84  const std::vector<WeightedRelation<ACellHolder>>& cellHolderRelations,
85  Weight minStateToFollow = -INFINITY) const
86  {
87  assert(std::is_sorted(cellHolderRelations.begin(), cellHolderRelations.end()));
88 
89  Path<ACellHolder> path;
90  if (not startCellHolder) return path;
91  const AutomatonCell& startCell = startCellHolder->getAutomatonCell();
92  if (not validStartCell(startCell, minStateToFollow)) return path;
93 
94  // Start new path
95  path.reserve(20); // Just a guess
96 
97  // Insert a pointer to the cell into the path
98  path.push_back(startCellHolder);
99  bool grew = true;
100  while (grew) {
101  grew = false;
102  ACellHolder* cellHolder = path.back();
103 
104  auto continuations = asRange(std::equal_range(cellHolderRelations.begin(),
105  cellHolderRelations.end(),
106  cellHolder));
107 
108  for (const WeightedRelation<ACellHolder>& relation : continuations) {
109  // cppcheck-suppress useStlAlgorithm
110  if (isHighestContinuation(relation)) {
111  ACellHolder* neighbor = relation.getTo();
112  path.push_back(neighbor);
113  grew = true;
114  break;
115  }
116  }
117  }
118  return path;
119  }
120 
121  private:
128  void growAllPaths(Path<ACellHolder>& path,
129  const std::vector<WeightedRelation<ACellHolder>>& cellHolderRelations,
130  std::vector<Path<ACellHolder> >& paths) const
131  {
132  auto growPathByRelation = [&](const WeightedRelation<ACellHolder>& neighborRelation) {
133  if (not this->isHighestContinuation(neighborRelation)) return false;
134  ACellHolder* neighbor(neighborRelation.getTo());
135  path.push_back(neighbor);
136  this->growAllPaths(path, cellHolderRelations, paths);
137  path.pop_back();
138  return true;
139  };
140 
141  ACellHolder* lastCellHolder = path.back();
142 
143  auto continuations = asRange(std::equal_range(cellHolderRelations.begin(),
144  cellHolderRelations.end(),
145  lastCellHolder));
146  int nRelationsUsed = std::count_if(continuations.begin(),
147  continuations.end(),
148  growPathByRelation);
149 
150  if (nRelationsUsed == 0) {
151  // end point of the recursion copy maximal path to the vector.
152  paths.push_back(path);
153  }
154  }
155 
160  static bool validStartCell(const AutomatonCell& automatonCell,
161  Weight minStateToFollow)
162  {
163  return
164  automatonCell.hasStartFlag() and
165  not automatonCell.hasMaskedFlag() and
166  not automatonCell.hasCycleFlag() and
167  minStateToFollow <= automatonCell.getCellState();
168  }
169 
174  static bool isHighestContinuation(const WeightedRelation<ACellHolder>& relation)
175  {
176  ACellHolder* cellHolderPtr(relation.getFrom());
177  ACellHolder* neighborCellHolderPtr(relation.getTo());
178 
179  if (not cellHolderPtr or not neighborCellHolderPtr) return false;
180 
181  ACellHolder& cellHolder = *cellHolderPtr;
182  Weight relationWeight = relation.getWeight();
183  ACellHolder& neighborCellHolder = *neighborCellHolderPtr;
184 
185  return isHighestContinuation(cellHolder, relationWeight, neighborCellHolder);
186  }
187 
192  static bool isHighestContinuation(ACellHolder& cellHolder,
193  Weight relationWeight,
194  ACellHolder& neighborCellHolder)
195  {
196  const AutomatonCell& automatonCell = cellHolder.getAutomatonCell();
197  const AutomatonCell& neighborAutomatonCell = neighborCellHolder.getAutomatonCell();
198 
199  return not neighborAutomatonCell.hasCycleFlag() and not neighborAutomatonCell.hasMaskedFlag() and
200  (automatonCell.getCellState() ==
201  (neighborAutomatonCell.getCellState() + relationWeight + automatonCell.getCellWeight()));
202  }
203  };
204  }
206 }
Belle2::TrackFindingCDC::AutomatonCell::hasMaskedFlag
bool hasMaskedFlag() const
Gets the current state of the masked marker flag.
Definition: AutomatonCell.h:228
Belle2::TrackFindingCDC::WeightedRelation::getFrom
From * getFrom() const
Getter for the pointer to the from side object.
Definition: WeightedRelation.h:101
Belle2::TrackFindingCDC::CellularPathFollower::growAllPaths
void growAllPaths(Path< ACellHolder > &path, const std::vector< WeightedRelation< ACellHolder >> &cellHolderRelations, std::vector< Path< ACellHolder > > &paths) const
Helper function for recursively growing paths.
Definition: CellularPathFollower.h:136
Belle2::TrackFindingCDC::AutomatonCell::getCellWeight
Weight getCellWeight() const
Getter for the cell weight.
Definition: AutomatonCell.h:126
Belle2::TrackFindingCDC::WeightedRelation::getWeight
Weight getWeight() const
Getter for the weight.
Definition: WeightedRelation.h:107
Belle2
Abstract base class for different kinds of events.
Definition: MillepedeAlgorithm.h:19
Belle2::TrackFindingCDC::AutomatonCell
Cell used by the cellular automata.
Definition: AutomatonCell.h:39
Belle2::TrackFindingCDC::AutomatonCell::hasCycleFlag
bool hasCycleFlag() const
Gets the current state of the cycle marker flag.
Definition: AutomatonCell.h:204
Belle2::TrackFindingCDC::CellularPathFollower::followAll
std::vector< Path< ACellHolder > > followAll(const std::vector< ACellHolder * > &cellHolders, const std::vector< WeightedRelation< ACellHolder >> &cellHolderRelations, Weight minStateToFollow=-INFINITY) const
Follow paths from all start cells marked with the start flag.
Definition: CellularPathFollower.h:52
Belle2::TrackFindingCDC::WeightedRelation
Type for two related objects with a weight.
Definition: CDCSegment2D.h:36
Belle2::TrackFindingCDC::WeightedRelation::getTo
To * getTo() const
Getter for the pointer to the to side object.
Definition: WeightedRelation.h:125
Belle2::Path
Implements a path consisting of Module and/or Path objects.
Definition: Path.h:40
Belle2::TrackFindingCDC::CellularPathFollower::followSingle
Path< ACellHolder > followSingle(ACellHolder *startCellHolder, const std::vector< WeightedRelation< ACellHolder >> &cellHolderRelations, Weight minStateToFollow=-INFINITY) const
Follows a single maximal path starting with the given start cell.
Definition: CellularPathFollower.h:91
Belle2::TrackFindingCDC::CellularPathFollower::validStartCell
static bool validStartCell(const AutomatonCell &automatonCell, Weight minStateToFollow)
Helper function to determine, if the cell has all flags indicating to be a start cell and that its st...
Definition: CellularPathFollower.h:168
Belle2::TrackFindingCDC::CellularPathFollower::isHighestContinuation
static bool isHighestContinuation(const WeightedRelation< ACellHolder > &relation)
Helper function determining if the given neighbor is one of the best to be followed.
Definition: CellularPathFollower.h:182
Belle2::TrackFindingCDC::AutomatonCell::getCellState
Weight getCellState() const
Getter for the cell state.
Definition: AutomatonCell.h:106