Belle II Software development
Public Types | Public Member Functions | Static Public Member Functions | Public Attributes | Protected Member Functions | Protected Attributes | List of all members
PathCollectorRecursive< ContainerType, NodeType, NeighbourContainerType, NodeCompatibilityCheckerType > Class Template Reference
Packages » tracking

Path finder for generic ContainerType. More...

#include <PathCollectorRecursive.h>

Public Types

using Path = std::vector<NodeType*>
 Using Path for vector of pointers to NodeTypes.
 

Public Member Functions

bool findPaths (ContainerType &aNetwork, std::vector< Path > &paths, unsigned int pathLimit, bool storeSubsets=false)
 Main functionality of this class Evaluates provided network and creates all allowed paths.
 

Static Public Member Functions

static std::string printPaths (const std::vector< Path > &allPaths)
 Prints information about all paths provided in a vector of paths.
 

Public Attributes

unsigned int minPathLength = 2
 public Data members:
 
unsigned int nTrees = 0
 Counter for number of trees found.
 
unsigned int nRecursiveCalls = 0
 Counter for number of recursive calls.
 
bool m_storeSubsets = false
 flag if subsets should be stored or not
 

Protected Member Functions

Path clone (const Path &aPath) const
 Copies path to create an identical one.
 
void storeAcceptedPath (Path newPath, std::vector< Path > &allNodePaths) const
 Tests length requirement on a path before adding it to path vector.
 
void findPathsRecursive (std::vector< Path > &allNodePaths, Path &currentPath, NeighbourContainerType &innerNeighbours)
 Recursive pathFinder: Collects all possible segment combinations to build paths.
 

Protected Attributes

NodeCompatibilityCheckerType m_compatibilityChecker
 protected Data members:
 

Detailed Description

template<class ContainerType, class NodeType, class NeighbourContainerType, class NodeCompatibilityCheckerType>
class Belle2::PathCollectorRecursive< ContainerType, NodeType, NeighbourContainerType, NodeCompatibilityCheckerType >

Path finder for generic ContainerType.

Uses recursive collection process and returns vector of paths, which are vectors of NodeType*.

Requirements for ContainerType:

  • must have begin() and end() with iterator pointing to pointers of entries ( = ContainerType< NodeType*>)

Requirements for NodeType:

  • must have function: bool NodeType::getMetaInfo().isSeed()
  • must have function: NeighbourContainerType& NodeType::getInnerNodes()
  • must have function: bool NodeType::getOuterNodes().empty()
  • other requirements depend on NodeCompatibilityCheckerType used.

Requirements for NeighbourContainerType:

  • must have function: bool NeighbourContainerType::empty()
  • must have function: unsigned int (or comparable) NeighbourContainerType::size()
  • must have access operator: NeighbourContainerType: operator [] returning a NodeType*

Requirements for NodeCompatibilityCheckerType:

  • must have function bool areCompatible(NodeType* outerNode, NodeType* innerNode);

Definition at line 44 of file PathCollectorRecursive.h.

Member Typedef Documentation

◆ Path

template<class ContainerType, class NodeType, class NeighbourContainerType, class NodeCompatibilityCheckerType>
using Path = std::vector<NodeType*>

Using Path for vector of pointers to NodeTypes.

Definition at line 47 of file PathCollectorRecursive.h.

Member Function Documentation

◆ clone()

template<class ContainerType, class NodeType, class NeighbourContainerType, class NodeCompatibilityCheckerType>
Path clone ( const Path & aPath) const
inlineprotected

Copies path to create an identical one.

Definition at line 117 of file PathCollectorRecursive.h.

118 {
119 Path newPath = Path();
120 for (auto* entry : aPath) {
121 newPath.push_back(entry);
122 }
123 return newPath;
124 }

◆ findPaths()

template<class ContainerType, class NodeType, class NeighbourContainerType, class NodeCompatibilityCheckerType>
bool findPaths ( ContainerType & aNetwork,
std::vector< Path > & paths,
unsigned int pathLimit,
bool storeSubsets = false )
inline

Main functionality of this class Evaluates provided network and creates all allowed paths.

All found paths are filled into the provided vector 'paths'. If storeSubsets is turned on, also the sub-paths are saved to vector 'paths'. If a defined limit on the number of possible paths is exceeded, the search is aborted, and false is returned.

Definition at line 57 of file PathCollectorRecursive.h.

58 {
59 m_storeSubsets = storeSubsets;
60
61 std::vector<Path> allNodePaths;
62 for (NodeType* aNode : aNetwork) {
63 if (aNode->getMetaInfo().isSeed() == false) {
64 continue;
65 }
66
67 NeighbourContainerType& innerNeighbours = aNode->getInnerNodes();
68 if (innerNeighbours.empty()) {
69 continue;
70 }
71 if (aNode->getOuterNodes().empty()) {
72 nTrees++;
73 }
74
75 // creating unique_ptr of a new path:
76 Path newPath = Path{aNode};
77
78 findPathsRecursive(allNodePaths, newPath, innerNeighbours);
79 storeAcceptedPath(newPath, allNodePaths);
80
81 if (allNodePaths.size() > pathLimit) {
82 B2WARNING("Number of collected paths is too large: skipping the event and not processing it."
83 << LogVar("Number of node paths", allNodePaths.size()) << LogVar("Current limit of paths", pathLimit));
84 return false;
85 }
86 }
87 paths = allNodePaths;
88 return true;
89 }

