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

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()

Path clone ( const Path & aPath ) const

inlineprotected

Copies path to create an identical one.

Definition at line 117 of file PathCollectorRecursive.h.

    {
      Path newPath = Path();
      for (auto* entry : aPath) {
        newPath.push_back(entry);
      }
      return newPath;
    }

◆ findPaths()

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.

    {
      m_storeSubsets = storeSubsets;
 
      std::vector<Path> allNodePaths;
      for (NodeType* aNode : aNetwork) {
        if (aNode->getMetaInfo().isSeed() == false) {
          continue;
        }
 
        NeighbourContainerType& innerNeighbours = aNode->getInnerNodes();
        if (innerNeighbours.empty()) {
          continue;
        }
        if (aNode->getOuterNodes().empty()) {
          nTrees++;
        }
 
        // creating unique_ptr of a new path:
        Path newPath = Path{aNode};
 
        findPathsRecursive(allNodePaths, newPath, innerNeighbours);
        storeAcceptedPath(newPath, allNodePaths);
 
        if (allNodePaths.size() > pathLimit) {
          B2WARNING("Number of collected paths is too large: skipping the event and not processing it."
                    << LogVar("Number of node paths", allNodePaths.size()) << LogVar("Current limit of paths", pathLimit));
          return false;
        }
      }
      paths = allNodePaths;
      return true;
    }

◆ findPathsRecursive()

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.

    {
      nRecursiveCalls++;
 
      if (currentPath.size() > 30) {
        B2WARNING("findPathsRecursive reached a path length of over 30. Stopping Path here!");
        return;
      }
 
      // Test if there are viable neighbours to current node
      NeighbourContainerType viableNeighbours;
      for (size_t iNeighbour = 0; iNeighbour < innerNeighbours.size(); ++iNeighbour) {
        if (m_compatibilityChecker.areCompatible(currentPath.back(), innerNeighbours[iNeighbour])) {
          viableNeighbours.push_back(innerNeighbours[iNeighbour]);
        }
      }
 
      // If current path will continue, optionally store the subpath up to current node
      if (m_storeSubsets && viableNeighbours.size() > 0) {
        Path newPath = clone(currentPath);
        storeAcceptedPath(newPath, allNodePaths);
      }
 
      for (size_t iNeighbour = 0; iNeighbour < viableNeighbours.size(); ++iNeighbour) {
        // the last alternative is assigned to the existing path.
        if (iNeighbour == viableNeighbours.size() - 1) {
          currentPath.push_back(viableNeighbours[iNeighbour]);
          NeighbourContainerType& newNeighbours = viableNeighbours[iNeighbour]->getInnerNodes();
 
          findPathsRecursive(allNodePaths, currentPath, newNeighbours);
        } else {
          Path newPath = clone(currentPath);
 
          newPath.push_back(viableNeighbours[iNeighbour]);
          NeighbourContainerType& newNeighbours = viableNeighbours[iNeighbour]->getInnerNodes();
 
          findPathsRecursive(allNodePaths, newPath, newNeighbours);
          storeAcceptedPath(newPath, allNodePaths);
        }
      }
    }

◆ printPaths()

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.

    {
      std::stringstream out;
      unsigned int longestPath = 0, longesPathIndex = 0, index = 0;
      out << "Print " << allPaths.size() << " paths:";
      for (Path const& aPath : allPaths) {
        if (longestPath < aPath.size()) {
          longestPath = aPath.size();
          longesPathIndex = index;
        }
        out << "\n" << "path " << index << ": length " << aPath.size() << ", entries:\n";
        for (auto* entry : aPath) {
          out << entry->getEntry() << "| ";
        }
        index++;
      }
      out << "\n" << "longest path was " << longesPathIndex << " with length of " << longestPath << "\n";
 
      return out.str();
    }

◆ storeAcceptedPath()

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.

    {
      if (newPath.size() >= minPathLength) {
        allNodePaths.push_back(newPath);
      }
    }

Member Data Documentation

◆ m_compatibilityChecker

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

bool m_storeSubsets = false

flag if subsets should be stored or not

Definition at line 192 of file PathCollectorRecursive.h.

◆ minPathLength

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

unsigned int nRecursiveCalls = 0

Counter for number of recursive calls.

Definition at line 189 of file PathCollectorRecursive.h.

◆ nTrees

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:

tracking/trackFindingVXD/algorithms/include/PathCollectorRecursive.h

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ Path

Member Function Documentation

◆ clone()

◆ findPaths()

◆ findPathsRecursive()

◆ printPaths()

◆ storeAcceptedPath()

Member Data Documentation

◆ m_compatibilityChecker

◆ m_storeSubsets

◆ minPathLength

◆ nRecursiveCalls

◆ nTrees