source: src/Fragmentation/BondsPerShortestPath.cpp@ 50e4e5

/*
 * Project: MoleCuilder
 * Description: creates and alters molecular systems
 * Copyright (C)  2010 University of Bonn. All rights reserved.
 * Please see the LICENSE file or "Copyright notice" in builder.cpp for details.
 */

/*
 * BondsPerShortestPath.cpp
 *
 *  Created on: Oct 18, 2011
 *      Author: heber
 */

// include config.h
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include "CodePatterns/MemDebug.hpp"

#include "BondsPerShortestPath.hpp"

#include "CodePatterns/Log.hpp"

#include "atom.hpp"
#include "Bond/bond.hpp"
#include "Element/element.hpp"
#include "Fragmentation/KeySet.hpp"

BondsPerShortestPath::BondsPerShortestPath(int _Order) :
  Order(_Order)
{
  InitialiseSPList();
}

BondsPerShortestPath::~BondsPerShortestPath()
{
  // free Order-dependent entries of UniqueFragments structure for next loop cycle
  FreeSPList();
}

/** Allocates memory for BondsPerShortestPath::BondsPerSPList.
 * \sa BondsPerShortestPath::FreeSPList()
 */
void BondsPerShortestPath::InitialiseSPList()
{
  BondsPerSPList.resize(Order);
  BondsPerSPCount = new int[Order];
  for (int i=Order;i--;) {
    BondsPerSPCount[i] = 0;
  }
};

/** Free's memory for for BondsPerShortestPath::BondsPerSPList.
 * \sa BondsPerShortestPath::InitialiseSPList()
 */
void BondsPerShortestPath::FreeSPList()
{
  delete[](BondsPerSPCount);
};

/** Sets FragmenSearch to initial value.
 * Sets BondsPerShortestPath::ShortestPathList entries to zero, BondsPerShortestPath::BondsPerSPCount to zero (except zero level to 1) and
 * adds initial bond BondsPerShortestPath::Root to BondsPerShortestPath::Root to BondsPerShortestPath::BondsPerSPList
 * \param *_Root root node, self loop becomes first bond
 * \sa BondsPerShortestPath::FreeSPList()
 */
void BondsPerShortestPath::SetSPList(atom *_Root)
{
  // prepare root level (SP = 0) and a loop bond denoting Root
  for (int i=Order;i--;)
    BondsPerSPCount[i] = 0;
  BondsPerSPCount[0] = 1;
  bond *Binder = new bond(_Root, _Root);
  BondsPerSPList[0].push_back(Binder);
};

/** Resets BondsPerShortestPath::ShortestPathList and cleans bonds from BondsPerShortestPath::BondsPerSPList.
 * \sa BondsPerShortestPath::InitialiseSPList()
 */
void BondsPerShortestPath::ResetSPList()
{
  DoLog(0) && (Log() << Verbose(0) << "Free'ing all found lists. and resetting index lists" << endl);
  for(int i=Order;i--;) {
    DoLog(1) && (Log() << Verbose(1) << "Current SP level is " << i << ": ");
    // delete added bonds
    for (BondsPerSP::iterator iter = BondsPerSPList[i].begin();
        iter != BondsPerSPList[i].end();
        ++iter) {
      delete(*iter);
    }
    BondsPerSPList[i].clear();
    // also start and end node
    DoLog(0) && (Log() << Verbose(0) << "cleaned." << endl);
  }
};


/** Fills the Bonds per Shortest Path List and set the vertex labels.
 * \param _RootKeyNr index of root node
 * \param RestrictedKeySet Restricted vertex set to use in context of molecule
 * \param saturation this tells whether to treat hydrogen special or not.
 */
