Belle II Software  release-05-01-25
WeightedFastHoughTree< T, ADomain, ADomainDivsion > Class Template Reference

Dynamic tree structure with weighted items in each node which are markable through out the tree. More...

#include <WeightedFastHoughTree.h>

Inheritance diagram for WeightedFastHoughTree< T, ADomain, ADomainDivsion >:
Collaboration diagram for WeightedFastHoughTree< T, ADomain, ADomainDivsion >:

Public Types

using Node = typename Super::Node
 Type of the node in the tree.
 

Public Member Functions

template<class Ts >
void seed (const Ts &items)
 Take the item set and insert them into the top node of the hough space.
 
template<class AItemInDomainMeasure >
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 is below minWeight.
 
template<class AItemInDomainMeasure , class ASkipNodePredicate >
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 returns true.
 
template<class AItemInDomainMeasure >
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. More...
 
template<class AItemInDomainMeasure , class ASkipNodePredicate >
std::vector< std::pair< ADomain, std::vector< T > > > findHeaviestLeafRepeated (AItemInDomainMeasure &weightItemInDomain, int maxLevel, ASkipNodePredicate &skipNode)
 Go through all children until maxLevel is reached and find the heaviest leaves. More...
 
template<class AItemInDomainMeasure , class ASkipNodePredicate >
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. More...
 
template<class AItemInDomainMeasure , class ASkipNodePredicate >
NodefindHeaviestLeaf (AItemInDomainMeasure &weightItemInDomain, int maxLevel, ASkipNodePredicate &skipNode)
 Go through all children until the maxLevel is reached and find the leaf with the highest weight. More...
 
template<class AItemInDomainMeasure , class AIsLeafPredicate >
void fillWalk (AItemInDomainMeasure &weightItemInDomain, AIsLeafPredicate &isLeaf)
 Walk through the children and fill them if necessary until isLeaf returns true. More...
 
template<class ATreeWalker >
void walkHeighWeightFirst (ATreeWalker &walker)
 Walk the tree investigating the heaviest children with priority. More...
 
void fell ()
 Fell to tree meaning deleting all child nodes from the tree. Keeps the top node.
 
void raze ()
 Like fell but also releases all memory the tree has aquired during long executions.
 
NodegetTopNode ()
 Getter for the top node of the tree.
 
const NodegetTopNode () const
 Constant getter for the top node of the tree.
 
int getNNodes () const
 Gets the number of nodes currently contained in the tree Also demonstrates how to walk over the tree.
 
std::map< int, int > getNNodesByLevel () const
 Gets the number of nodes by level in the tree Also demonstrates how to walk over the tree.
 
void walk (AWalker &walker)
 Forward walk to the top node.
 
void walk (AWalker &walker, APriorityMeasure &priority)
 Forward walk to the top node.
 

Public Attributes

SubPropertiesFactory m_subPropertiesFactory
 Instance of the properties factory for the sub nodes.
 
Node m_topNode
 Memory for the top node of the tree.
 
std::deque< typename Node::Children > m_children
 Central point to provide memory for the child structures.
 
size_t m_nUsedChildren
 Last index of used children.
 

Private Types

using Super = WeightedParititioningDynTree< WithSharedMark< T >, ADomain, ADomainDivsion >
 Type of the Tree the partitions using markable items the hough space.
 
using This = DynTree< WithWeightedItems< ADomain, WithSharedMark< T > >, ADomainDivsion >
 Type of this class.
 
using Properties = WithWeightedItems< ADomain, WithSharedMark< T > >
 Type of the Properties.
 
using SubPropertiesFactory = ADomainDivsion
 Type of the factory for the sub node properties.
 

Private Member Functions

std::vector< Node > * createChildren (Node *parentNode)
 Create child nodes for the given parents.
 
std::vector< Node > * getUnusedChildren ()
 Aquire the next unused child node structure, recycling all memory.
 

Private Attributes

