source: src/Graph/BreadthFirstSearchAdd.cpp@ 3bdb6d

/*
 * 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.
 */

/*
 * BreadthFirstSearchAdd.cpp
 *
 *  Created on: Feb 16, 2011
 *      Author: heber
 */

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

#include "CodePatterns/MemDebug.hpp"

#include "BreadthFirstSearchAdd.hpp"

#include "atom.hpp"
#include "Bond/bond.hpp"
#include "CodePatterns/Assert.hpp"
#include "CodePatterns/Info.hpp"
#include "CodePatterns/Log.hpp"
#include "CodePatterns/Verbose.hpp"
#include "molecule.hpp"
#include "World.hpp"


BreadthFirstSearchAdd::BreadthFirstSearchAdd(atom *&_Root, int _BondOrder, bool _IsAngstroem) :
  BondOrder(_BondOrder),
  Root(_Root),
  IsAngstroem(_IsAngstroem)
{
  BFSStack.push_front(Root);
}


BreadthFirstSearchAdd::~BreadthFirstSearchAdd()
{}

void BreadthFirstSearchAdd::Init(atom *&_Root, int _BondOrder)
{
  BondOrder = _BondOrder;
  Root = _Root;
  BFSStack.clear();
  BFSStack.push_front(Root);
}

void BreadthFirstSearchAdd::InitNode(atomId_t atom_id)
{
  PredecessorList[atom_id] = NULL;
  ShortestPathList[atom_id] = -1;
  if (AddedAtomList.find(atom_id) != AddedAtomList.end()) // mark already present atoms (i.e. Root and maybe others) as visited
    ColorList[atom_id] = GraphEdge::lightgray;
  else
    ColorList[atom_id] = GraphEdge::white;
}


void BreadthFirstSearchAdd::UnvisitedNode(molecule *Mol, atom *&Walker, atom *&OtherAtom, bond *&Binder, bond *&Bond)
{
  if (Binder != Bond) // let other atom GraphEdge::white if it's via Root bond. In case it's cyclic it has to be reached again (yet Root is from OtherAtom already GraphEdge::black, thus no problem)
    ColorList[OtherAtom->getNr()] = GraphEdge::lightgray;
  PredecessorList[OtherAtom->getNr()] = Walker; // Walker is the predecessor
  ShortestPathList[OtherAtom->getNr()] = ShortestPathList[Walker->getNr()] + 1;
  DoLog(2) && (Log() << Verbose(2) << "Coloring OtherAtom " << OtherAtom->getName() << " " << GraphEdge::getColorName(ColorList[OtherAtom->getNr()]) << ", its predecessor is " << Walker->getName() << " and its Shortest Path is " << ShortestPathList[OtherAtom->getNr()] << " egde(s) long." << endl);
  if ((((ShortestPathList[OtherAtom->getNr()] < BondOrder) && (Binder != Bond)))) { // Check for maximum distance
    DoLog(3) && (Log() << Verbose(3));
    if (AddedAtomList[OtherAtom->getNr()] == NULL) { // add if it's not been so far
      AddedAtomList[OtherAtom->getNr()] = Mol->AddCopyAtom(OtherAtom);
      DoLog(0) && (Log() << Verbose(0) << "Added OtherAtom " << OtherAtom->getName());
      AddedBondList[Binder] = Mol->CopyBond(AddedAtomList[Walker->getNr()], AddedAtomList[OtherAtom->getNr()], Binder);
      DoLog(0) && (Log() << Verbose(0) << " and bond " << *(AddedBondList[Binder]) << ", ");
    } else { // this code should actually never come into play (all GraphEdge::white atoms are not yet present in BondMolecule, that's why they are GraphEdge::white in the first place)
      DoLog(0) && (Log() << Verbose(0) << "Not adding OtherAtom " << OtherAtom->getName());
      if (AddedBondList[Binder] == NULL) {
        AddedBondList[Binder] = Mol->CopyBond(AddedAtomList[Walker->getNr()], AddedAtomList[OtherAtom->getNr()], Binder);
        DoLog(0) && (Log() << Verbose(0) << ", added Bond " << *(AddedBondList[Binder]));
      } else
        DoLog(0) && (Log() << Verbose(0) << ", not added Bond ");
    }
    DoLog(0) && (Log() << Verbose(0) << ", putting OtherAtom into queue." << endl);
    BFSStack.push_front(OtherAtom);
  } else { // out of bond order, then replace
    if ((AddedAtomList[OtherAtom->getNr()] == NULL) && (Binder->Cyclic))
      ColorList[OtherAtom->getNr()] = GraphEdge::white; // unmark if it has not been queued/added, to make it available via its other bonds (cyclic)
    if (Binder == Bond)
      DoLog(3) && (Log() << Verbose(3) << "Not Queueing, is the Root bond");
    else if (ShortestPathList[OtherAtom->getNr()] >= BondOrder)
      DoLog(3) && (Log() << Verbose(3) << "Not Queueing, is out of Bond Count of " << BondOrder);
    if (!Binder->Cyclic)
      DoLog(0) && (Log() << Verbose(0) << ", is not part of a cyclic bond, saturating bond with Hydrogen." << endl);
    if (AddedBondList[Binder] == NULL) {
      if ((AddedAtomList[OtherAtom->getNr()] != NULL)) { // .. whether we add or saturate
        AddedBondList[Binder] = Mol->CopyBond(AddedAtomList[Walker->getNr()], AddedAtomList[OtherAtom->getNr()], Binder);
      } else {
#ifdef ADDHYDROGEN
        if (!Mol->AddHydrogenReplacementAtom(Binder, AddedAtomList[Walker->getNr()], Walker, OtherAtom, IsAngstroem))
        exit(1);
#endif
      }
    }
  }
}


