Belle II Software  release-05-02-19
WeightedFastHoughTree.h
1 /**************************************************************************
2 * BASF2 (Belle Analysis Framework 2) *
3 * Copyright(C) 2015 - 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/hough/trees/DynTree.h>
13 #include <tracking/trackFindingCDC/hough/baseelements/WithWeightedItems.h>
14 #include <tracking/trackFindingCDC/hough/baseelements/WithSharedMark.h>
15 
16 #include <vector>
17 #include <memory>
18 #include <cassert>
19 #include <cfloat>
20 #include <cmath>
21 
22 namespace Belle2 {
27  namespace TrackFindingCDC {
28 
30  template<class T, class ADomain, class ADomainDivsion>
31  class WeightedParititioningDynTree :
32  public DynTree< WithWeightedItems<ADomain, T>, ADomainDivsion> {
33  private:
35  using Super = DynTree< WithWeightedItems<ADomain, T>, ADomainDivsion>;
36 
37  public:
39  WeightedParititioningDynTree(ADomain topDomain, ADomainDivsion domainDivsion) :
40  Super(WithWeightedItems<ADomain, T>(std::move(topDomain)), std::move(domainDivsion))
41  {}
42  };
43 
50  template<class T, class ADomain, class ADomainDivsion>
51  class WeightedFastHoughTree :
52  public WeightedParititioningDynTree<WithSharedMark<T>, ADomain, ADomainDivsion> {
53 
54  private:
56  using Super = WeightedParititioningDynTree<WithSharedMark<T>, ADomain, ADomainDivsion>;
57 
58  public:
61 
63  using Node = typename Super::Node;
64 
65  public:
67  template<class Ts>
68  void seed(const Ts& items)
69  {
70  this->fell();
71  Node& topNode = this->getTopNode();
72  for (auto && item : items) {
73  m_marks.push_back(false);
74  bool& markOfItem = m_marks.back();
75  Weight weight = DBL_MAX;
76  topNode.insert(WithSharedMark<T>(T(item), &markOfItem), weight);
77  }
78  }
79 
81  template <class AItemInDomainMeasure>
82  std::vector<std::pair<ADomain, std::vector<T>>>
83  findHeavyLeavesDisjoint(AItemInDomainMeasure& weightItemInDomain,
84  int maxLevel,
85  double minWeight)
86  {
87  auto skipLowWeightNode = [minWeight](const Node * node) {
88  return not(node->getWeight() >= minWeight);
89  };
90  return findLeavesDisjoint(weightItemInDomain, maxLevel, skipLowWeightNode);
91  }
92 
94  template <class AItemInDomainMeasure, class ASkipNodePredicate>
95  std::vector<std::pair<ADomain, std::vector<T>>>
96  findLeavesDisjoint(AItemInDomainMeasure& weightItemInDomain,
97  int maxLevel,
98  ASkipNodePredicate& skipNode)
99  {
100  std::vector<std::pair<ADomain, std::vector<T> > > found;
101  auto isLeaf = [&found, &skipNode, maxLevel](Node * node) {
102  // Skip the expansion and the filling of the children
103  if (skipNode(node)) {
104  return true;
105  }
106 
107  // Node is a leaf at the maximum level
108  // Save its content
109  // Do not walk children
110  if (node->getLevel() >= maxLevel) {
111  const ADomain* domain = node;
112  found.emplace_back(*domain, std::vector<T>(node->begin(), node->end()));
113  for (WithSharedMark<T>& markableItem : *node) {
114  markableItem.mark();
115  }
116  return true;
117  }
118 
119  // Else to node has enough weight and is not at the lowest level
120  // Signal that it is not a leaf
121  // Continue to create and fill children.
122  return false;
123  };
124  fillWalk(weightItemInDomain, isLeaf);
125  return found;
126  }
127 
135  template <class AItemInDomainMeasure>
136  std::vector<std::pair<ADomain, std::vector<T>>>
137  findHeaviestLeafRepeated(AItemInDomainMeasure& weightItemInDomain,
138  int maxLevel,
139  const Weight minWeight = NAN)
140  {
141  auto skipLowWeightNode = [minWeight](const Node * node) {
142  return not(node->getWeight() >= minWeight);
143  };
144  return findHeaviestLeafRepeated(weightItemInDomain, maxLevel, skipLowWeightNode);
145  }
146 
154  template <class AItemInDomainMeasure, class ASkipNodePredicate>
155  std::vector<std::pair<ADomain, std::vector<T>>>
156  findHeaviestLeafRepeated(AItemInDomainMeasure& weightItemInDomain,
157  int maxLevel,
158  ASkipNodePredicate& skipNode)
159  {
160  std::vector<std::pair<ADomain, std::vector<T> > > found;
161  Node* node = findHeaviestLeaf(weightItemInDomain, maxLevel, skipNode);
162  while (node) {
163  const ADomain* domain = node;
164  found.emplace_back(*domain, std::vector<T>(node->begin(), node->end()));
165  for (WithSharedMark<T>& markableItem : *node) {
166  markableItem.mark();
167  }
168  node = findHeaviestLeaf(weightItemInDomain, maxLevel, skipNode);
169  }
170  return found;
171  }
172 
178  template <class AItemInDomainMeasure, class ASkipNodePredicate>
179  std::unique_ptr<std::pair<ADomain, std::vector<T>>>
180  findHeaviestLeafSingle(AItemInDomainMeasure& weightItemInDomain,
181  int maxLevel,
182  ASkipNodePredicate& skipNode)
183  {
184  using Result = std::pair<ADomain, std::vector<T> >;
185  std::unique_ptr<Result> found = nullptr;
186  Node* node = findHeaviestLeaf(weightItemInDomain, maxLevel, skipNode);
187  if (node) {
188  const ADomain* domain = node;
189  found.reset(new Result(*domain, std::vector<T>(node->begin(), node->end())));
190  for (WithSharedMark<T>& markableItem : *node) {
191  markableItem.mark();
192  }
193  }
194  return found;
195  }
196 
202  template <class AItemInDomainMeasure, class ASkipNodePredicate>
203  Node* findHeaviestLeaf(AItemInDomainMeasure& weightItemInDomain,
204  int maxLevel,
205  ASkipNodePredicate& skipNode)
206  {
207  Node* heaviestNode = nullptr;
208  Weight heighestWeigth = NAN;
209  auto isLeaf = [&heaviestNode, &heighestWeigth, maxLevel, &skipNode](Node * node) {
210  // Skip the expansion and the filling of the children
211  if (skipNode(node)) {
212  return true;
213  }
214 
215  Weight nodeWeight = node->getWeight();
216  // Skip the expansion and filling of the children if the node has not enough weight
217  if (not std::isnan(heighestWeigth) and not(nodeWeight > heighestWeigth)) {
218  return true;
219  }
220 
221  // Node is a leaf at the maximum level and is heavier than everything seen before.
222  // Save its content
223  // Do not walk children
224  if (node->getLevel() >= maxLevel) {
225  heaviestNode = node;
226  heighestWeigth = nodeWeight;
227  return true;
228  }
229  return false;
230  };
231  fillWalk(weightItemInDomain, isLeaf);
232  return heaviestNode;
233  }
234 
235  public:
240  template<class AItemInDomainMeasure, class AIsLeafPredicate>
241  void fillWalk(AItemInDomainMeasure& weightItemInDomain,
242  AIsLeafPredicate& isLeaf)
243  {
244  auto walker = [&weightItemInDomain, &isLeaf](Node * node) {
245  // Check if node is a leaf
246  // Do not create children in this case
247  if (isLeaf(node)) {
248  // Do not walk children.
249  return false;
250  }
251 
252  // Node is not a leaf.
253  // Check if it has childen.
254  // If children have not been created, create and fill them.
255  typename Node::Children* children = node->getChildren();
256  if (not children) {
257  node->createChildren();
258  children = node->getChildren();
259  for (Node& childNode : *children) {
260  assert(childNode.getChildren() == nullptr);
261  assert(childNode.size() == 0);
262  auto measure =
263  [&childNode, &weightItemInDomain](WithSharedMark<T>& markableItem) -> Weight {
264  // Weighting function should not see the mark, but only the item itself.
265  T & item(markableItem);
266  return weightItemInDomain(item, &childNode);
267  };
268  childNode.insert(*node, measure);
269  }
270  }
271  // Continue to walk the children.
272  return true;
273  };
274  walkHeighWeightFirst(walker);
275  }
276 
278  template<class ATreeWalker>
279  void walkHeighWeightFirst(ATreeWalker& walker)
280  {
281  auto priority = [](Node * node) -> float {
283  auto isMarked = [](const WithSharedMark<T>& markableItem) -> bool {
284  return markableItem.isMarked();
285  };
286  node->eraseIf(isMarked);
287  return node->getWeight();
288  };
289 
290  this->walk(walker, priority);
291  }
292 
294  void fell()
295  {
296  this->getTopNode().clear();
297  m_marks.clear();
298  Super::fell();
299  }
300 
302  void raze()
303  {
304  this->fell();
305  Super::raze();
306  m_marks.shrink_to_fit();
307  }
308 
309  private:
311  std::deque<bool> m_marks;
312  // Note: Have to use a deque here because std::vector<bool> is special
313  // std::vector<bool> m_marks;
314  };
315  }
317 }
Belle2::TrackFindingCDC::WeightedFastHoughTree::findHeaviestLeafSingle
std::unique_ptr< std::pair< ADomain, std::vector< T > > > findHeaviestLeafSingle(AItemInDomainMeasure &weightItemInDomain, int maxLevel, ASkipNodePredicate &skipNode)
Go through all children until the maxLevel is reached and find the leaf with the highest weight.
Definition: WeightedFastHoughTree.h:188
Belle2::TrackFindingCDC::WeightedFastHoughTree::findHeavyLeavesDisjoint
std::vector< std::pair< ADomain, std::vector< T > > > findHeavyLeavesDisjoint(AItemInDomainMeasure &weightItemInDomain, int maxLevel, double minWeight)
Find all children node at maximum level and add them to the result list. Skip nodes if their weight i...
Definition: WeightedFastHoughTree.h:91
Belle2::TrackFindingCDC::DynTree< WithWeightedItems< ADomain, WithSharedMark< T > >, ADomainDivsion >::raze
void raze()
Like fell but also releases all memory the tree has aquired during long execution.
Definition: DynTree.h:358
Belle2::TrackFindingCDC::DynTree< WithWeightedItems< ADomain, WithSharedMark< T > >, ADomainDivsion >::walk
void walk(AWalker &walker)
Forward walk to the top node.
Definition: DynTree.h:325
Belle2::TrackFindingCDC::WeightedFastHoughTree::fillWalk
void fillWalk(AItemInDomainMeasure &weightItemInDomain, AIsLeafPredicate &isLeaf)
Walk through the children and fill them if necessary until isLeaf returns true.
Definition: WeightedFastHoughTree.h:249
Belle2::TrackFindingCDC::DynTree< WithWeightedItems< ADomain, WithSharedMark< T > >, ADomainDivsion >::fell
void fell()
Fell to tree meaning deleting all child nodes from the tree. Keeps the top node.
Definition: DynTree.h:343
Belle2::TrackFindingCDC::WeightedFastHoughTree::fell
void fell()
Fell to tree meaning deleting all child nodes from the tree. Keeps the top node.
Definition: WeightedFastHoughTree.h:302
Belle2::TrackFindingCDC::WeightedFastHoughTree::m_marks
std::deque< bool > m_marks
Memory of the used marks of the items.
Definition: WeightedFastHoughTree.h:319
Belle2::TrackFindingCDC::WeightedFastHoughTree::raze
void raze()
Like fell but also releases all memory the tree has aquired during long executions.
Definition: WeightedFastHoughTree.h:310
Belle2::TrackFindingCDC::WeightedFastHoughTree::findHeaviestLeafRepeated
std::vector< std::pair< ADomain, std::vector< T > > > findHeaviestLeafRepeated(AItemInDomainMeasure &weightItemInDomain, int maxLevel, const Weight minWeight=NAN)
Go through all children until maxLevel is reached and find the heaviest leaves.
Definition: WeightedFastHoughTree.h:145
Belle2::TrackFindingCDC::DynTree< WithWeightedItems< ADomain, WithSharedMark< T > >, ADomainDivsion >::getTopNode
Node & getTopNode()
Getter for the top node of the tree.
Definition: DynTree.h:247
Belle2::TrackFindingCDC::WeightedParititioningDynTree
Type of tree for paritioning the hough space.
Definition: WeightedFastHoughTree.h:39
Belle2
Abstract base class for different kinds of events.
Definition: MillepedeAlgorithm.h:19
Belle2::TrackFindingCDC::WeightedFastHoughTree::seed
void seed(const Ts &items)
Take the item set and insert them into the top node of the hough space.
Definition: WeightedFastHoughTree.h:76
Belle2::TrackFindingCDC::WithSharedMark
Mixin class to attach a mark that is shared among many instances.
Definition: WithSharedMark.h:31
Belle2::TrackFindingCDC::DynTree< WithWeightedItems< ADomain, T >, ADomainDivsion >
Belle2::TrackFindingCDC::WeightedParititioningDynTree::WeightedParititioningDynTree
WeightedParititioningDynTree(ADomain topDomain, ADomainDivsion domainDivsion)
Constructor attaching a vector of the weigthed items to the top most node domain.
Definition: WeightedFastHoughTree.h:47
Belle2::TrackFindingCDC::WeightedParititioningDynTree::Super
DynTree< WithWeightedItems< ADomain, T >, ADomainDivsion > Super
Type of the base class.
Definition: WeightedFastHoughTree.h:43
Belle2::TrackFindingCDC::WeightedFastHoughTree
Dynamic tree structure with weighted items in each node which are markable through out the tree.
Definition: WeightedFastHoughTree.h:59
Belle2::TrackFindingCDC::WeightedFastHoughTree::findLeavesDisjoint
std::vector< std::pair< ADomain, std::vector< T > > > findLeavesDisjoint(AItemInDomainMeasure &weightItemInDomain, int maxLevel, ASkipNodePredicate &skipNode)
Find all children node at maximum level and add them to the result list. Skip nodes if skipNode retur...
Definition: WeightedFastHoughTree.h:104
Belle2::TrackFindingCDC::WithWeightedItems
A mixin class to attach a set of weighted items to a class.
Definition: WithWeightedItems.h:35
Belle2::TrackFindingCDC::WeightedFastHoughTree::walkHeighWeightFirst
void walkHeighWeightFirst(ATreeWalker &walker)
Walk the tree investigating the heaviest children with priority.
Definition: WeightedFastHoughTree.h:287
Belle2::TrackFindingCDC::WeightedFastHoughTree::findHeaviestLeaf
Node * findHeaviestLeaf(AItemInDomainMeasure &weightItemInDomain, int maxLevel, ASkipNodePredicate &skipNode)
Go through all children until the maxLevel is reached and find the leaf with the highest weight.
Definition: WeightedFastHoughTree.h:211
Belle2::TrackFindingCDC::WeightedFastHoughTree::Node
typename Super::Node Node
Type of the node in the tree.
Definition: WeightedFastHoughTree.h:71