source: src/Graph/BreadthFirstSearchAdd.cpp@ 48d20d

/*
 * Project: MoleCuilder
 * Description: creates and alters molecular systems
 * Copyright (C)  2010-2012 University of Bonn. All rights reserved.
 * 
 *
 *   This file is part of MoleCuilder.
 *
 *    MoleCuilder is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    MoleCuilder is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoleCuilder.  If not, see <http://www.gnu.org/licenses/>.
 */

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

#include "Atom/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, const enum HydrogenSaturation _saturation) :
  BondOrder(_BondOrder),
  Root(_Root),
  saturation(_saturation),
  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::ptr &Binder, bond::ptr &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;
  LOG(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.");
  if ((((ShortestPathList[OtherAtom->getNr()] < BondOrder) && (Binder != Bond)))) { // Check for maximum distance
    std::stringstream output;
    if (AddedAtomList[OtherAtom->getNr()] == NULL) { // add if it's not been so far
      AddedAtomList[OtherAtom->getNr()] = Mol->AddCopyAtom(OtherAtom);
      output << "Added OtherAtom " << OtherAtom->getName();
      AddedBondList[Binder] = Mol->CopyBond(AddedAtomList[Walker->getNr()], AddedAtomList[OtherAtom->getNr()], Binder);
      output << " 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)
      output << "Not adding OtherAtom " << OtherAtom->getName();
      if (AddedBondList[Binder] == NULL) {
        AddedBondList[Binder] = Mol->CopyBond(AddedAtomList[Walker->getNr()], AddedAtomList[OtherAtom->getNr()], Binder);
        output << ", added Bond " << *(AddedBondList[Binder]);
      } else
        output << ", not added Bond ";
    }
    output << ", putting OtherAtom into queue.";
    LOG(0, output.str());
    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)
    {
      std::stringstream output;
      if (Binder == Bond)
        output << "Not Queueing, is the Root bond";
      else if (ShortestPathList[OtherAtom->getNr()] >= BondOrder)
        output << "Not Queueing, is out of Bond Count of " << BondOrder;
      if (!Binder->Cyclic)
        output << ", is not part of a cyclic bond, saturating bond with Hydrogen.";
      LOG(3, output.str());
    }
    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 {
        if (saturation == DoSaturate)
          if (!Mol->AddHydrogenReplacementAtom(Binder, AddedAtomList[Walker->getNr()], Walker, OtherAtom, IsAngstroem))
            exit(1);
      }
    }
  }
}


void BreadthFirstSearchAdd::VisitedNode(molecule *Mol, atom *&Walker, atom *&OtherAtom, bond::ptr &Binder, bond::ptr &Bond)
{
  LOG(3, "Not Adding, has already been visited.");
  // 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)
      if (saturation == DoSaturate)
        if(!Mol->AddHydrogenReplacementAtom(Binder, AddedAtomList[Walker->getNr()], Walker, OtherAtom, IsAngstroem))
          exit(1);
    }
  }
}


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

  // 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();
    LOG(1, "Current Walker is: " << Walker->getName() << ", and has " << ListOfBonds.size() << " bonds.");
    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);
        LOG(2, "Current OtherAtom is: " << OtherAtom->getName() << " for bond " << *(*Runner) << ".");
        if (ColorList[OtherAtom->getNr()] == GraphEdge::white) {
          UnvisitedNode(Mol, Walker, OtherAtom, Binder, Bond);
        } else {
          VisitedNode(Mol, Walker, OtherAtom, Binder, Bond);
        }
      }
    }
    ColorList[Walker->getNr()] = GraphEdge::black;
    LOG(1, "Coloring Walker " << Walker->getName() << " GraphEdge::black.");
  }
}