void BreadthFirstSearchAdd::VisitedNode(molecule *Mol, atom *&Walker, atom *&OtherAtom, bond *&Binder, bond *&Bond)
{
  DoLog(3) && (Log() << Verbose(3) << "Not Adding, has already been visited." << endl);
  // This has to be a cyclic bond, check whether it's present ...
  if (AddedBondList[Binder] == NULL) {
    if ((Binder != Bond) && (Binder->Cyclic) && (((ShortestPathList[Walker->getNr()] + 1) < BondOrder))) {
      AddedBondList[Binder] = Mol->CopyBond(AddedAtomList[Walker->getNr()], AddedAtomList[OtherAtom->getNr()], Binder);
    } else { // if it's root bond it has to broken (otherwise we would not create the fragments)
#ifdef ADDHYDROGEN
      if(!Mol->AddHydrogenReplacementAtom(Binder, AddedAtomList[Walker->getNr()], Walker, OtherAtom, IsAngstroem))
      exit(1);
#endif
    }
  }
}


void BreadthFirstSearchAdd::operator()(molecule *Mol, atom *_Root, bond *Bond, int _BondOrder)
{
  Info FunctionInfo("BreadthFirstSearchAdd");
  atom *Walker = NULL, *OtherAtom = NULL;
  bond *Binder = NULL;

  // add Root if not done yet
  if (AddedAtomList[_Root->getNr()] == NULL) // add Root if not yet present
    AddedAtomList[_Root->getNr()] = Mol->AddCopyAtom(_Root);

  Init(_Root, _BondOrder);

  // and go on ... Queue always contains all GraphEdge::lightgray vertices
  while (!BFSStack.empty()) {
    // we have to pop the oldest atom from stack. This keeps the atoms on the stack always of the same ShortestPath distance.
    // e.g. if current atom is 2, push to end of stack are of length 3, but first all of length 2 would be popped. They again
    // append length of 3 (their neighbours). Thus on stack we have always atoms of a certain length n at bottom of stack and
    // followed by n+1 till top of stack.
    Walker = BFSStack.front(); // pop oldest added
    BFSStack.pop_front();
    const BondList& ListOfBonds = Walker->getListOfBonds();
    DoLog(1) && (Log() << Verbose(1) << "Current Walker is: " << Walker->getName() << ", and has " << ListOfBonds.size() << " bonds." << endl);
    for (BondList::const_iterator Runner = ListOfBonds.begin();
        Runner != ListOfBonds.end();
        ++Runner) {
      if ((*Runner) != NULL) { // don't look at bond equal NULL
        Binder = (*Runner);
        OtherAtom = (*Runner)->GetOtherAtom(Walker);
        DoLog(2) && (Log() << Verbose(2) << "Current OtherAtom is: " << OtherAtom->getName() << " for bond " << *(*Runner) << "." << endl);
        if (ColorList[OtherAtom->getNr()] == GraphEdge::white) {
          UnvisitedNode(Mol, Walker, OtherAtom, Binder, Bond);
        } else {
          VisitedNode(Mol, Walker, OtherAtom, Binder, Bond);
        }
      }
    }
    ColorList[Walker->getNr()] = GraphEdge::black;
    DoLog(1) && (Log() << Verbose(1) << "Coloring Walker " << Walker->getName() << " GraphEdge::black." << endl);
  }
}