Belle II Software  release-05-02-19
PathCollectorRecursive.h
1 /**************************************************************************
2  * BASF2 (Belle Analysis Framework 2) *
3  * Copyright(C) 2015 - Belle II Collaboration *
4  * *
5  * Author: The Belle II Collaboration *
6  * Contributors: Jakob Lettenbichler, Jonas Wagner, Felix Metzner *
7  * *
8  * This software is provided "as is" without any warranty. *
9  **************************************************************************/
10 #pragma once
11 
12 #include <string>
13 #include <vector>
14 #include <sstream>
15 
16 #include <framework/logging/Logger.h>
17 
18 namespace Belle2 {
45  template<class ContainerType, class NodeType, class NeighbourContainerType, class NodeCompatibilityCheckerType>
46  class PathCollectorRecursive {
47  public:
49  using Path = std::vector<NodeType*>;
50 
51 
58  bool findPaths(ContainerType& aNetwork, std::vector<Path>& paths, unsigned int pathLimit, bool storeSubsets = false)
59  {
60  m_storeSubsets = storeSubsets;
61 
62  std::vector<Path> allNodePaths;
63  for (NodeType* aNode : aNetwork) {
64  if (aNode->getMetaInfo().isSeed() == false) {
65  continue;
66  }
67 
68  NeighbourContainerType& innerNeighbours = aNode->getInnerNodes();
69  if (innerNeighbours.empty()) {
70  continue;
71  }
72  if (aNode->getOuterNodes().empty()) {
73  nTrees++;
74  }
75 
76  // creating unique_ptr of a new path:
77  Path newPath = Path{aNode};
78 
79  findPathsRecursive(allNodePaths, newPath, innerNeighbours);
80  storeAcceptedPath(newPath, allNodePaths);
81 
82  if (allNodePaths.size() > pathLimit) {
83  B2ERROR("Number of collected paths to large. Aborting Event!");
84  return false;
85  }
86  }
87  paths = allNodePaths;
88  return true;
89  }
90 
91 
93  static std::string printPaths(std::vector<Path>& allPaths)
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  }
113 
114 
115  protected:
117  Path clone(Path& aPath) const
118  {
119  Path newPath = Path();
120  for (auto* entry : aPath) {
121  newPath.push_back(entry);
122  }
123  return newPath;
124  }
125 
126 
128  void storeAcceptedPath(Path newPath, std::vector<Path>& allNodePaths) const
129  {
130  if (newPath.size() >= minPathLength) {
131  allNodePaths.push_back(newPath);
132  }
133  }
134 
135 
137  void findPathsRecursive(std::vector<Path >& allNodePaths, Path& currentPath, NeighbourContainerType& innerNeighbours)
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  }
178 
179  public:
181 
183  unsigned int minPathLength = 2;
184 
186  unsigned int nTrees = 0;
187 
189  unsigned int nRecursiveCalls = 0;
190 
192  bool m_storeSubsets = false;
193 
194  protected:
196 
197  NodeCompatibilityCheckerType m_compatibilityChecker;
198  };
200 }
Belle2::PathCollectorRecursive::storeAcceptedPath
void storeAcceptedPath(Path newPath, std::vector< Path > &allNodePaths) const
Tests length requirement on a path before adding it to path vector.
Definition: PathCollectorRecursive.h:136
Belle2::PathCollectorRecursive::findPaths
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.
Definition: PathCollectorRecursive.h:66
Belle2::PathCollectorRecursive::Path
std::vector< NodeType * > Path
Using Path for vector of pointers to NodeTypes.
Definition: PathCollectorRecursive.h:57
Belle2::PathCollectorRecursive::nRecursiveCalls
unsigned int nRecursiveCalls
Counter for number of recursive calls.
Definition: PathCollectorRecursive.h:197
Belle2::PathCollectorRecursive::findPathsRecursive
void findPathsRecursive(std::vector< Path > &allNodePaths, Path &currentPath, NeighbourContainerType &innerNeighbours)
Recursive pathFinder: Collects all possible segment combinations to build paths.
Definition: PathCollectorRecursive.h:145
Belle2::PathCollectorRecursive::printPaths
static std::string printPaths(std::vector< Path > &allPaths)
Prints information about all paths provided in a vector of paths.
Definition: PathCollectorRecursive.h:101
Belle2
Abstract base class for different kinds of events.
Definition: MillepedeAlgorithm.h:19
Belle2::PathCollectorRecursive::clone
Path clone(Path &aPath) const
Copies path to create an identical one.
Definition: PathCollectorRecursive.h:125
Belle2::PathCollectorRecursive::minPathLength
unsigned int minPathLength
public Data members:
Definition: PathCollectorRecursive.h:191
Belle2::PathCollectorRecursive::m_compatibilityChecker
NodeCompatibilityCheckerType m_compatibilityChecker
protected Data members:
Definition: PathCollectorRecursive.h:205
Belle2::Path
Implements a path consisting of Module and/or Path objects.
Definition: Path.h:40
Belle2::PathCollectorRecursive::nTrees
unsigned int nTrees
Counter for number of trees found.
Definition: PathCollectorRecursive.h:194
Belle2::PathCollectorRecursive::m_storeSubsets
bool m_storeSubsets
flag if subsets should be stored or not
Definition: PathCollectorRecursive.h:200