PathCollectorRecursive.h

/**************************************************************************
 * basf2 (Belle II Analysis Software Framework)                           *
 * Author: The Belle II Collaboration                                     *
 *                                                                        *
 * See git log for contributors and copyright holders.                    *
 * This file is licensed under LGPL-3.0, see LICENSE.md.                  *
 **************************************************************************/
#pragma once
 
#include <string>
#include <vector>
#include <sstream>
 
#include <framework/logging/Logger.h>
 
namespace Belle2 {
  template<class ContainerType, class NodeType, class NeighbourContainerType, class NodeCompatibilityCheckerType>
  class PathCollectorRecursive {
  public:
    using Path = std::vector<NodeType*>;
 
 
    // cppcheck-suppress constParameter
    bool findPaths(ContainerType& aNetwork, std::vector<Path>& paths, unsigned int pathLimit, bool storeSubsets = false)
    {
      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;
    }
 
 
    static std::string printPaths(const std::vector<Path>& allPaths)
    {
      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();
    }
 
 
  protected:
    Path clone(const Path& aPath) const
    {
      Path newPath = Path();
      for (auto* entry : aPath) {
        newPath.push_back(entry);
      }
      return newPath;
    }
 
 
    void storeAcceptedPath(Path newPath, std::vector<Path>& allNodePaths) const
    {
      if (newPath.size() >= minPathLength) {
        allNodePaths.push_back(newPath);
      }
    }
 
 
    void findPathsRecursive(std::vector<Path >& allNodePaths, Path& currentPath, NeighbourContainerType& innerNeighbours)
    {
      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);
        }
      }
    }
 
  public:
 
    unsigned int minPathLength = 2;
 
    unsigned int nTrees = 0;
 
    unsigned int nRecursiveCalls = 0;
 
    bool m_storeSubsets = false;
 
  protected:
 
    NodeCompatibilityCheckerType m_compatibilityChecker;
  };
}