void BondsPerShortestPath::FillSPListandLabelVertices(int _RootKeyNr, KeySet &RestrictedKeySet, const enum HydrogenSaturation saturation)
{
  // Actually, we should construct a spanning tree vom the root atom and select all edges therefrom and put them into
  // according shortest path lists. However, we don't. Rather we fill these lists right away, as they do form a spanning
  // tree already sorted into various SP levels. That's why we just do loops over the depth (CurrentSP) and breadth
  // (EdgeinSPLevel) of this tree ...
  // In another picture, the bonds always contain a direction by rightatom being the one more distant from root and hence
  // naturally leftatom forming its predecessor, preventing the BFS"seeker" from continuing in the wrong direction.
  int AtomKeyNr = -1;
  atom *Walker = NULL;
  atom *OtherWalker = NULL;
  atom *Predecessor = NULL;
  bond *Binder = NULL;
  int RootKeyNr = _RootKeyNr;
  int RemainingWalkers = -1;
  int SP = -1;

  DoLog(0) && (Log() << Verbose(0) << "Starting BFS analysis ..." << endl);
  for (SP = 0; SP < (Order-1); SP++) {
    DoLog(1) && (Log() << Verbose(1) << "New SP level reached: " << SP << ", creating new SP list with " << BondsPerSPCount[SP] << " item(s)");
    if (SP > 0) {
      DoLog(0) && (Log() << Verbose(0) << ", old level closed with " << BondsPerSPCount[SP-1] << " item(s)." << endl);
      BondsPerSPCount[SP] = 0;
    } else
      DoLog(0) && (Log() << Verbose(0) << "." << endl);

    RemainingWalkers = BondsPerSPCount[SP];
    for (BondsPerSP::const_iterator CurrentEdge = BondsPerSPList[SP].begin();
        CurrentEdge != BondsPerSPList[SP].end();
        ++CurrentEdge) { /// start till end of this SP level's list
      RemainingWalkers--;
      Walker = (*CurrentEdge)->rightatom;    // rightatom is always the one more distant
      Predecessor = (*CurrentEdge)->leftatom;    // ... and leftatom is predecessor
      AtomKeyNr = Walker->getNr();
      DoLog(0) && (Log() << Verbose(0) << "Current Walker is: " << *Walker << " with nr " << Walker->getNr() << " and SP of " << SP << ", with " << RemainingWalkers << " remaining walkers on this level." << endl);
      // check for new sp level
      // go through all its bonds
      DoLog(1) && (Log() << Verbose(1) << "Going through all bonds of Walker." << endl);
      const BondList& ListOfBonds = Walker->getListOfBonds();
      for (BondList::const_iterator Runner = ListOfBonds.begin();
          Runner != ListOfBonds.end();
          ++Runner) {
        OtherWalker = (*Runner)->GetOtherAtom(Walker);
        if ((RestrictedKeySet.find(OtherWalker->getNr()) != RestrictedKeySet.end())
            // skip hydrogens if desired and restrict to fragment
            && ((saturation == DontSaturate) || (OtherWalker->getType()->getAtomicNumber() != 1))) {
          DoLog(2) && (Log() << Verbose(2) << "Current partner is " << *OtherWalker << " with nr " << OtherWalker->getNr() << " in bond " << *(*Runner) << "." << endl);
          // set the label if not set (and push on root stack as well)
          if ((OtherWalker != Predecessor) && (OtherWalker->GetTrueFather()->getNr() > RootKeyNr)) { // only pass through those with label bigger than Root's
            // add the bond in between to the SP list
            Binder = new bond(Walker, OtherWalker); // create a new bond in such a manner, that bond::rightatom is always the one more distant
            BondsPerSPList[SP+1].push_back(Binder);
            BondsPerSPCount[SP+1]++;
            DoLog(3) && (Log() << Verbose(3) << "Added its bond to SP list, having now " << BondsPerSPCount[SP+1] << " item(s)." << endl);
          } else {
            if (OtherWalker != Predecessor)
              DoLog(3) && (Log() << Verbose(3) << "Not passing on, as index of " << *OtherWalker << " " << OtherWalker->GetTrueFather()->getNr() << " is smaller than that of Root " << RootKeyNr << "." << endl);
            else
              DoLog(3) && (Log() << Verbose(3) << "This is my predecessor " << *Predecessor << "." << endl);
          }
        } else Log() << Verbose(2) << "Is not in the restricted keyset or skipping hydrogen " << *OtherWalker << "." << endl;
      }
    }
  }
};

/** prints the Bonds per Shortest Path list in BondsPerShortestPath.
 */
void BondsPerShortestPath::OutputSPList()
{
  DoLog(0) && (Log() << Verbose(0) << "Printing all found lists." << endl);
  for(int i=1;i<Order;i++) {    // skip the root edge in the printing
    DoLog(1) && (Log() << Verbose(1) << "Current SP level is " << i << "." << endl);
    for (BondsPerShortestPath::BondsPerSP::const_iterator Binder = BondsPerSPList[i].begin();
        Binder != BondsPerSPList[i].end();
        ++Binder) {
      DoLog(2) && (Log() << Verbose(2) << *Binder << endl);
    }
  }
};

/** Simply counts all bonds in all BondsPerShortestPath::BondsPerSPList lists.
 */
int BondsPerShortestPath::CountNumbersInBondsList()
{
  int SP = -1;  // the Root <-> Root edge must be subtracted!
  for(int i=Order;i--;) { // sum up all found edges
    for (BondsPerShortestPath::BondsPerSP::const_iterator Binder = BondsPerSPList[i].begin();
        Binder != BondsPerSPList[i].end();
        ++Binder) {
      SP++;
    }
  }
  return SP;
};

/** Getter for BondsPerShortestPath::Order.
 *
 * @return returns BondsPerShortestPath::Order
 */
int BondsPerShortestPath::getOrder() const
{
  return Order;
}