std::deque< bool > m_marks
 Memory of the used marks of the items.
 

Detailed Description

template<class T, class ADomain, class ADomainDivsion>
class Belle2::TrackFindingCDC::WeightedFastHoughTree< T, ADomain, ADomainDivsion >

Dynamic tree structure with weighted items in each node which are markable through out the tree.

Used to build fast hough type algorithms, where objects are allowed to carry weights relative to the hough space part (here called a ADomain) they are contained in. The shared marks allow for interrative extraction of hough peaks such that other areas of the hough space notice that certain element have already been consumed.

Definition at line 59 of file WeightedFastHoughTree.h.

Member Function Documentation

◆ fillWalk()

void fillWalk ( AItemInDomainMeasure &  weightItemInDomain,
AIsLeafPredicate &  isLeaf 
)
inline

Walk through the children and fill them if necessary until isLeaf returns true.

Uses the weightItemInDomain to create weights for the items (or decide if an item belongs to a mode or not).

Definition at line 249 of file WeightedFastHoughTree.h.

256  {
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 {

◆ findHeaviestLeaf()

Node* findHeaviestLeaf ( AItemInDomainMeasure &  weightItemInDomain,
int  maxLevel,
ASkipNodePredicate &  skipNode 
)
inline

Go through all children until the maxLevel is reached and find the leaf with the highest weight.

If no node could be found, return a nullptr. A node is skipped if skipNode is returns true for this node.

Definition at line 211 of file WeightedFastHoughTree.h.

◆ findHeaviestLeafRepeated() [1/2]

std::vector<std::pair<ADomain, std::vector<T> > > findHeaviestLeafRepeated ( AItemInDomainMeasure &  weightItemInDomain,
int  maxLevel,
ASkipNodePredicate &  skipNode 
)
inline

Go through all children until maxLevel is reached and find the heaviest leaves.

For this, the single heaviest leaf is found and added to an internal list. The process is repeated until no leaf can be found anymore. A node is skipped if skipNode is returns true for this node.

Definition at line 164 of file WeightedFastHoughTree.h.

◆ findHeaviestLeafRepeated() [2/2]

std::vector<std::pair<ADomain, std::vector<T> > > findHeaviestLeafRepeated ( AItemInDomainMeasure &  weightItemInDomain,
int  maxLevel,
const Weight  minWeight = NAN 
)
inline

Go through all children until maxLevel is reached and find the heaviest leaves.

For this, the single heaviest leaf is found and added to an internal list. The process is repeated until no leaf can be found anymore. A node is skipped if the weight is below minWeight.

Definition at line 145 of file WeightedFastHoughTree.h.

◆ findHeaviestLeafSingle()

std::unique_ptr<std::pair<ADomain, std::vector<T> > > findHeaviestLeafSingle ( AItemInDomainMeasure &  weightItemInDomain,
int  maxLevel,
ASkipNodePredicate &  skipNode 
)
inline

Go through all children until the maxLevel is reached and find the leaf with the highest weight.

If no node could be found, return an empty list, otherwise return a list with just on element. A node is skipped if skipNode is returns true for this node.

Definition at line 188 of file WeightedFastHoughTree.h.

◆ walkHeighWeightFirst()

void walkHeighWeightFirst ( ATreeWalker &  walker)
inline

Walk the tree investigating the heaviest children with priority.

Clear items that have been marked as used before evaluating the weight.

Definition at line 287 of file WeightedFastHoughTree.h.


The documentation for this class was generated from the following file:
Belle2::TrackFindingCDC::WeightedFastHoughTree::walkHeighWeightFirst
void walkHeighWeightFirst(ATreeWalker &walker)
Walk the tree investigating the heaviest children with priority.
Definition: WeightedFastHoughTree.h:287
Belle2::TrackFindingCDC::WeightedFastHoughTree::Node
typename Super::Node Node
Type of the node in the tree.
Definition: WeightedFastHoughTree.h:71