◆ findPathsRecursive()

template<class ContainerType, class NodeType, class NeighbourContainerType, class NodeCompatibilityCheckerType>
void findPathsRecursive ( std::vector< Path > & allNodePaths,
Path & currentPath,
NeighbourContainerType & innerNeighbours )
inlineprotected

Recursive pathFinder: Collects all possible segment combinations to build paths.

Definition at line 137 of file PathCollectorRecursive.h.

138 {
139 nRecursiveCalls++;
140
141 if (currentPath.size() > 30) {
142 B2WARNING("findPathsRecursive reached a path length of over 30. Stopping Path here!");
143 return;
144 }
145
146 // Test if there are viable neighbours to current node
147 NeighbourContainerType viableNeighbours;
148 for (size_t iNeighbour = 0; iNeighbour < innerNeighbours.size(); ++iNeighbour) {
149 if (m_compatibilityChecker.areCompatible(currentPath.back(), innerNeighbours[iNeighbour])) {
150 viableNeighbours.push_back(innerNeighbours[iNeighbour]);
151 }
152 }
153
154 // If current path will continue, optionally store the subpath up to current node
155 if (m_storeSubsets && viableNeighbours.size() > 0) {
156 Path newPath = clone(currentPath);
157 storeAcceptedPath(newPath, allNodePaths);
158 }
159
160 for (size_t iNeighbour = 0; iNeighbour < viableNeighbours.size(); ++iNeighbour) {
161 // the last alternative is assigned to the existing path.
162 if (iNeighbour == viableNeighbours.size() - 1) {
163 currentPath.push_back(viableNeighbours[iNeighbour]);
164 NeighbourContainerType& newNeighbours = viableNeighbours[iNeighbour]->getInnerNodes();
165
166 findPathsRecursive(allNodePaths, currentPath, newNeighbours);
167 } else {
168 Path newPath = clone(currentPath);
169
170 newPath.push_back(viableNeighbours[iNeighbour]);
171 NeighbourContainerType& newNeighbours = viableNeighbours[iNeighbour]->getInnerNodes();
172
173 findPathsRecursive(allNodePaths, newPath, newNeighbours);
174 storeAcceptedPath(newPath, allNodePaths);
175 }
176 }
177 }

◆ printPaths()

template<class ContainerType, class NodeType, class NeighbourContainerType, class NodeCompatibilityCheckerType>
static std::string printPaths ( const std::vector< Path > & allPaths)
inlinestatic

Prints information about all paths provided in a vector of paths.

Definition at line 93 of file PathCollectorRecursive.h.

94 {
95 std::stringstream out;
96 unsigned int longestPath = 0, longesPathIndex = 0, index = 0;
97 out << "Print " << allPaths.size() << " paths:";
98 for (Path const& aPath : allPaths) {
99 if (longestPath < aPath.size()) {
100 longestPath = aPath.size();
101 longesPathIndex = index;
102 }
103 out << "\n" << "path " << index << ": length " << aPath.size() << ", entries:\n";
104 for (auto* entry : aPath) {
105 out << entry->getEntry() << "| ";
106 }
107 index++;
108 }
109 out << "\n" << "longest path was " << longesPathIndex << " with length of " << longestPath << "\n";
110
111 return out.str();
112 }

◆ storeAcceptedPath()

template<class ContainerType, class NodeType, class NeighbourContainerType, class NodeCompatibilityCheckerType>
void storeAcceptedPath ( Path newPath,
std::vector< Path > & allNodePaths ) const
inlineprotected

Tests length requirement on a path before adding it to path vector.

Definition at line 128 of file PathCollectorRecursive.h.

129 {
130 if (newPath.size() >= minPathLength) {
131 allNodePaths.push_back(newPath);
132 }
133 }

Member Data Documentation

◆ m_compatibilityChecker

template<class ContainerType, class NodeType, class NeighbourContainerType, class NodeCompatibilityCheckerType>
NodeCompatibilityCheckerType m_compatibilityChecker
protected

protected Data members:

Stores mini-Class for checking compatibility of two nodes passed.

Definition at line 197 of file PathCollectorRecursive.h.

◆ m_storeSubsets

template<class ContainerType, class NodeType, class NeighbourContainerType, class NodeCompatibilityCheckerType>
bool m_storeSubsets = false

flag if subsets should be stored or not

Definition at line 192 of file PathCollectorRecursive.h.

◆ minPathLength

template<class ContainerType, class NodeType, class NeighbourContainerType, class NodeCompatibilityCheckerType>
unsigned int minPathLength = 2

public Data members:

parameter for setting minimal path length: path length == number of nodes collected in a row from given network, this is not necessarily number of hits!

Definition at line 183 of file PathCollectorRecursive.h.

◆ nRecursiveCalls

template<class ContainerType, class NodeType, class NeighbourContainerType, class NodeCompatibilityCheckerType>
unsigned int nRecursiveCalls = 0

Counter for number of recursive calls.

Definition at line 189 of file PathCollectorRecursive.h.

◆ nTrees

template<class ContainerType, class NodeType, class NeighbourContainerType, class NodeCompatibilityCheckerType>
unsigned int nTrees = 0

Counter for number of trees found.

Definition at line 186 of file PathCollectorRecursive.h.

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