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 >
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. 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.
Node &	getTopNode ()
	Getter for the top node of the tree.
const Node &	getTopNode () 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.
template<class AWalker >
void	walk (AWalker &walker)
	Forward walk to the top node.
template<class AWalker , class APriorityMeasure >
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 = 0
	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< AProperties, ASubPropertiesFactory >
	Type of this class.
using	Properties = AProperties
	Type of the Properties.
using	SubPropertiesFactory = ASubPropertiesFactory
	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 49 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 239 of file WeightedFastHoughTree.h.

      {
        auto walker = [&weightItemInDomain, &isLeaf](Node * node) {
          // Check if node is a leaf
          // Do not create children in this case
          if (isLeaf(node)) {
            // Do not walk children.
            return false;
          }
 
          // Node is not a leaf.
          // Check if it has childen.
          // If children have not been created, create and fill them.
          typename Node::Children* children = node->getChildren();
          if (not children) {
            node->createChildren();
            children = node->getChildren();
            for (Node& childNode : *children) {
              assert(childNode.getChildren() == nullptr);
              assert(childNode.size() == 0);
              auto measure =
              [&childNode, &weightItemInDomain](WithSharedMark<T>& markableItem) -> Weight {
                // Weighting function should not see the mark, but only the item itself.
                T & item(markableItem);
                return weightItemInDomain(item, &childNode);
              };
              childNode.insert(*node, measure);
            }
          }
          // Continue to walk the children.
          return true;
        };
        walkHeighWeightFirst(walker);
      }

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 201 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 154 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 135 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 178 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 277 of file WeightedFastHoughTree.h.

---

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

• tracking/trackFindingCDC/hough/trees/include/WeightedFastHoughTree.h