SectorGraph.h

/**************************************************************************
 * BASF2 (Belle Analysis Framework 2)                                     *
 * Copyright(C) 2015 - Belle II Collaboration                             *
 *                                                                        *
 * Author: The Belle II Collaboration                                     *
 * Contributors: Jakob Lettenbichler (jakob.lettenbichler@oeaw.ac.at)     *
 *                                                                        *
 * This software is provided "as is" without any warranty.                *
 **************************************************************************/
 
#pragma once
 
#include <framework/logging/Logger.h>
#include <tracking/trackFindingVXD/sectorMapTools/SubGraphID.h>
#include <tracking/trackFindingVXD/sectorMapTools/SubGraph.h>
 
#include <string>
#include <vector>
#include <unordered_map>
#include <utility> // std::pair, std::move
 
 
namespace Belle2 {
  template<class FilterType>  class SectorGraph {
  protected:
    std::unordered_map<SubGraphID, SubGraph<FilterType>> m_subgraphs; 
    std::vector<FilterType> m_filterIDs; 
  public:
 
    explicit SectorGraph(std::vector<FilterType>& fIDs) : m_filterIDs(fIDs)
    { if (m_filterIDs.empty()) { B2FATAL("SectorGraph-constructor: passed filterIDs are empty, this is an illegal usage of this class!"); } }
 
    using Iterator = typename std::unordered_map<SubGraphID, SubGraph<FilterType>>::iterator;
 
    Iterator find(SubGraphID idChain) { return m_subgraphs.find(idChain); }
 
    Iterator begin() { return m_subgraphs.begin(); }
 
    Iterator end() { return m_subgraphs.end(); }
 
    unsigned size() const { return m_subgraphs.size(); }
 
    unsigned long nFoundTotal() const
    {
      unsigned long nFound = 0;
      for (auto& pack : m_subgraphs) { nFound += pack.second.getFound(); }
      return nFound;
    }
 
    Iterator add(SubGraphID& newID)
    {
      if (m_subgraphs.find(newID) != end())
      { B2WARNING("SectorGraph::add: given ID " << newID.print() << " is already in graph, not added again..."); return end(); }
      std::pair<Iterator, bool> pos = m_subgraphs.insert({newID, SubGraph<FilterType>(newID, m_filterIDs)});
      B2DEBUG(1, "SectorGraph::add: new subgraph added: " << pos.first->second.print());
      return pos.first;
    }
 
    std::string print(bool fullPrint = true) const
    {
      unsigned nSubgraphs = m_subgraphs.size();
      std::string out = "graph has got " + std::to_string(nSubgraphs) + " entries:\n";
      out += "now printing " + (fullPrint ? std::string("full") : std::string("short version of the")) + " graph:\n";
      for (const auto& entry : m_subgraphs) {
        if (!fullPrint and nSubgraphs % 100 != 0) continue; // printing only 100 subgraphs of mainGraph for the short version.
        out += entry.second.print() + "\n";
      }
      return out;
    }
 
    unsigned pruneGraph(double rarenessCut)
    {
      //sanity checks:
      if (rarenessCut < 0 or rarenessCut >= 1)
      { B2WARNING("pruneGraph: rarenessCut is rubbish: " << rarenessCut << ", stopping prune-process."); return 0; }
      if (rarenessCut == 0) { B2DEBUG(1, "pruneGraph: nothing to be done, stopping prune-process."); return 0; }
 
      // .first counts total number of occurances of branches of this trunk (= outer sector(s))
      // .second is a vector of pointers to the subgraphs of that trunk.
      std::vector< std::pair<unsigned, std::vector<SubGraph<FilterType>*> >> trunks;
 
      // find those sharing a trunk (trunkTotal) and cluster them in these trunks:
      for (auto& subGraphEntry : m_subgraphs) {
        SubGraph<FilterType>& graph = subGraphEntry.second;
        bool found = false;
        for (auto& trunk : trunks) {
          if (graph.checkSharesTrunk(*(trunk.second.at(0)))) {
            trunk.first += graph.getFound();
            trunk.second.push_back(&graph);
            found = true;
            continue;
          }
 
          if (found) continue;
          trunks.push_back({graph.getFound(), {&graph} });
        }
      }
 
      unsigned long nFoundB4 = nFoundTotal(), nKilled = 0;
      unsigned sizeb4 = size();
      B2DEBUG(1, "pruneGraph - before pruning: graph of size " << sizeb4 << " has " << trunks.size() << " trunks with " << nFoundB4 <<
              " total found.");
 
      // collect subGraphs (=branches) to be deleted:
      std::vector<SubGraph<FilterType>*> deadBranches;
      for (auto& trunk : trunks) {
        double trunkCut = rarenessCut * double(trunk.first);
 
        // sort branches of trunk by rareness (rarest one first):
        std::sort(trunk.second.begin(),
                  trunk.second.end(),
                  [](const SubGraph<FilterType>* a, const SubGraph<FilterType>* b)
                  -> bool { return a->getFound() < b->getFound(); });
 
        // skip trunk, if there are no rare branches.
        auto pos = trunk.second.begin();
        if (double((**pos).getFound()) >= trunkCut) continue;
 
        // collect branches to be killed starting with the smallest one and stop when reaching those which have been slipping above the threshold in the process:
        while (pos != trunk.second.end()) {
          // mark the most rarest entry:
          deadBranches.push_back(*pos);
          trunkCut -= double((**pos).getFound()) * rarenessCut;
 
          // reached the point when all graphs left are now good enough for us: -> stopping loop.
          if (double((**pos).getFound()) >= trunkCut) break;
          ++pos;
        }
      } // looping over trunks
 
      if (deadBranches.empty()) { B2DEBUG(1, "pruneGraph: no rare branches found - stopping pruning process."); return 0; }
 
      // kill selected ones:
      for (auto* graph : deadBranches) {
        nKilled += graph->getFound();
        m_subgraphs.erase(graph->getID());
      }
 
      B2DEBUG(1, "pruneGraph - after pruning graph with size (before/after " << sizeb4 << "/" << size() <<
              ") and nFound (before/after/killed " << nFoundB4 << "/" << nFoundTotal() << "/" << nKilled);
 
      return nKilled;
    }
 
 
    void updateSubLayerIDs()
    {
      unsigned nUpdated = 0, // counts sectors which shall be updated
               nFound = 0, // counts sectors which were found (without double entry removal)
               nGraphsUpdated = 0; // counts graphs which were updated
 
      // collects the secIDs which have got inner sectors on same sensor:
      std::vector<unsigned> idsFound;
      std::string idsPrinted;
 
      // collect all SecIDs where SubLayer has to be updated.
      for (auto& subGraphEntry : m_subgraphs) {
        SubGraphID graphID = subGraphEntry.second.getID();
        std::vector<unsigned> found = graphID.hasSharedLayer();
        if (found.empty()) continue;
        idsFound.insert(idsFound.end(), found.begin(), found.end());
      }
      for (unsigned id : idsFound) { idsPrinted += FullSecID(id).getFullSecString() + " "; }
      B2DEBUG(1, "updateSubLayerIDs: before unique of found ids, following IDs are recorded: \n" << idsPrinted);
      nFound += idsFound.size();
      std::sort(idsFound.begin(), idsFound.end());
      idsFound.erase(std::unique(idsFound.begin(), idsFound.end()), idsFound.end());
      nUpdated += idsFound.size();
 
      idsPrinted = "";
      for (unsigned id : idsFound) { idsPrinted += FullSecID(id).getFullSecString() + " "; }
      B2DEBUG(1, "updateSubLayerIDs: before updating Subgraphs, following IDs have to be updated: \n" << idsPrinted);
 
 
      // update all subGraphIDs where subLayerID has to be increased:
      for (auto& subGraphEntry : m_subgraphs) {
        SubGraph<FilterType>& graph = subGraphEntry.second;
        unsigned nSecsUpdated = graph.idCheckAndUpdate(idsFound);
        if (nSecsUpdated == 0) {
          B2DEBUG(50, "updateSubLayerIDs: was _not_ updated: " << graph.getID().print());
          continue;
        }
        nGraphsUpdated++;
        B2DEBUG(50, "updateSubLayerIDs: was updated " << nSecsUpdated << " times: " << graph.getID().print());
      }
 
      B2DEBUG(1, "updateSubLayerIDs: nSectors found/updated: " << nFound << "/" << nUpdated << ", nSubgraphs updated: " <<
              nGraphsUpdated);
 
      // create new map of Subgraphs with updated LayerIDs
      // subGraph: copy with updated iD.
      // SubGraphID: a.isElementOf(SubGraphID& b) <- checks if given sectorPack ( >= 1 sector) is part of a, ignores subLayerID.
      // SubGraphID: a.replaceElement(SubGraphID& b) <- checks if given sectorPack ( >= 1 sector) is part of a, ignores subLayerID. if yes, replaces element(s). WARNING only works with complete replacement of SubGraphID (entries are const).
      // SubGraphID: a.areTheSameSectors(SubGraphID& b) <- checks if sectors are identical (while ignoring the subLayerID)
      // SubGraphID: a.sharesLayer() <- returns IDs of entries being inner friend of sectors on same layer.
 
      // return new map of Subgraphs.
    }
 
    std::vector<FullSecID> getAllFullSecIDsOfSensor(VxdID sensor)
    {
      std::vector<FullSecID> foundIDs;
 
      for (auto& subGraph : m_subgraphs) {
        std::vector<FullSecID> sectorsFound = subGraph.second.getSectorsOfSensor(sensor);
        if (sectorsFound.empty()) continue;
        foundIDs.insert(foundIDs.end(), sectorsFound.begin(), sectorsFound.end());
      }
      B2DEBUG(1, "getAllFullSecIDsOfSensor: VxdID " << sensor << " has " << foundIDs.size() << " sectors in this graph");
      return foundIDs;
    }
 
    const std::vector<FilterType>& getFilterTypes() const { return m_filterIDs; }
  };
}