source: src/molecules.cpp@ 570125

/** \file molecules.cpp
 *
 * Functions for the class molecule.
 *
 */

#include "config.hpp"
#include "molecules.hpp"

/************************************* Other Functions *************************************/

/** Determines sum of squared distances of \a X to all \a **vectors.
 * \param *x reference vector
 * \param *params
 * \return sum of square distances
 */
double LSQ (const gsl_vector * x, void * params)
{
  double sum = 0.;
  struct LSQ_params *par = (struct LSQ_params *)params;
  Vector **vectors = par->vectors;
  int num = par->num;

  for (int i=num;i--;) {
    for(int j=NDIM;j--;)
      sum += (gsl_vector_get(x,j) - (vectors[i])->x[j])*(gsl_vector_get(x,j) - (vectors[i])->x[j]);
  }

  return sum;
};

/************************************* Functions for class molecule *********************************/

/** Constructor of class molecule.
 * Initialises molecule list with correctly referenced start and end, and sets molecule::last_atom to zero.
 */
molecule::molecule(periodentafel *teil)
{
  // init atom chain list
  start = new atom;
  end = new atom;
  start->father = NULL;
  end->father = NULL;
  link(start,end);
  InternalPointer = start;
  // init bond chain list
  first = new bond(start, end, 1, -1);
  last = new bond(start, end, 1, -1);
  link(first,last);
  // other stuff
  MDSteps = 0;
  last_atom = 0;
  elemente = teil;
  AtomCount = 0;
  BondCount = 0;
  NoNonBonds = 0;
  NoNonHydrogen = 0;
  NoCyclicBonds = 0;
  ListOfBondsPerAtom = NULL;
  NumberOfBondsPerAtom = NULL;
  ElementCount = 0;
  for(int i=MAX_ELEMENTS;i--;)
    ElementsInMolecule[i] = 0;
  cell_size[0] = cell_size[2] = cell_size[5]= 20.;
  cell_size[1] = cell_size[3] = cell_size[4]= 0.;
  strcpy(name,"none");
  IndexNr  = -1;
  ActiveFlag = false;
  TesselStruct = NULL;
};

/** Destructor of class molecule.
 * Initialises molecule list with correctly referenced start and end, and sets molecule::last_atom to zero.
 */
molecule::~molecule()
{
  if (ListOfBondsPerAtom != NULL)
    for(int i=AtomCount;i--;)
      Free((void **)&ListOfBondsPerAtom[i], "molecule::~molecule: ListOfBondsPerAtom[i]");
  Free((void **)&ListOfBondsPerAtom, "molecule::~molecule: ListOfBondsPerAtom");
  Free((void **)&NumberOfBondsPerAtom, "molecule::~molecule: NumberOfBondsPerAtom");
  if (TesselStruct != NULL)
    delete(TesselStruct);
  CleanupMolecule();
  delete(first);
  delete(last);
  delete(end);
  delete(start);
};


/** Determine center of all atoms.
 * \param *out output stream for debugging
 * \return pointer to allocated with central coordinates
 */
Vector *molecule::GetCenter(ofstream *out)
{
  Vector *center = DetermineCenterOfAll(out);
  return center;
};

/** Return current atom in the list.
 * \return pointer to atom or NULL if none present
 */
TesselPoint *molecule::GetPoint()
{
  if ((InternalPointer != start) && (InternalPointer != end))
    return InternalPointer;
  else
    return NULL;
};

/** Return pointer to one after last atom in the list.
 * \return pointer to end marker
 */
TesselPoint *molecule::GetTerminalPoint()
{
  return end;
};

/** Go to next atom.
 * Stops at last one.
 */
void molecule::GoToNext()
{
  if (InternalPointer != end)
    InternalPointer = InternalPointer->next;
};

/** Go to previous atom.
 * Stops at first one.
 */
void molecule::GoToPrevious()
{
  if (InternalPointer->previous != start)
    InternalPointer = InternalPointer->previous;
};

/** Goes to first atom.
 */
void molecule::GoToFirst()
{
  InternalPointer = start->next;
};

/** Goes to last atom.
 */
void molecule::GoToLast()
{
  InternalPointer = end->previous;
};

/** Checks whether we have any atoms in molecule.
 * \return true - no atoms, false - not empty
 */
bool molecule::IsEmpty()
{
  return (start->next == end);
};

/** Checks whether we are at the last atom
 * \return true - current atom is last one, false - is not last one
 */
bool molecule::IsEnd()
{
  return (InternalPointer == end);
};

/** Adds given atom \a *pointer from molecule list.
 * Increases molecule::last_atom and gives last number to added atom and names it according to its element::abbrev and molecule::AtomCount
 * \param *pointer allocated and set atom
 * \return true - succeeded, false - atom not found in list
 */
bool molecule::AddAtom(atom *pointer)
{
  if (pointer != NULL) {
    pointer->sort = &pointer->nr;
    pointer->nr = last_atom++;  // increase number within molecule
    AtomCount++;
    if (pointer->type != NULL) {
      if (ElementsInMolecule[pointer->type->Z] == 0)
        ElementCount++;
      ElementsInMolecule[pointer->type->Z]++; // increase number of elements
      if (pointer->type->Z != 1)
        NoNonHydrogen++;
      if (pointer->Name == NULL) {
        Free((void **)&pointer->Name, "molecule::AddAtom: *pointer->Name");
        pointer->Name = (char *) Malloc(sizeof(char)*6, "molecule::AddAtom: *pointer->Name");
        sprintf(pointer->Name, "%2s%02d", pointer->type->symbol, pointer->nr+1);
      }
    }
    return add(pointer, end);
  } else
    return false;
};

/** Adds a copy of the given atom \a *pointer from molecule list.
 * Increases molecule::last_atom and gives last number to added atom.
 * \param *pointer allocated and set atom
 * \return true - succeeded, false - atom not found in list
 */
atom * molecule::AddCopyAtom(atom *pointer)
{
  if (pointer != NULL) {
    atom *walker = new atom(pointer);
    walker->Name = (char *) Malloc(sizeof(char)*strlen(pointer->Name)+1, "atom::atom: *Name");
    strcpy (walker->Name, pointer->Name);
    walker->nr = last_atom++;  // increase number within molecule
    add(walker, end);
    if ((pointer->type != NULL) && (pointer->type->Z != 1))
      NoNonHydrogen++;
    AtomCount++;
    return walker;
  } else
    return NULL;
};

/** Adds a Hydrogen atom in replacement for the given atom \a *partner in bond with a *origin.
 * Here, we have to distinguish between single, double or triple bonds as stated by \a BondDegree, that each demand
 * a different scheme when adding \a *replacement atom for the given one.
 * -# Single Bond: Simply add new atom with bond distance rescaled to typical hydrogen one
 * -# Double Bond: Here, we need the **BondList of the \a *origin atom, by scanning for the other bonds instead of
 *    *Bond, we use the through these connected atoms to determine the plane they lie in, vector::MakeNormalvector().
 *    The orthonormal vector to this plane along with the vector in *Bond direction determines the plane the two
 *    replacing hydrogens shall lie in. Now, all remains to do is take the usual hydrogen double bond angle for the
 *    element of *origin and form the sin/cos admixture of both plane vectors for the new coordinates of the two
 *    hydrogens forming this angle with *origin.
 * -# Triple Bond: The idea is to set up a tetraoid (C1-H1-H2-H3) (however the lengths \f$b\f$ of the sides of the base
 *    triangle formed by the to be added hydrogens are not equal to the typical bond distance \f$l\f$ but have to be
 *    determined from the typical angle \f$\alpha\f$ for a hydrogen triple connected to the element of *origin):
 *    We have the height \f$d\f$ as the vector in *Bond direction (from triangle C1-H1-H2).
 *    \f[ h = l \cdot \cos{\left (\frac{\alpha}{2} \right )} \qquad b = 2l \cdot \sin{\left (\frac{\alpha}{2} \right)} \quad \rightarrow \quad d = l \cdot \sqrt{\cos^2{\left (\frac{\alpha}{2} \right)}-\frac{1}{3}\cdot\sin^2{\left (\frac{\alpha}{2}\right )}}
 *    \f]
 *    vector::GetNormalvector() creates one orthonormal vector from this *Bond vector and vector::MakeNormalvector creates
 *    the third one from the former two vectors. The latter ones form the plane of the base triangle mentioned above.
 *    The lengths for these are \f$f\f$ and \f$g\f$ (from triangle H1-H2-(center of H1-H2-H3)) with knowledge that
 *    the median lines in an isosceles triangle meet in the center point with a ratio 2:1.
 *    \f[ f = \frac{b}{\sqrt{3}} \qquad g = \frac{b}{2}
 *    \f]
 *    as the coordination of all three atoms in the coordinate system of these three vectors:
 *    \f$\pmatrix{d & f & 0}\f$, \f$\pmatrix{d & -0.5 \cdot f & g}\f$ and \f$\pmatrix{d & -0.5 \cdot f & -g}\f$.
 *
 * \param *out output stream for debugging
 * \param *Bond pointer to bond between \a *origin and \a *replacement
 * \param *TopOrigin son of \a *origin of upper level molecule (the atom added to this molecule as a copy of \a *origin)
 * \param *origin pointer to atom which acts as the origin for scaling the added hydrogen to correct bond length
 * \param *replacement pointer to the atom which shall be copied as a hydrogen atom in this molecule
 * \param **BondList list of bonds \a *replacement has (necessary to determine plane for double and triple bonds)
 * \param NumBond  number of bonds in \a **BondList
 * \param isAngstroem whether the coordination of the given atoms is in AtomicLength (false) or Angstrom(true)
 * \return number of atoms added, if < bond::BondDegree then something went wrong
 * \todo double and triple bonds splitting (always use the tetraeder angle!)
 */
bool molecule::AddHydrogenReplacementAtom(ofstream *out, bond *TopBond, atom *BottomOrigin, atom *TopOrigin, atom *TopReplacement, bond **BondList, int NumBond, bool IsAngstroem)
{
  double bondlength;  // bond length of the bond to be replaced/cut
  double bondangle;  // bond angle of the bond to be replaced/cut
  double BondRescale;   // rescale value for the hydrogen bond length
  bool AllWentWell = true;    // flag gathering the boolean return value of molecule::AddAtom and other functions, as return value on exit
  bond *FirstBond = NULL, *SecondBond = NULL; // Other bonds in double bond case to determine "other" plane
  atom *FirstOtherAtom = NULL, *SecondOtherAtom = NULL, *ThirdOtherAtom = NULL; // pointer to hydrogen atoms to be added
  double b,l,d,f,g, alpha, factors[NDIM];    // hold temporary values in triple bond case for coordination determination
  Vector Orthovector1, Orthovector2;  // temporary vectors in coordination construction
  Vector InBondvector;    // vector in direction of *Bond
  bond *Binder = NULL;
  double *matrix;

//  *out << Verbose(3) << "Begin of AddHydrogenReplacementAtom." << endl;
  // create vector in direction of bond
  InBondvector.CopyVector(&TopReplacement->x);
  InBondvector.SubtractVector(&TopOrigin->x);
  bondlength = InBondvector.Norm();

   // is greater than typical bond distance? Then we have to correct periodically
   // the problem is not the H being out of the box, but InBondvector have the wrong direction
   // due to TopReplacement or Origin being on the wrong side!
  if (bondlength > BondDistance) {
//    *out << Verbose(4) << "InBondvector is: ";
//    InBondvector.Output(out);
//    *out << endl;
    Orthovector1.Zero();
    for (int i=NDIM;i--;) {
      l = TopReplacement->x.x[i] - TopOrigin->x.x[i];
      if (fabs(l) > BondDistance) { // is component greater than bond distance
        Orthovector1.x[i] = (l < 0) ? -1. : +1.;
      } // (signs are correct, was tested!)
    }
    matrix = ReturnFullMatrixforSymmetric(cell_size);
    Orthovector1.MatrixMultiplication(matrix);
    InBondvector.SubtractVector(&Orthovector1); // subtract just the additional translation
    Free((void **)&matrix, "molecule::AddHydrogenReplacementAtom: *matrix");
    bondlength = InBondvector.Norm();
//    *out << Verbose(4) << "Corrected InBondvector is now: ";
//    InBondvector.Output(out);
//    *out << endl;
  } // periodic correction finished

  InBondvector.Normalize();
  // get typical bond length and store as scale factor for later
  BondRescale = TopOrigin->type->HBondDistance[TopBond->BondDegree-1];
  if (BondRescale == -1) {
    cerr << Verbose(3) << "ERROR: There is no typical hydrogen bond distance in replacing bond (" << TopOrigin->Name << "<->" << TopReplacement->Name << ") of degree " << TopBond->BondDegree << "!" << endl;
    return false;
    BondRescale = bondlength;
  } else {
    if (!IsAngstroem)
      BondRescale /= (1.*AtomicLengthToAngstroem);
  }

  // discern single, double and triple bonds
  switch(TopBond->BondDegree) {
    case 1:
      FirstOtherAtom = new atom();    // new atom
      FirstOtherAtom->type = elemente->FindElement(1);  // element is Hydrogen
      FirstOtherAtom->v.CopyVector(&TopReplacement->v); // copy velocity
      FirstOtherAtom->FixedIon = TopReplacement->FixedIon;
      if (TopReplacement->type->Z == 1) { // neither rescale nor replace if it's already hydrogen
        FirstOtherAtom->father = TopReplacement;
        BondRescale = bondlength;
      } else {
        FirstOtherAtom->father = NULL;  // if we replace hydrogen, we mark it as our father, otherwise we are just an added hydrogen with no father
      }
      InBondvector.Scale(&BondRescale);   // rescale the distance vector to Hydrogen bond length
      FirstOtherAtom->x.CopyVector(&TopOrigin->x); // set coordination to origin ...
      FirstOtherAtom->x.AddVector(&InBondvector);  // ... and add distance vector to replacement atom
      AllWentWell = AllWentWell && AddAtom(FirstOtherAtom);
//      *out << Verbose(4) << "Added " << *FirstOtherAtom << " at: ";
//      FirstOtherAtom->x.Output(out);
//      *out << endl;
      Binder = AddBond(BottomOrigin, FirstOtherAtom, 1);
      Binder->Cyclic = false;
      Binder->Type = TreeEdge;
      break;
    case 2:
      // determine two other bonds (warning if there are more than two other) plus valence sanity check
      for (int i=0;i<NumBond;i++) {
        if (BondList[i] != TopBond) {
          if (FirstBond == NULL) {
            FirstBond = BondList[i];
            FirstOtherAtom = BondList[i]->GetOtherAtom(TopOrigin);
          } else if (SecondBond == NULL) {
            SecondBond = BondList[i];
            SecondOtherAtom = BondList[i]->GetOtherAtom(TopOrigin);
          } else {
            *out << Verbose(3) << "WARNING: Detected more than four bonds for atom " << TopOrigin->Name;
          }
        }
      }
      if (SecondOtherAtom == NULL) {  // then we have an atom with valence four, but only 3 bonds: one to replace and one which is TopBond (third is FirstBond)
        SecondBond = TopBond;
        SecondOtherAtom = TopReplacement;
      }
      if (FirstOtherAtom != NULL) { // then we just have this double bond and the plane does not matter at all
//        *out << Verbose(3) << "Regarding the double bond (" << TopOrigin->Name << "<->" << TopReplacement->Name << ") to be constructed: Taking " << FirstOtherAtom->Name << " and " << SecondOtherAtom->Name << " along with " << TopOrigin->Name << " to determine orthogonal plane." << endl;

        // determine the plane of these two with the *origin
        AllWentWell = AllWentWell && Orthovector1.MakeNormalVector(&TopOrigin->x, &FirstOtherAtom->x, &SecondOtherAtom->x);
      } else {
        Orthovector1.GetOneNormalVector(&InBondvector);
      }
      //*out << Verbose(3)<< "Orthovector1: ";
      //Orthovector1.Output(out);
      //*out << endl;
      // orthogonal vector and bond vector between origin and replacement form the new plane
      Orthovector1.MakeNormalVector(&InBondvector);
      Orthovector1.Normalize();
      //*out << Verbose(3) << "ReScaleCheck: " << Orthovector1.Norm() << " and " << InBondvector.Norm() << "." << endl;

      // create the two Hydrogens ...
      FirstOtherAtom = new atom();
      SecondOtherAtom = new atom();
      FirstOtherAtom->type = elemente->FindElement(1);
      SecondOtherAtom->type = elemente->FindElement(1);
      FirstOtherAtom->v.CopyVector(&TopReplacement->v); // copy velocity
      FirstOtherAtom->FixedIon = TopReplacement->FixedIon;
      SecondOtherAtom->v.CopyVector(&TopReplacement->v); // copy velocity
      SecondOtherAtom->FixedIon = TopReplacement->FixedIon;
      FirstOtherAtom->father = NULL;  // we are just an added hydrogen with no father
      SecondOtherAtom->father = NULL;  //  we are just an added hydrogen with no father
      bondangle = TopOrigin->type->HBondAngle[1];
      if (bondangle == -1) {
        *out << Verbose(3) << "ERROR: There is no typical hydrogen bond angle in replacing bond (" << TopOrigin->Name << "<->" << TopReplacement->Name << ") of degree " << TopBond->BondDegree << "!" << endl;
        return false;
        bondangle = 0;
      }
      bondangle *= M_PI/180./2.;
//      *out << Verbose(3) << "ReScaleCheck: InBondvector ";
//      InBondvector.Output(out);
//      *out << endl;
//      *out << Verbose(3) << "ReScaleCheck: Orthovector ";
//      Orthovector1.Output(out);
//      *out << endl;
//      *out << Verbose(3) << "Half the bond angle is " << bondangle << ", sin and cos of it: " << sin(bondangle) << ", " << cos(bondangle) << endl;
      FirstOtherAtom->x.Zero();
      SecondOtherAtom->x.Zero();
      for(int i=NDIM;i--;) { // rotate by half the bond angle in both directions (InBondvector is bondangle = 0 direction)
        FirstOtherAtom->x.x[i] = InBondvector.x[i] * cos(bondangle) + Orthovector1.x[i] * (sin(bondangle));
        SecondOtherAtom->x.x[i] = InBondvector.x[i] * cos(bondangle) + Orthovector1.x[i] * (-sin(bondangle));
      }
      FirstOtherAtom->x.Scale(&BondRescale);  // rescale by correct BondDistance
      SecondOtherAtom->x.Scale(&BondRescale);
      //*out << Verbose(3) << "ReScaleCheck: " << FirstOtherAtom->x.Norm() << " and " << SecondOtherAtom->x.Norm() << "." << endl;
      for(int i=NDIM;i--;) { // and make relative to origin atom
        FirstOtherAtom->x.x[i] += TopOrigin->x.x[i];
        SecondOtherAtom->x.x[i] += TopOrigin->x.x[i];
      }
      // ... and add to molecule
      AllWentWell = AllWentWell && AddAtom(FirstOtherAtom);
      AllWentWell = AllWentWell && AddAtom(SecondOtherAtom);
//      *out << Verbose(4) << "Added " << *FirstOtherAtom << " at: ";
//      FirstOtherAtom->x.Output(out);
//      *out << endl;
//      *out << Verbose(4) << "Added " << *SecondOtherAtom << " at: ";
//      SecondOtherAtom->x.Output(out);
//      *out << endl;
      Binder = AddBond(BottomOrigin, FirstOtherAtom, 1);
      Binder->Cyclic = false;
      Binder->Type = TreeEdge;
      Binder = AddBond(BottomOrigin, SecondOtherAtom, 1);
      Binder->Cyclic = false;
      Binder->Type = TreeEdge;
      break;
    case 3:
      // take the "usual" tetraoidal angle and add the three Hydrogen in direction of the bond (height of the tetraoid)
      FirstOtherAtom = new atom();
      SecondOtherAtom = new atom();
      ThirdOtherAtom = new atom();
      FirstOtherAtom->type = elemente->FindElement(1);
      SecondOtherAtom->type = elemente->FindElement(1);
      ThirdOtherAtom->type = elemente->FindElement(1);
      FirstOtherAtom->v.CopyVector(&TopReplacement->v); // copy velocity
      FirstOtherAtom->FixedIon = TopReplacement->FixedIon;
      SecondOtherAtom->v.CopyVector(&TopReplacement->v); // copy velocity
      SecondOtherAtom->FixedIon = TopReplacement->FixedIon;
      ThirdOtherAtom->v.CopyVector(&TopReplacement->v); // copy velocity
      ThirdOtherAtom->FixedIon = TopReplacement->FixedIon;
      FirstOtherAtom->father = NULL;  //  we are just an added hydrogen with no father
      SecondOtherAtom->father = NULL;  //  we are just an added hydrogen with no father
      ThirdOtherAtom->father = NULL;  //  we are just an added hydrogen with no father

      // we need to vectors orthonormal the InBondvector
      AllWentWell = AllWentWell && Orthovector1.GetOneNormalVector(&InBondvector);
//      *out << Verbose(3) << "Orthovector1: ";
//      Orthovector1.Output(out);
//      *out << endl;
      AllWentWell = AllWentWell && Orthovector2.MakeNormalVector(&InBondvector, &Orthovector1);
//      *out << Verbose(3) << "Orthovector2: ";
//      Orthovector2.Output(out);
//      *out << endl;

      // create correct coordination for the three atoms
      alpha = (TopOrigin->type->HBondAngle[2])/180.*M_PI/2.;  // retrieve triple bond angle from database
      l = BondRescale;        // desired bond length
      b = 2.*l*sin(alpha);    // base length of isosceles triangle
      d = l*sqrt(cos(alpha)*cos(alpha) - sin(alpha)*sin(alpha)/3.);   // length for InBondvector
      f = b/sqrt(3.);   // length for Orthvector1
      g = b/2.;         // length for Orthvector2
//      *out << Verbose(3) << "Bond length and half-angle: " << l << ", " << alpha << "\t (b,d,f,g) = " << b << ", " << d << ", " << f << ", " << g << ", " << endl;
//      *out << Verbose(3) << "The three Bond lengths: " << sqrt(d*d+f*f) << ", " << sqrt(d*d+(-0.5*f)*(-0.5*f)+g*g) << ", "  << sqrt(d*d+(-0.5*f)*(-0.5*f)+g*g) << endl;
      factors[0] = d;
      factors[1] = f;
      factors[2] = 0.;
      FirstOtherAtom->x.LinearCombinationOfVectors(&InBondvector, &Orthovector1, &Orthovector2, factors);
      factors[1] = -0.5*f;
      factors[2] = g;
      SecondOtherAtom->x.LinearCombinationOfVectors(&InBondvector, &Orthovector1, &Orthovector2, factors);
      factors[2] = -g;
      ThirdOtherAtom->x.LinearCombinationOfVectors(&InBondvector, &Orthovector1, &Orthovector2, factors);

      // rescale each to correct BondDistance
//      FirstOtherAtom->x.Scale(&BondRescale);
//      SecondOtherAtom->x.Scale(&BondRescale);
//      ThirdOtherAtom->x.Scale(&BondRescale);

      // and relative to *origin atom
      FirstOtherAtom->x.AddVector(&TopOrigin->x);
      SecondOtherAtom->x.AddVector(&TopOrigin->x);
      ThirdOtherAtom->x.AddVector(&TopOrigin->x);

      // ... and add to molecule
      AllWentWell = AllWentWell && AddAtom(FirstOtherAtom);
      AllWentWell = AllWentWell && AddAtom(SecondOtherAtom);
      AllWentWell = AllWentWell && AddAtom(ThirdOtherAtom);
//      *out << Verbose(4) << "Added " << *FirstOtherAtom << " at: ";
//      FirstOtherAtom->x.Output(out);
//      *out << endl;
//      *out << Verbose(4) << "Added " << *SecondOtherAtom << " at: ";
//      SecondOtherAtom->x.Output(out);
//      *out << endl;
//      *out << Verbose(4) << "Added " << *ThirdOtherAtom << " at: ";
//      ThirdOtherAtom->x.Output(out);
//      *out << endl;
      Binder = AddBond(BottomOrigin, FirstOtherAtom, 1);
      Binder->Cyclic = false;
      Binder->Type = TreeEdge;
      Binder = AddBond(BottomOrigin, SecondOtherAtom, 1);
      Binder->Cyclic = false;
      Binder->Type = TreeEdge;
      Binder = AddBond(BottomOrigin, ThirdOtherAtom, 1);
      Binder->Cyclic = false;
      Binder->Type = TreeEdge;
      break;
    default:
      cerr << "ERROR: BondDegree does not state single, double or triple bond!" << endl;
      AllWentWell = false;
      break;
  }

//  *out << Verbose(3) << "End of AddHydrogenReplacementAtom." << endl;
  return AllWentWell;
};

/** Adds given atom \a *pointer from molecule list.
 * Increases molecule::last_atom and gives last number to added atom.
 * \param filename name and path of xyz file
 * \return true - succeeded, false - file not found
 */
bool molecule::AddXYZFile(string filename)
{
  istringstream *input = NULL;
  int NumberOfAtoms = 0; // atom number in xyz read
  int i, j; // loop variables
  atom *Walker = NULL;  // pointer to added atom
  char shorthand[3];  // shorthand for atom name
  ifstream xyzfile;   // xyz file
  string line;    // currently parsed line
  double x[3];    // atom coordinates

  xyzfile.open(filename.c_str());
  if (!xyzfile)
    return false;

  getline(xyzfile,line,'\n'); // Read numer of atoms in file
  input = new istringstream(line);
  *input >> NumberOfAtoms;
  cout << Verbose(0) << "Parsing " << NumberOfAtoms << " atoms in file." << endl;
  getline(xyzfile,line,'\n'); // Read comment
  cout << Verbose(1) << "Comment: " << line << endl;

  if (MDSteps == 0) // no atoms yet present
    MDSteps++;
  for(i=0;i<NumberOfAtoms;i++){
    Walker = new atom;
    getline(xyzfile,line,'\n');
    istringstream *item = new istringstream(line);
    //istringstream input(line);
    //cout << Verbose(1) << "Reading: " << line << endl;
    *item >> shorthand;
    *item >> x[0];
    *item >> x[1];
    *item >> x[2];
    Walker->type = elemente->FindElement(shorthand);
    if (Walker->type == NULL) {
      cerr << "Could not parse the element at line: '" << line << "', setting to H.";
      Walker->type = elemente->FindElement(1);
    }
    if (Trajectories[Walker].R.size() <= (unsigned int)MDSteps) {
      Trajectories[Walker].R.resize(MDSteps+10);
      Trajectories[Walker].U.resize(MDSteps+10);
      Trajectories[Walker].F.resize(MDSteps+10);
    }
    for(j=NDIM;j--;) {
      Walker->x.x[j] = x[j];
      Trajectories[Walker].R.at(MDSteps-1).x[j] = x[j];
      Trajectories[Walker].U.at(MDSteps-1).x[j] = 0;
      Trajectories[Walker].F.at(MDSteps-1).x[j] = 0;
    }
    AddAtom(Walker);  // add to molecule
    delete(item);
  }
  xyzfile.close();
  delete(input);
  return true;
};

/** Creates a copy of this molecule.
 * \return copy of molecule
 */
molecule *molecule::CopyMolecule()
{
  molecule *copy = new molecule(elemente);
  atom *CurrentAtom = NULL;
  atom *LeftAtom = NULL, *RightAtom = NULL;
  atom *Walker = NULL;

  // copy all atoms
  Walker = start;
  while(Walker->next != end) {
    Walker = Walker->next;
    CurrentAtom = copy->AddCopyAtom(Walker);
  }

  // copy all bonds
  bond *Binder = first;
  bond *NewBond = NULL;
  while(Binder->next != last) {
    Binder = Binder->next;
    // get the pendant atoms of current bond in the copy molecule
    LeftAtom = copy->start;
    while (LeftAtom->next != copy->end) {
      LeftAtom = LeftAtom->next;
      if (LeftAtom->father == Binder->leftatom)
        break;
    }
    RightAtom = copy->start;
    while (RightAtom->next != copy->end) {
      RightAtom = RightAtom->next;
      if (RightAtom->father == Binder->rightatom)
        break;
    }
    NewBond = copy->AddBond(LeftAtom, RightAtom, Binder->BondDegree);
    NewBond->Cyclic = Binder->Cyclic;
    if (Binder->Cyclic)
      copy->NoCyclicBonds++;
    NewBond->Type = Binder->Type;
  }
  // correct fathers
  Walker = copy->start;
  while(Walker->next != copy->end) {
    Walker = Walker->next;
    if (Walker->father->father == Walker->father)   // same atom in copy's father points to itself
      Walker->father = Walker;  // set father to itself (copy of a whole molecule)
    else
     Walker->father = Walker->father->father;  // set father to original's father
  }
  // copy values
  copy->CountAtoms((ofstream *)&cout);
  copy->CountElements();
  if (first->next != last) {  // if adjaceny list is present
    copy->BondDistance = BondDistance;
    copy->CreateListOfBondsPerAtom((ofstream *)&cout);
  }

  return copy;
};

/** Adds a bond to a the molecule specified by two atoms, \a *first and \a *second.
 * Also updates molecule::BondCount and molecule::NoNonBonds.
 * \param *first first atom in bond
 * \param *second atom in bond
 * \return pointer to bond or NULL on failure
 */
bond * molecule::AddBond(atom *atom1, atom *atom2, int degree=1)
{
  bond *Binder = NULL;
  if ((atom1 != NULL) && (FindAtom(atom1->nr) != NULL) && (atom2 != NULL) && (FindAtom(atom2->nr) != NULL)) {
    Binder = new bond(atom1, atom2, degree, BondCount++);
    if ((atom1->type != NULL) && (atom1->type->Z != 1) && (atom2->type != NULL) && (atom2->type->Z != 1))
      NoNonBonds++;
    add(Binder, last);
  } else {
    cerr << Verbose(1) << "ERROR: Could not add bond between " << atom1->Name << " and " << atom2->Name << " as one or both are not present in the molecule." << endl;
  }
  return Binder;
};

/** Remove bond from bond chain list.
 * \todo Function not implemented yet
 * \param *pointer bond pointer
 * \return true - bound found and removed, false - bond not found/removed
 */
bool molecule::RemoveBond(bond *pointer)
{
  //cerr << Verbose(1) << "molecule::RemoveBond: Function not implemented yet." << endl;
  removewithoutcheck(pointer);
  return true;
};

/** Remove every bond from bond chain list that atom \a *BondPartner is a constituent of.
 * \todo Function not implemented yet
 * \param *BondPartner atom to be removed
 * \return true - bounds found and removed, false - bonds not found/removed
 */
bool molecule::RemoveBonds(atom *BondPartner)
{
  cerr << Verbose(1) << "molecule::RemoveBond: Function not implemented yet." << endl;
  return false;
};

/** Set molecule::name from the basename without suffix in the given \a *filename.
 * \param *filename filename
 */
void molecule::SetNameFromFilename(const char *filename)
{
  int length = 0;
  char *molname = strrchr(filename, '/')+sizeof(char);  // search for filename without dirs
  char *endname = strchr(molname, '.');
  if ((endname == NULL) || (endname < molname))
    length = strlen(molname);
  else
    length = strlen(molname) - strlen(endname);
  strncpy(name, molname, length);
  name[length]='\0';
};

/** Sets the molecule::cell_size to the components of \a *dim (rectangular box)
 * \param *dim vector class
 */
void molecule::SetBoxDimension(Vector *dim)
{
  cell_size[0] = dim->x[0];
  cell_size[1] = 0.;
  cell_size[2] = dim->x[1];
  cell_size[3] = 0.;
  cell_size[4] = 0.;
  cell_size[5] = dim->x[2];
};

/** Centers the molecule in the box whose lengths are defined by vector \a *BoxLengths.
 * \param *out output stream for debugging
 */
bool molecule::CenterInBox(ofstream *out)
{
  bool status = true;
  Vector x;
  double *M = ReturnFullMatrixforSymmetric(cell_size);
  double *Minv = x.InverseMatrix(M);
  Vector *Center = DetermineCenterOfAll(out);

  // go through all atoms
  atom *ptr = start;  // start at first in list
  while (ptr->next != end) {  // continue with second if present
    ptr = ptr->next;
    //ptr->Output(1,1,out);
    // multiply its vector with matrix inverse
    x.CopyVector(&ptr->x);
    x.SubtractVector(Center); // now, it's centered at origin
    x.MatrixMultiplication(Minv);
    // truncate to [0,1] for each axis
    for (int i=0;i<NDIM;i++) {
      x.x[i] += 0.5;  // set to center of box
      while (x.x[i] >= 1.)
        x.x[i] -= 1.;
      while (x.x[i] < 0.)
        x.x[i] += 1.;
    }
    x.MatrixMultiplication(M);
    ptr->x.CopyVector(&x);
  }
  delete(M);
  delete(Minv);
  delete(Center);
  return status;
};


/** Bounds the molecule in the box whose lengths are defined by vector \a *BoxLengths.
 * \param *out output stream for debugging
 */
bool molecule::BoundInBox(ofstream *out)
{
  bool status = true;
  Vector x;
  double *M = ReturnFullMatrixforSymmetric(cell_size);
  double *Minv = x.InverseMatrix(M);

  // go through all atoms
  atom *ptr = start;  // start at first in list
  while (ptr->next != end) {  // continue with second if present
    ptr = ptr->next;
    //ptr->Output(1,1,out);
    // multiply its vector with matrix inverse
    x.CopyVector(&ptr->x);
    x.MatrixMultiplication(Minv);
    // truncate to [0,1] for each axis
    for (int i=0;i<NDIM;i++) {
      while (x.x[i] >= 1.)
        x.x[i] -= 1.;
      while (x.x[i] < 0.)
        x.x[i] += 1.;
    }
    x.MatrixMultiplication(M);
    ptr->x.CopyVector(&x);
  }
  delete(M);
  delete(Minv);
  return status;
};

/** Centers the edge of the atoms at (0,0,0).
 * \param *out output stream for debugging
 * \param *max coordinates of other edge, specifying box dimensions.
 */
void molecule::CenterEdge(ofstream *out, Vector *max)
{
  Vector *min = new Vector;

//  *out << Verbose(3) << "Begin of CenterEdge." << endl;
  atom *ptr = start->next;  // start at first in list
  if (ptr != end) {   //list not empty?
    for (int i=NDIM;i--;) {
      max->x[i] = ptr->x.x[i];
      min->x[i] = ptr->x.x[i];
    }
    while (ptr->next != end) {  // continue with second if present
      ptr = ptr->next;
      //ptr->Output(1,1,out);
      for (int i=NDIM;i--;) {
        max->x[i] = (max->x[i] < ptr->x.x[i]) ? ptr->x.x[i] : max->x[i];
        min->x[i] = (min->x[i] > ptr->x.x[i]) ? ptr->x.x[i] : min->x[i];
      }
    }
//    *out << Verbose(4) << "Maximum is ";
//    max->Output(out);
//    *out << ", Minimum is ";
//    min->Output(out);
//    *out << endl;
    min->Scale(-1.);
    max->AddVector(min);
    Translate(min);
    Center.Zero();
  }
  delete(min);
//  *out << Verbose(3) << "End of CenterEdge." << endl;
};

/** Centers the center of the atoms at (0,0,0).
 * \param *out output stream for debugging
 * \param *center return vector for translation vector
 */
void molecule::CenterOrigin(ofstream *out)
{
  int Num = 0;
  atom *ptr = start->next;  // start at first in list

  Center.Zero();

  if (ptr != end) {   //list not empty?
    while (ptr->next != end) {  // continue with second if present
      ptr = ptr->next;
      Num++;
      Center.AddVector(&ptr->x);
    }
    Center.Scale(-1./Num); // divide through total number (and sign for direction)
    Translate(&Center);
    Center.Zero();
  }
};

/** Returns vector pointing to center of all atoms.
 * \param *out output stream for debugging
 * \return pointer to center of all vector
 */
Vector * molecule::DetermineCenterOfAll(ofstream *out)
{
  atom *ptr = start->next;  // start at first in list
  Vector *a = new Vector();
  Vector tmp;
  double Num = 0;

  a->Zero();

  if (ptr != end) {   //list not empty?
    while (ptr->next != end) {  // continue with second if present
      ptr = ptr->next;
      Num += 1.;
      tmp.CopyVector(&ptr->x);
      a->AddVector(&tmp);
    }
    a->Scale(1./Num); // divide through total mass (and sign for direction)
  }
  //cout << Verbose(1) << "Resulting center of gravity: ";
  //a->Output(out);
  //cout << endl;
  return a;
};

/** Returns vector pointing to center of gravity.
 * \param *out output stream for debugging
 * \return pointer to center of gravity vector
 */
Vector * molecule::DetermineCenterOfGravity(ofstream *out)
{
  atom *ptr = start->next;  // start at first in list
  Vector *a = new Vector();
  Vector tmp;
  double Num = 0;

  a->Zero();

  if (ptr != end) {   //list not empty?
    while (ptr->next != end) {  // continue with second if present
      ptr = ptr->next;
      Num += ptr->type->mass;
      tmp.CopyVector(&ptr->x);
      tmp.Scale(ptr->type->mass);  // scale by mass
      a->AddVector(&tmp);
    }
    a->Scale(-1./Num); // divide through total mass (and sign for direction)
  }
//  *out << Verbose(1) << "Resulting center of gravity: ";
//  a->Output(out);
//  *out << endl;
  return a;
};

/** Centers the center of gravity of the atoms at (0,0,0).
 * \param *out output stream for debugging
 * \param *center return vector for translation vector
 */
void molecule::CenterPeriodic(ofstream *out)
{
  DeterminePeriodicCenter(Center);
};


/** Centers the center of gravity of the atoms at (0,0,0).
 * \param *out output stream for debugging
 * \param *center return vector for translation vector
 */
void molecule::CenterAtVector(ofstream *out, Vector *newcenter)
{
  Center.CopyVector(newcenter);
};


/** Scales all atoms by \a *factor.
 * \param *factor pointer to scaling factor
 */
void molecule::Scale(double **factor)
{
  atom *ptr = start;

  while (ptr->next != end) {
    ptr = ptr->next;
    for (int j=0;j<MDSteps;j++)
      Trajectories[ptr].R.at(j).Scale(factor);
    ptr->x.Scale(factor);
  }
};

/** Translate all atoms by given vector.
 * \param trans[] translation vector.
 */
void molecule::Translate(const Vector *trans)
{
  atom *ptr = start;

  while (ptr->next != end) {
    ptr = ptr->next;
    for (int j=0;j<MDSteps;j++)
      Trajectories[ptr].R.at(j).Translate(trans);
    ptr->x.Translate(trans);
  }
};

/** Translate the molecule periodically in the box.
 * \param trans[] translation vector.
 */
void molecule::TranslatePeriodically(const Vector *trans)
{
  atom *ptr = NULL;
  Vector x;
  double *M = ReturnFullMatrixforSymmetric(cell_size);
  double *Minv = x.InverseMatrix(M);
  double value;

  // go through all atoms
  ptr = start->next;  // start at first in list
  while (ptr != end) {  // continue with second if present
    //ptr->Output(1,1,out);
    // multiply its vector with matrix inverse
    x.CopyVector(&ptr->x);
    x.Translate(trans);
    x.MatrixMultiplication(Minv);
    // truncate to [0,1] for each axis
    for (int i=0;i<NDIM;i++) {
      value = floor(fabs(x.x[i]));  // next lower integer
      if (x.x[i] >=0) {
        x.x[i] -= value;
      } else {
        x.x[i] += value+1;
      }
    }
    // matrix multiply
    x.MatrixMultiplication(M);
    ptr->x.CopyVector(&x);
    for (int j=0;j<MDSteps;j++) {
      x.CopyVector(&Trajectories[ptr].R.at(j));
      x.Translate(trans);
      x.MatrixMultiplication(Minv);
      // truncate to [0,1] for each axis
      for (int i=0;i<NDIM;i++) {
        value = floor(x.x[i]);  // next lower integer
        if (x.x[i] >=0) {
          x.x[i] -= value;
        } else {
          x.x[i] += value+1;
        }
      }
      // matrix multiply
      x.MatrixMultiplication(M);
      Trajectories[ptr].R.at(j).CopyVector(&x);
    }
    ptr = ptr->next;
  }
  delete(M);
  delete(Minv);
};


/** Mirrors all atoms against a given plane.
 * \param n[] normal vector of mirror plane.
 */
void molecule::Mirror(const Vector *n)
{
  atom *ptr = start;

  while (ptr->next != end) {
    ptr = ptr->next;
    for (int j=0;j<MDSteps;j++)
      Trajectories[ptr].R.at(j).Mirror(n);
    ptr->x.Mirror(n);
  }
};

/** Determines center of molecule (yet not considering atom masses).
 * \param center reference to return vector
 */
void molecule::DeterminePeriodicCenter(Vector &center)
{
  atom *Walker = start;
  bond *Binder = NULL;
  double *matrix = ReturnFullMatrixforSymmetric(cell_size);
  double tmp;
  bool flag;
  Vector Testvector, Translationvector;

  do {
    Center.Zero();
    flag = true;
    while (Walker->next != end) {
      Walker = Walker->next;
#ifdef ADDHYDROGEN
      if (Walker->type->Z != 1) {
#endif
        Testvector.CopyVector(&Walker->x);
        Testvector.InverseMatrixMultiplication(matrix);
        Translationvector.Zero();
        for (int i=0;i<NumberOfBondsPerAtom[Walker->nr]; i++) {
          Binder = ListOfBondsPerAtom[Walker->nr][i];
          if (Walker->nr < Binder->GetOtherAtom(Walker)->nr) // otherwise we shift one to, the other fro and gain nothing
            for (int j=0;j<NDIM;j++) {
              tmp = Walker->x.x[j] - Binder->GetOtherAtom(Walker)->x.x[j];
              if ((fabs(tmp)) > BondDistance) {
                flag = false;
                cout << Verbose(0) << "Hit: atom " << Walker->Name << " in bond " << *Binder << " has to be shifted due to " << tmp << "." << endl;
                if (tmp > 0)
                  Translationvector.x[j] -= 1.;
                else
                  Translationvector.x[j] += 1.;
              }
            }
        }
        Testvector.AddVector(&Translationvector);
        Testvector.MatrixMultiplication(matrix);
        Center.AddVector(&Testvector);
        cout << Verbose(1) << "vector is: ";
        Testvector.Output((ofstream *)&cout);
        cout << endl;
#ifdef ADDHYDROGEN
        // now also change all hydrogens
        for (int i=0;i<NumberOfBondsPerAtom[Walker->nr]; i++) {
          Binder = ListOfBondsPerAtom[Walker->nr][i];
          if (Binder->GetOtherAtom(Walker)->type->Z == 1) {
            Testvector.CopyVector(&Binder->GetOtherAtom(Walker)->x);
            Testvector.InverseMatrixMultiplication(matrix);
            Testvector.AddVector(&Translationvector);
            Testvector.MatrixMultiplication(matrix);
            Center.AddVector(&Testvector);
            cout << Verbose(1) << "Hydrogen vector is: ";
            Testvector.Output((ofstream *)&cout);
            cout << endl;
          }
        }
      }
#endif
    }
  } while (!flag);
  Free((void **)&matrix, "molecule::DetermineCenter: *matrix");
  Center.Scale(1./(double)AtomCount);
};

/** Transforms/Rotates the given molecule into its principal axis system.
 * \param *out output stream for debugging
 * \param DoRotate whether to rotate (true) or only to determine the PAS.
 */
void molecule::PrincipalAxisSystem(ofstream *out, bool DoRotate)
{
  atom *ptr = start;  // start at first in list
  double InertiaTensor[NDIM*NDIM];
  Vector *CenterOfGravity = DetermineCenterOfGravity(out);

  CenterPeriodic(out);

  // reset inertia tensor
  for(int i=0;i<NDIM*NDIM;i++)
    InertiaTensor[i] = 0.;

  // sum up inertia tensor
  while (ptr->next != end) {
    ptr = ptr->next;
    Vector x;
    x.CopyVector(&ptr->x);
    //x.SubtractVector(CenterOfGravity);
    InertiaTensor[0] += ptr->type->mass*(x.x[1]*x.x[1] + x.x[2]*x.x[2]);
    InertiaTensor[1] += ptr->type->mass*(-x.x[0]*x.x[1]);
    InertiaTensor[2] += ptr->type->mass*(-x.x[0]*x.x[2]);
    InertiaTensor[3] += ptr->type->mass*(-x.x[1]*x.x[0]);
    InertiaTensor[4] += ptr->type->mass*(x.x[0]*x.x[0] + x.x[2]*x.x[2]);
    InertiaTensor[5] += ptr->type->mass*(-x.x[1]*x.x[2]);
    InertiaTensor[6] += ptr->type->mass*(-x.x[2]*x.x[0]);
    InertiaTensor[7] += ptr->type->mass*(-x.x[2]*x.x[1]);
    InertiaTensor[8] += ptr->type->mass*(x.x[0]*x.x[0] + x.x[1]*x.x[1]);
  }
  // print InertiaTensor for debugging
  *out << "The inertia tensor is:" << endl;
  for(int i=0;i<NDIM;i++) {
    for(int j=0;j<NDIM;j++)
      *out << InertiaTensor[i*NDIM+j] << " ";
    *out << endl;
  }
  *out << endl;

  // diagonalize to determine principal axis system
  gsl_eigen_symmv_workspace *T = gsl_eigen_symmv_alloc(NDIM);
  gsl_matrix_view m = gsl_matrix_view_array(InertiaTensor, NDIM, NDIM);
  gsl_vector *eval = gsl_vector_alloc(NDIM);
  gsl_matrix *evec = gsl_matrix_alloc(NDIM, NDIM);
  gsl_eigen_symmv(&m.matrix, eval, evec, T);
  gsl_eigen_symmv_free(T);
  gsl_eigen_symmv_sort(eval, evec, GSL_EIGEN_SORT_ABS_DESC);

  for(int i=0;i<NDIM;i++) {
    *out << Verbose(1) << "eigenvalue = " << gsl_vector_get(eval, i);
    *out << ", eigenvector = (" << evec->data[i * evec->tda + 0] << "," << evec->data[i * evec->tda + 1] << "," << evec->data[i * evec->tda + 2] << ")" << endl;
  }

  // check whether we rotate or not
  if (DoRotate) {
    *out << Verbose(1) << "Transforming molecule into PAS ... ";
    // the eigenvectors specify the transformation matrix
    ptr = start;
    while (ptr->next != end) {
      ptr = ptr->next;
      for (int j=0;j<MDSteps;j++)
        Trajectories[ptr].R.at(j).MatrixMultiplication(evec->data);
      ptr->x.MatrixMultiplication(evec->data);
    }
    *out << "done." << endl;

    // summing anew for debugging (resulting matrix has to be diagonal!)
    // reset inertia tensor
    for(int i=0;i<NDIM*NDIM;i++)
      InertiaTensor[i] = 0.;

    // sum up inertia tensor
    ptr = start;
    while (ptr->next != end) {
      ptr = ptr->next;
      Vector x;
      x.CopyVector(&ptr->x);
      //x.SubtractVector(CenterOfGravity);
      InertiaTensor[0] += ptr->type->mass*(x.x[1]*x.x[1] + x.x[2]*x.x[2]);
      InertiaTensor[1] += ptr->type->mass*(-x.x[0]*x.x[1]);
      InertiaTensor[2] += ptr->type->mass*(-x.x[0]*x.x[2]);
      InertiaTensor[3] += ptr->type->mass*(-x.x[1]*x.x[0]);
      InertiaTensor[4] += ptr->type->mass*(x.x[0]*x.x[0] + x.x[2]*x.x[2]);
      InertiaTensor[5] += ptr->type->mass*(-x.x[1]*x.x[2]);
      InertiaTensor[6] += ptr->type->mass*(-x.x[2]*x.x[0]);
      InertiaTensor[7] += ptr->type->mass*(-x.x[2]*x.x[1]);
      InertiaTensor[8] += ptr->type->mass*(x.x[0]*x.x[0] + x.x[1]*x.x[1]);
    }
    // print InertiaTensor for debugging
    *out << "The inertia tensor is:" << endl;
    for(int i=0;i<NDIM;i++) {
      for(int j=0;j<NDIM;j++)
        *out << InertiaTensor[i*NDIM+j] << " ";
      *out << endl;
    }
    *out << endl;
  }

  // free everything
  delete(CenterOfGravity);
  gsl_vector_free(eval);
  gsl_matrix_free(evec);
};

/** Evaluates the potential energy used for constrained molecular dynamics.
 * \f$V_i^{con} = c^{bond} \cdot | r_{P(i)} - R_i | + sum_{i \neq j} C^{min} \cdot \frac{1}{C_{ij}} + C^{inj} \Bigl (1 - \theta \bigl (\prod_{i \neq j} (P(i) - P(j)) \bigr ) \Bigr )\f$
 *     where the first term points to the target in minimum distance, the second is a penalty for trajectories lying too close to each other (\f$C_{ij}$ is minimum distance between 
 *     trajectories i and j) and the third term is a penalty for two atoms trying to each the same target point.
 * Note that for the second term we have to solve the following linear system:
 * \f$-c_1 \cdot n_1 + c_2 \cdot n_2 + C \cdot n_3 = - p_2 + p_1\f$, where \f$c_1\f$, \f$c_2\f$ and \f$C\f$ are constants, 
 * offset vector \f$p_1\f$ in direction \f$n_1\f$, offset vector \f$p_2\f$ in direction \f$n_2\f$,
 * \f$n_3\f$ is the normal vector to both directions. \f$C\f$ would be the minimum distance between the two lines.
 * \sa molecule::MinimiseConstrainedPotential(), molecule::VerletForceIntegration()
 * \param *out output stream for debugging
 * \param *PermutationMap gives target ptr for each atom, array of size molecule::AtomCount (this is "x" in \f$ V^{con}(x) \f$ )
 * \param startstep start configuration (MDStep in molecule::trajectories)
 * \param endstep end configuration (MDStep in molecule::trajectories)
 * \param *constants constant in front of each term
 * \param IsAngstroem whether coordinates are in angstroem (true) or bohrradius (false)
 * \return potential energy
 * \note This routine is scaling quadratically which is not optimal.
 * \todo There's a bit double counting going on for the first time, bu nothing to worry really about.
 */
double molecule::ConstrainedPotential(ofstream *out, atom **PermutationMap, int startstep, int endstep, double *constants, bool IsAngstroem)
{
  double result = 0., tmp, Norm1, Norm2;
  atom *Walker = NULL, *Runner = NULL, *Sprinter = NULL;
  Vector trajectory1, trajectory2, normal, TestVector;
  gsl_matrix *A = gsl_matrix_alloc(NDIM,NDIM);
  gsl_vector *x = gsl_vector_alloc(NDIM);

  // go through every atom
  Walker = start;
  while (Walker->next != end) {
    Walker = Walker->next;
    // first term: distance to target
    Runner = PermutationMap[Walker->nr];   // find target point
    tmp = (Trajectories[Walker].R.at(startstep).Distance(&Trajectories[Runner].R.at(endstep)));
    tmp *= IsAngstroem ? 1. : 1./AtomicLengthToAngstroem;
    result += constants[0] * tmp;
    //*out << Verbose(4) << "Adding " << tmp*constants[0] << "." << endl;
    
    // second term: sum of distances to other trajectories
    Runner = start;
    while (Runner->next != end) {
      Runner = Runner->next;
      if (Runner == Walker) // hence, we only go up to the Walker, not beyond (similar to i=0; i<j; i++)
        break;
      // determine normalized trajectories direction vector (n1, n2)
      Sprinter = PermutationMap[Walker->nr];   // find first target point
      trajectory1.CopyVector(&Trajectories[Sprinter].R.at(endstep));
      trajectory1.SubtractVector(&Trajectories[Walker].R.at(startstep));
      trajectory1.Normalize();
      Norm1 = trajectory1.Norm();
      Sprinter = PermutationMap[Runner->nr];   // find second target point
      trajectory2.CopyVector(&Trajectories[Sprinter].R.at(endstep));
      trajectory2.SubtractVector(&Trajectories[Runner].R.at(startstep));
      trajectory2.Normalize();
      Norm2 = trajectory1.Norm();
      // check whether either is zero()
      if ((Norm1 < MYEPSILON) && (Norm2 < MYEPSILON)) {
        tmp = Trajectories[Walker].R.at(startstep).Distance(&Trajectories[Runner].R.at(startstep));
      } else if (Norm1 < MYEPSILON) {
        Sprinter = PermutationMap[Walker->nr];   // find first target point
        trajectory1.CopyVector(&Trajectories[Sprinter].R.at(endstep));  // copy first offset
        trajectory1.SubtractVector(&Trajectories[Runner].R.at(startstep));  // subtract second offset
        trajectory2.Scale( trajectory1.ScalarProduct(&trajectory2) ); // trajectory2 is scaled to unity, hence we don't need to divide by anything 
        trajectory1.SubtractVector(&trajectory2);   // project the part in norm direction away
        tmp = trajectory1.Norm();  // remaining norm is distance
      } else if (Norm2 < MYEPSILON) {
        Sprinter = PermutationMap[Runner->nr];   // find second target point
        trajectory2.CopyVector(&Trajectories[Sprinter].R.at(endstep));  // copy second offset
        trajectory2.SubtractVector(&Trajectories[Walker].R.at(startstep));  // subtract first offset
        trajectory1.Scale( trajectory2.ScalarProduct(&trajectory1) ); // trajectory1 is scaled to unity, hence we don't need to divide by anything 
        trajectory2.SubtractVector(&trajectory1);   // project the part in norm direction away
        tmp = trajectory2.Norm();  // remaining norm is distance
      } else if ((fabs(trajectory1.ScalarProduct(&trajectory2)/Norm1/Norm2) - 1.) < MYEPSILON) { // check whether they're linear dependent
//        *out << Verbose(3) << "Both trajectories of " << *Walker << " and " << *Runner << " are linear dependent: ";
//        *out << trajectory1;
//        *out << " and ";
//        *out << trajectory2;
        tmp = Trajectories[Walker].R.at(startstep).Distance(&Trajectories[Runner].R.at(startstep));
//        *out << " with distance " << tmp << "." << endl;
      } else { // determine distance by finding minimum distance
//        *out << Verbose(3) << "Both trajectories of " << *Walker << " and " << *Runner << " are linear independent ";
//        *out << endl;
//        *out << "First Trajectory: ";
//        *out << trajectory1 << endl;
//        *out << "Second Trajectory: ";
//        *out << trajectory2 << endl;
        // determine normal vector for both
        normal.MakeNormalVector(&trajectory1, &trajectory2);
        // print all vectors for debugging
//        *out << "Normal vector in between: ";
//        *out << normal << endl;
        // setup matrix
        for (int i=NDIM;i--;) {
          gsl_matrix_set(A, 0, i, trajectory1.x[i]);
          gsl_matrix_set(A, 1, i, trajectory2.x[i]);
          gsl_matrix_set(A, 2, i, normal.x[i]);
          gsl_vector_set(x,i, (Trajectories[Walker].R.at(startstep).x[i] - Trajectories[Runner].R.at(startstep).x[i]));
        }
        // solve the linear system by Householder transformations
        gsl_linalg_HH_svx(A, x);
        // distance from last component
        tmp = gsl_vector_get(x,2);
//        *out << " with distance " << tmp << "." << endl;
        // test whether we really have the intersection (by checking on c_1 and c_2)
        TestVector.CopyVector(&Trajectories[Runner].R.at(startstep));
        trajectory2.Scale(gsl_vector_get(x,1));
        TestVector.AddVector(&trajectory2);
        normal.Scale(gsl_vector_get(x,2));
        TestVector.AddVector(&normal);
        TestVector.SubtractVector(&Trajectories[Walker].R.at(startstep));
        trajectory1.Scale(gsl_vector_get(x,0));
        TestVector.SubtractVector(&trajectory1);
        if (TestVector.Norm() < MYEPSILON) {
//          *out << Verbose(2) << "Test: ok.\tDistance of " << tmp << " is correct." << endl;  
        } else {
//          *out << Verbose(2) << "Test: failed.\tIntersection is off by ";
//          *out << TestVector;
//          *out << "." << endl;  
        }
      }
      // add up
      tmp *= IsAngstroem ? 1. : 1./AtomicLengthToAngstroem;
      if (fabs(tmp) > MYEPSILON) {
        result += constants[1] * 1./tmp;
        //*out << Verbose(4) << "Adding " << 1./tmp*constants[1] << "." << endl;
      }
    }
      
    // third term: penalty for equal targets
    Runner = start;
    while (Runner->next != end) {
      Runner = Runner->next;
      if ((PermutationMap[Walker->nr] == PermutationMap[Runner->nr]) && (Walker->nr < Runner->nr)) {
        Sprinter = PermutationMap[Walker->nr];
//        *out << *Walker << " and " << *Runner << " are heading to the same target at ";
//        *out << Trajectories[Sprinter].R.at(endstep);
//        *out << ", penalting." << endl;
        result += constants[2];
        //*out << Verbose(4) << "Adding " << constants[2] << "." << endl;
      }
    }
  }
  
  return result;
};

void PrintPermutationMap(ofstream *out, atom **PermutationMap, int Nr) 
{
  stringstream zeile1, zeile2;
  int *DoubleList = (int *) Malloc(Nr*sizeof(int), "PrintPermutationMap: *DoubleList");
  int doubles = 0;
  for (int i=0;i<Nr;i++)
    DoubleList[i] = 0;
  zeile1 << "PermutationMap: ";
  zeile2 << "                ";
  for (int i=0;i<Nr;i++) {
    DoubleList[PermutationMap[i]->nr]++;
    zeile1 << i << " ";
    zeile2 << PermutationMap[i]->nr << " ";
  }
  for (int i=0;i<Nr;i++)
    if (DoubleList[i] > 1)
    doubles++;
 // *out << "Found " << doubles << " Doubles." << endl;
  Free((void **)&DoubleList, "PrintPermutationMap: *DoubleList");
//  *out << zeile1.str() << endl << zeile2.str() << endl;
};

/** Minimises the extra potential for constrained molecular dynamics and gives forces and the constrained potential energy.
 * We do the following:
 *  -# Generate a distance list from all source to all target points
 *  -# Sort this per source point
 *  -# Take for each source point the target point with minimum distance, use this as initial permutation
 *  -# check whether molecule::ConstrainedPotential() is greater than injective penalty
 *     -# If so, we go through each source point, stepping down in the sorted target point distance list and re-checking potential.
 *  -# Next, we only apply transformations that keep the injectivity of the permutations list.
 *  -# Hence, for one source point we step down the ladder and seek the corresponding owner of this new target 
 *     point and try to change it for one with lesser distance, or for the next one with greater distance, but only
 *     if this decreases the conditional potential.
 *  -# finished. 
 *  -# Then, we calculate the forces by taking the spatial derivative, where we scale the potential to such a degree,
 *     that the total force is always pointing in direction of the constraint force (ensuring that we move in the
 *     right direction).
 *  -# Finally, we calculate the potential energy and return.
 * \param *out output stream for debugging
 * \param **PermutationMap on return: mapping between the atom label of the initial and the final configuration
 * \param startstep current MD step giving initial position between which and \a endstep we perform the constrained MD (as further steps are always concatenated)
 * \param endstep step giving final position in constrained MD 
 * \param IsAngstroem whether coordinates are in angstroem (true) or bohrradius (false)
 * \sa molecule::VerletForceIntegration()
 * \return potential energy (and allocated **PermutationMap (array of molecule::AtomCount ^2)
 * \todo The constrained potential's constants are set to fixed values right now, but they should scale based on checks of the system in order
 *       to ensure they're properties (e.g. constants[2] always greater than the energy of the system).
 * \bug this all is not O(N log N) but O(N^2)
 */
double molecule::MinimiseConstrainedPotential(ofstream *out, atom **&PermutationMap, int startstep, int endstep, bool IsAngstroem)
{
  double Potential, OldPotential, OlderPotential;
  PermutationMap = (atom **) Malloc(AtomCount*sizeof(atom *), "molecule::MinimiseConstrainedPotential: **PermutationMap");
  DistanceMap **DistanceList = (DistanceMap **) Malloc(AtomCount*sizeof(DistanceMap *), "molecule::MinimiseConstrainedPotential: **DistanceList");
  DistanceMap::iterator *DistanceIterators = (DistanceMap::iterator *) Malloc(AtomCount*sizeof(DistanceMap::iterator), "molecule::MinimiseConstrainedPotential: *DistanceIterators");
  int *DoubleList = (int *) Malloc(AtomCount*sizeof(int), "molecule::MinimiseConstrainedPotential: *DoubleList");
  DistanceMap::iterator *StepList = (DistanceMap::iterator *) Malloc(AtomCount*sizeof(DistanceMap::iterator), "molecule::MinimiseConstrainedPotential: *StepList");
  double constants[3];
  int round;
  atom *Walker = NULL, *Runner = NULL, *Sprinter = NULL;
  DistanceMap::iterator Rider, Strider;
  
  /// Minimise the potential
  // set Lagrange multiplier constants
  constants[0] = 10.;
  constants[1] = 1.;
  constants[2] = 1e+7;    // just a huge penalty
  // generate the distance list
  *out << Verbose(1) << "Creating the distance list ... " << endl;
  for (int i=AtomCount; i--;) {
    DoubleList[i] = 0;  // stores for how many atoms in startstep this atom is a target in endstep
    DistanceList[i] = new DistanceMap;    // is the distance sorted target list per atom
    DistanceList[i]->clear();
  }
  *out << Verbose(1) << "Filling the distance list ... " << endl;
  Walker = start;
  while (Walker->next != end) {
    Walker = Walker->next;
    Runner = start;
    while(Runner->next != end) {
      Runner = Runner->next;
      DistanceList[Walker->nr]->insert( DistancePair(Trajectories[Walker].R.at(startstep).Distance(&Trajectories[Runner].R.at(endstep)), Runner) );
    }
  }
  // create the initial PermutationMap (source -> target)
  Walker = start;
  while (Walker->next != end) {
    Walker = Walker->next;
    StepList[Walker->nr] = DistanceList[Walker->nr]->begin();    // stores the step to the next iterator that could be a possible next target
    PermutationMap[Walker->nr] = DistanceList[Walker->nr]->begin()->second;   // always pick target with the smallest distance
    DoubleList[DistanceList[Walker->nr]->begin()->second->nr]++;            // increase this target's source count (>1? not injective)
    DistanceIterators[Walker->nr] = DistanceList[Walker->nr]->begin();    // and remember which one we picked
    *out << *Walker << " starts with distance " << DistanceList[Walker->nr]->begin()->first << "." << endl;
  }
  *out << Verbose(1) << "done." << endl;
  // make the PermutationMap injective by checking whether we have a non-zero constants[2] term in it
  *out << Verbose(1) << "Making the PermutationMap injective ... " << endl;
  Walker = start;
  DistanceMap::iterator NewBase;
  OldPotential = fabs(ConstrainedPotential(out, PermutationMap, startstep, endstep, constants, IsAngstroem));
  while ((OldPotential) > constants[2]) {
    PrintPermutationMap(out, PermutationMap, AtomCount);
    Walker = Walker->next;
    if (Walker == end) // round-robin at the end
      Walker = start->next;
    if (DoubleList[DistanceIterators[Walker->nr]->second->nr] <= 1)  // no need to make those injective that aren't
      continue;
    // now, try finding a new one
    NewBase = DistanceIterators[Walker->nr];  // store old base
    do {
      NewBase++;  // take next further distance in distance to targets list that's a target of no one
    } while ((DoubleList[NewBase->second->nr] != 0) && (NewBase != DistanceList[Walker->nr]->end()));
    if (NewBase != DistanceList[Walker->nr]->end()) {
      PermutationMap[Walker->nr] = NewBase->second;
      Potential = fabs(ConstrainedPotential(out, PermutationMap, startstep, endstep, constants, IsAngstroem));
      if (Potential > OldPotential) { // undo
        PermutationMap[Walker->nr] = DistanceIterators[Walker->nr]->second;
      } else {  // do
        DoubleList[DistanceIterators[Walker->nr]->second->nr]--;  // decrease the old entry in the doubles list
        DoubleList[NewBase->second->nr]++;    // increase the old entry in the doubles list
        DistanceIterators[Walker->nr] = NewBase;
        OldPotential = Potential;
        *out << Verbose(3) << "Found a new permutation, new potential is " << OldPotential << "." << endl;
      }
    }
  } 
  for (int i=AtomCount; i--;) // now each single entry in the DoubleList should be <=1
    if (DoubleList[i] > 1) { 
      cerr << "Failed to create an injective PermutationMap!" << endl;
      exit(1);
    }
  *out << Verbose(1) << "done." << endl;
  Free((void **)&DoubleList, "molecule::MinimiseConstrainedPotential: *DoubleList");
  // argument minimise the constrained potential in this injective PermutationMap
  *out << Verbose(1) << "Argument minimising the PermutationMap, at current potential " << OldPotential << " ... " << endl;
  OldPotential = 1e+10;
  round = 0;
  do {
    *out << "Starting round " << ++round << " ... " << endl;
    OlderPotential = OldPotential;
    do {
      Walker = start;
      while (Walker->next != end) { // pick one
        Walker = Walker->next;
        PrintPermutationMap(out, PermutationMap, AtomCount);
        Sprinter = DistanceIterators[Walker->nr]->second;   // store initial partner
        Strider = DistanceIterators[Walker->nr];  //remember old iterator
        DistanceIterators[Walker->nr] = StepList[Walker->nr];  
        if (DistanceIterators[Walker->nr] == DistanceList[Walker->nr]->end()) {// stop, before we run through the list and still on
          DistanceIterators[Walker->nr] == DistanceList[Walker->nr]->begin();
          break;
        }
        //*out << Verbose(2) << "Current Walker: " << *Walker << " with old/next candidate " << *Sprinter << "/" << *DistanceIterators[Walker->nr]->second << "." << endl;
        // find source of the new target
        Runner = start->next;
        while(Runner != end) { // find the source whose toes we might be stepping on (Walker's new target should be in use by another already)
          if (PermutationMap[Runner->nr] == DistanceIterators[Walker->nr]->second) {
            //*out << Verbose(2) << "Found the corresponding owner " << *Runner << " to " << *PermutationMap[Runner->nr] << "." << endl;
            break;
          }
          Runner = Runner->next;
        }
        if (Runner != end) { // we found the other source
          // then look in its distance list for Sprinter
          Rider = DistanceList[Runner->nr]->begin();
          for (; Rider != DistanceList[Runner->nr]->end(); Rider++)
            if (Rider->second == Sprinter)
              break;
          if (Rider != DistanceList[Runner->nr]->end()) { // if we have found one
            //*out << Verbose(2) << "Current Other: " << *Runner << " with old/next candidate " << *PermutationMap[Runner->nr] << "/" << *Rider->second << "." << endl; 
            // exchange both 
            PermutationMap[Walker->nr] = DistanceIterators[Walker->nr]->second; // put next farther distance into PermutationMap 
            PermutationMap[Runner->nr] = Sprinter;  // and hand the old target to its respective owner
            PrintPermutationMap(out, PermutationMap, AtomCount);
            // calculate the new potential
            //*out << Verbose(2) << "Checking new potential ..." << endl;
            Potential = ConstrainedPotential(out, PermutationMap, startstep, endstep, constants, IsAngstroem);
            if (Potential > OldPotential) { // we made everything worse! Undo ...
              //*out << Verbose(3) << "Nay, made the potential worse: " << Potential << " vs. " << OldPotential << "!" << endl;
              //*out << Verbose(3) << "Setting " << *Runner << "'s source to " << *DistanceIterators[Runner->nr]->second << "." << endl; 
              // Undo for Runner (note, we haven't moved the iteration yet, we may use this)
              PermutationMap[Runner->nr] = DistanceIterators[Runner->nr]->second;
              // Undo for Walker
              DistanceIterators[Walker->nr] = Strider;  // take next farther distance target
              //*out << Verbose(3) << "Setting " << *Walker << "'s source to " << *DistanceIterators[Walker->nr]->second << "." << endl; 
              PermutationMap[Walker->nr] = DistanceIterators[Walker->nr]->second;
            } else {
              DistanceIterators[Runner->nr] = Rider;  // if successful also move the pointer in the iterator list
              *out << Verbose(3) << "Found a better permutation, new potential is " << Potential << " vs." << OldPotential << "." << endl;
              OldPotential = Potential;
            }
            if (Potential > constants[2]) {
              cerr << "ERROR: The two-step permutation procedure did not maintain injectivity!" << endl;
              exit(255);
            }
            //*out << endl;
          } else {
            cerr << "ERROR: " << *Runner << " was not the owner of " << *Sprinter << "!" << endl;
            exit(255);
          }
        } else {
          PermutationMap[Walker->nr] = DistanceIterators[Walker->nr]->second; // new target has no source!
        }
        StepList[Walker->nr]++; // take next farther distance target
      }
    } while (Walker->next != end);
  } while ((OlderPotential - OldPotential) > 1e-3);
  *out << Verbose(1) << "done." << endl;

  
  /// free memory and return with evaluated potential 
  for (int i=AtomCount; i--;)
    DistanceList[i]->clear();
  Free((void **)&DistanceList, "molecule::MinimiseConstrainedPotential: **DistanceList");
  Free((void **)&DistanceIterators, "molecule::MinimiseConstrainedPotential: *DistanceIterators");
  return ConstrainedPotential(out, PermutationMap, startstep, endstep, constants, IsAngstroem);
};

/** Evaluates the (distance-related part) of the constrained potential for the constrained forces.
 * \param *out output stream for debugging
 * \param startstep current MD step giving initial position between which and \a endstep we perform the constrained MD (as further steps are always concatenated)
 * \param endstep step giving final position in constrained MD 
 * \param **PermutationMap mapping between the atom label of the initial and the final configuration
 * \param *Force ForceMatrix containing force vectors from the external energy functional minimisation.
 * \todo the constant for the constrained potential distance part is hard-coded independently of the hard-coded value in MinimiseConstrainedPotential()
 */
void molecule::EvaluateConstrainedForces(ofstream *out, int startstep, int endstep, atom **PermutationMap, ForceMatrix *Force)
{
  double constant = 10.;
  atom *Walker = NULL, *Sprinter = NULL; 
  
  /// evaluate forces (only the distance to target dependent part) with the final PermutationMap
  *out << Verbose(1) << "Calculating forces and adding onto ForceMatrix ... " << endl;
  Walker = start;
  while (Walker->next != NULL) {
    Walker = Walker->next;
    Sprinter = PermutationMap[Walker->nr];
    // set forces
    for (int i=NDIM;i++;)
      Force->Matrix[0][Walker->nr][5+i] += 2.*constant*sqrt(Trajectories[Walker].R.at(startstep).Distance(&Trajectories[Sprinter].R.at(endstep)));
  }  
  *out << Verbose(1) << "done." << endl;
};

/** Performs a linear interpolation between two desired atomic configurations with a given number of steps.
 * Note, step number is config::MaxOuterStep
 * \param *out output stream for debugging
 * \param startstep stating initial configuration in molecule::Trajectories
 * \param endstep stating final configuration in molecule::Trajectories
 * \param &config configuration structure
 * \return true - success in writing step files, false - error writing files or only one step in molecule::Trajectories
 */
bool molecule::LinearInterpolationBetweenConfiguration(ofstream *out, int startstep, int endstep, const char *prefix, config &configuration) 
{
  molecule *mol = NULL;
  bool status = true;
  int MaxSteps = configuration.MaxOuterStep; 
  MoleculeListClass *MoleculePerStep = new MoleculeListClass();
  // Get the Permutation Map by MinimiseConstrainedPotential
  atom **PermutationMap = NULL;
  atom *Walker = NULL, *Sprinter = NULL;
  MinimiseConstrainedPotential(out, PermutationMap, startstep, endstep, configuration.GetIsAngstroem());

  // check whether we have sufficient space in Trajectories for each atom
  Walker = start;
  while (Walker->next != end) {
    Walker = Walker->next;
    if (Trajectories[Walker].R.size() <= (unsigned int)(MaxSteps)) {
      //cout << "Increasing size for trajectory array of " << keyword << " to " << (MaxSteps+1) << "." << endl;
      Trajectories[Walker].R.resize(MaxSteps+1);
      Trajectories[Walker].U.resize(MaxSteps+1);
      Trajectories[Walker].F.resize(MaxSteps+1);
    }
  }
  // push endstep to last one
  Walker = start;
  while (Walker->next != end) { // remove the endstep (is now the very last one)
    Walker = Walker->next;
    for (int n=NDIM;n--;) {
      Trajectories[Walker].R.at(MaxSteps).x[n] = Trajectories[Walker].R.at(endstep).x[n];
      Trajectories[Walker].U.at(MaxSteps).x[n] = Trajectories[Walker].U.at(endstep).x[n];
      Trajectories[Walker].F.at(MaxSteps).x[n] = Trajectories[Walker].F.at(endstep).x[n];
    }
  }
  endstep = MaxSteps;
  
  // go through all steps and add the molecular configuration to the list and to the Trajectories of \a this molecule
  *out << Verbose(1) << "Filling intermediate " << MaxSteps << " steps with MDSteps of " << MDSteps << "." << endl;
  for (int step = 0; step <= MaxSteps; step++) {
    mol = new molecule(elemente);
    MoleculePerStep->insert(mol);
    Walker = start;
    while (Walker->next != end) {
      Walker = Walker->next;
      // add to molecule list
      Sprinter = mol->AddCopyAtom(Walker);
      for (int n=NDIM;n--;) {
        Sprinter->x.x[n] = Trajectories[Walker].R.at(startstep).x[n] + (Trajectories[PermutationMap[Walker->nr]].R.at(endstep).x[n] - Trajectories[Walker].R.at(startstep).x[n])*((double)step/(double)MaxSteps);
        // add to Trajectories
        //*out << Verbose(3) << step << ">=" << MDSteps-1 << endl;
        if (step < MaxSteps) {
          Trajectories[Walker].R.at(step).x[n] = Trajectories[Walker].R.at(startstep).x[n] + (Trajectories[PermutationMap[Walker->nr]].R.at(endstep).x[n] - Trajectories[Walker].R.at(startstep).x[n])*((double)step/(double)MaxSteps);
          Trajectories[Walker].U.at(step).x[n] = 0.;
          Trajectories[Walker].F.at(step).x[n] = 0.;
        }
      }
    }
  }
  MDSteps = MaxSteps+1;   // otherwise new Trajectories' points aren't stored on save&exit
  
  // store the list to single step files
  int *SortIndex = (int *) Malloc(AtomCount*sizeof(int), "molecule::LinearInterpolationBetweenConfiguration: *SortIndex");
  for (int i=AtomCount; i--; )
    SortIndex[i] = i;
  status = MoleculePerStep->OutputConfigForListOfFragments(out, &configuration, SortIndex);
  
  // free and return
  Free((void **)&PermutationMap, "molecule::MinimiseConstrainedPotential: *PermutationMap");
  delete(MoleculePerStep);
  return status;
};

/** Parses nuclear forces from file and performs Verlet integration.
 * Note that we assume the parsed forces to be in atomic units (hence, if coordinates are in angstroem, we
 * have to transform them).
 * This adds a new MD step to the config file.
 * \param *out output stream for debugging
 * \param *file filename
 * \param config structure with config::Deltat, config::IsAngstroem, config::DoConstrained
 * \param delta_t time step width in atomic units
 * \param IsAngstroem whether coordinates are in angstroem (true) or bohrradius (false)
 * \param DoConstrained whether we perform a constrained (>0, target step in molecule::trajectories) or unconstrained (0) molecular dynamics, \sa molecule::MinimiseConstrainedPotential() 
 * \return true - file found and parsed, false - file not found or imparsable
 * \todo This is not yet checked if it is correctly working with DoConstrained set to true.
 */
bool molecule::VerletForceIntegration(ofstream *out, char *file, config &configuration)
{
  atom *walker = NULL;
  ifstream input(file);
  string token;
  stringstream item;
  double IonMass, Vector[NDIM], ConstrainedPotentialEnergy, ActualTemp;
  ForceMatrix Force;

  CountElements();  // make sure ElementsInMolecule is up to date

  // check file
  if (input == NULL) {
    return false;
  } else {
    // parse file into ForceMatrix
    if (!Force.ParseMatrix(file, 0,0,0)) {
      cerr << "Could not parse Force Matrix file " << file << "." << endl;
      return false;
    }
    if (Force.RowCounter[0] != AtomCount) {
      cerr << "Mismatch between number of atoms in file " << Force.RowCounter[0] << " and in molecule " << AtomCount << "." << endl;
      return false;
    }
    // correct Forces
    for(int d=0;d<NDIM;d++)
      Vector[d] = 0.;
    for(int i=0;i<AtomCount;i++)
      for(int d=0;d<NDIM;d++) {
        Vector[d] += Force.Matrix[0][i][d+5];
      }
    for(int i=0;i<AtomCount;i++)
      for(int d=0;d<NDIM;d++) {
        Force.Matrix[0][i][d+5] -= Vector[d]/(double)AtomCount;
      }
    // solve a constrained potential if we are meant to
    if (configuration.DoConstrainedMD) {
      // calculate forces and potential
      atom **PermutationMap = NULL;
      ConstrainedPotentialEnergy = MinimiseConstrainedPotential(out, PermutationMap,configuration.DoConstrainedMD, 0, configuration.GetIsAngstroem());
      EvaluateConstrainedForces(out, configuration.DoConstrainedMD, 0, PermutationMap, &Force);
      Free((void **)&PermutationMap, "molecule::MinimiseConstrainedPotential: *PermutationMap");
    }
    
    // and perform Verlet integration for each atom with position, velocity and force vector
    walker = start;
    while (walker->next != end) { // go through every atom of this element
      walker = walker->next;
      //a = configuration.Deltat*0.5/walker->type->mass;        // (F+F_old)/2m = a and thus: v = (F+F_old)/2m * t = (F + F_old) * a
      // check size of vectors
      if (Trajectories[walker].R.size() <= (unsigned int)(MDSteps)) {
        //out << "Increasing size for trajectory array of " << *walker << " to " << (size+10) << "." << endl;
        Trajectories[walker].R.resize(MDSteps+10);
        Trajectories[walker].U.resize(MDSteps+10);
        Trajectories[walker].F.resize(MDSteps+10);
      }
      
      // Update R (and F)
      for (int d=0; d<NDIM; d++) {
        Trajectories[walker].F.at(MDSteps).x[d] = -Force.Matrix[0][walker->nr][d+5]*(configuration.GetIsAngstroem() ? AtomicLengthToAngstroem : 1.);
        Trajectories[walker].R.at(MDSteps).x[d] = Trajectories[walker].R.at(MDSteps-1).x[d];
        Trajectories[walker].R.at(MDSteps).x[d] += configuration.Deltat*(Trajectories[walker].U.at(MDSteps-1).x[d]);     // s(t) = s(0) + v * deltat + 1/2 a * deltat^2 
        Trajectories[walker].R.at(MDSteps).x[d] += 0.5*configuration.Deltat*configuration.Deltat*(Trajectories[walker].F.at(MDSteps).x[d]/walker->type->mass);     // F = m * a and s = 0.5 * F/m * t^2 = F * a * t
      }
      // Update U
      for (int d=0; d<NDIM; d++) {
        Trajectories[walker].U.at(MDSteps).x[d] = Trajectories[walker].U.at(MDSteps-1).x[d]; 
        Trajectories[walker].U.at(MDSteps).x[d] += configuration.Deltat * (Trajectories[walker].F.at(MDSteps).x[d]+Trajectories[walker].F.at(MDSteps-1).x[d]/walker->type->mass); // v = F/m * t
      }
//      out << "Integrated position&velocity of step " << (MDSteps) << ": ("; 
//      for (int d=0;d<NDIM;d++)
//        out << Trajectories[walker].R.at(MDSteps).x[d] << " ";          // next step
//      out << ")\t(";
//      for (int d=0;d<NDIM;d++)
//        cout << Trajectories[walker].U.at(MDSteps).x[d] << " ";          // next step
//      out << ")" << endl;
            // next atom
    }
  }
  // correct velocities (rather momenta) so that center of mass remains motionless
  for(int d=0;d<NDIM;d++)
    Vector[d] = 0.;
  IonMass = 0.;
  walker = start;
  while (walker->next != end) { // go through every atom
    walker = walker->next;
    IonMass += walker->type->mass;  // sum up total mass
    for(int d=0;d<NDIM;d++) {
      Vector[d] += Trajectories[walker].U.at(MDSteps).x[d]*walker->type->mass;
    }
  }
  // correct velocities (rather momenta) so that center of mass remains motionless
  for(int d=0;d<NDIM;d++)
    Vector[d] /= IonMass;
  ActualTemp = 0.;
  walker = start;
  while (walker->next != end) { // go through every atom of this element
    walker = walker->next;
    for(int d=0;d<NDIM;d++) {
      Trajectories[walker].U.at(MDSteps).x[d] -= Vector[d];
      ActualTemp += 0.5 * walker->type->mass * Trajectories[walker].U.at(MDSteps).x[d] * Trajectories[walker].U.at(MDSteps).x[d];
    }
  }
  Thermostats(configuration, ActualTemp, Berendsen);
  MDSteps++;


  // exit
  return true;
};

/** Implementation of various thermostats.
 * All these thermostats apply an additional force which has the following forms:
 * -# Woodcock
 *  \f$p_i \rightarrow \sqrt{\frac{T_0}{T}} \cdot p_i\f$
 * -# Gaussian
 *  \f$ \frac{ \sum_i \frac{p_i}{m_i} \frac{\partial V}{\partial q_i}} {\sum_i \frac{p^2_i}{m_i}} \cdot p_i\f$
 * -# Langevin
 *  \f$p_{i,n} \rightarrow \sqrt{1-\alpha^2} p_{i,0} + \alpha p_r\f$  
 * -# Berendsen
 *  \f$p_i \rightarrow \left [ 1+ \frac{\delta t}{\tau_T} \left ( \frac{T_0}{T} \right ) \right ]^{\frac{1}{2}} \cdot p_i\f$
 * -# Nose-Hoover
 *  \f$\zeta p_i \f$ with \f$\frac{\partial \zeta}{\partial t} = \frac{1}{M_s} \left ( \sum^N_{i=1} \frac{p_i^2}{m_i} - g k_B T \right )\f$
 * These Thermostats either simply rescale the velocities, thus this function should be called after ion velocities have been updated, and/or
 * have a constraint force acting additionally on the ions. In the latter case, the ion speeds have to be modified
 * belatedly and the constraint force set.
 * \param *P Problem at hand
 * \param i which of the thermostats to take: 0 - none, 1 - Woodcock, 2 - Gaussian, 3 - Langevin, 4 - Berendsen, 5 - Nose-Hoover
 * \sa InitThermostat()
 */
void molecule::Thermostats(config &configuration, double ActualTemp, int Thermostat)
{
  double ekin = 0.;
  double E = 0., G = 0.;
  double delta_alpha = 0.;
  double ScaleTempFactor;
  double sigma;
  double IonMass;
  int d;
  gsl_rng * r;
  const gsl_rng_type * T;
  double *U = NULL, *F = NULL, FConstraint[NDIM];
  atom *walker = NULL;
  
  // calculate scale configuration
  ScaleTempFactor = configuration.TargetTemp/ActualTemp;
    
  // differentating between the various thermostats
  switch(Thermostat) {
     case None:
      cout << Verbose(2) <<  "Applying no thermostat..." << endl;
      break;
     case Woodcock:
      if ((configuration.ScaleTempStep > 0) && ((MDSteps-1) % configuration.ScaleTempStep == 0)) {
        cout << Verbose(2) <<  "Applying Woodcock thermostat..." << endl;
        walker = start;
        while (walker->next != end) { // go through every atom of this element
          walker = walker->next;
          IonMass = walker->type->mass;
          U = Trajectories[walker].U.at(MDSteps).x;
          if (walker->FixedIon == 0) // even FixedIon moves, only not by other's forces
            for (d=0; d<NDIM; d++) {
              U[d] *= sqrt(ScaleTempFactor);
              ekin += 0.5*IonMass * U[d]*U[d];
            }
        }
      }
      break;
     case Gaussian:
      cout << Verbose(2) <<  "Applying Gaussian thermostat..." << endl;
      walker = start;
      while (walker->next != end) { // go through every atom of this element
        walker = walker->next;
        IonMass = walker->type->mass;
        U = Trajectories[walker].U.at(MDSteps).x;
        F = Trajectories[walker].F.at(MDSteps).x;
        if (walker->FixedIon == 0) // even FixedIon moves, only not by other's forces
          for (d=0; d<NDIM; d++) {
            G += U[d] * F[d]; 
            E += U[d]*U[d]*IonMass;
          }
      }
      cout << Verbose(1) << "Gaussian Least Constraint constant is " << G/E << "." << endl;
      walker = start;
      while (walker->next != end) { // go through every atom of this element
        walker = walker->next;
        IonMass = walker->type->mass;
        U = Trajectories[walker].U.at(MDSteps).x;
        F = Trajectories[walker].F.at(MDSteps).x;
        if (walker->FixedIon == 0) // even FixedIon moves, only not by other's forces
          for (d=0; d<NDIM; d++) {
            FConstraint[d] = (G/E) * (U[d]*IonMass);
            U[d] += configuration.Deltat/IonMass * (FConstraint[d]);
            ekin += IonMass * U[d]*U[d];
          }
      }
      break;
     case Langevin:
      cout << Verbose(2) <<  "Applying Langevin thermostat..." << endl;
      // init random number generator
      gsl_rng_env_setup();
      T = gsl_rng_default;
      r = gsl_rng_alloc (T);
      // Go through each ion
      walker = start;
      while (walker->next != end) { // go through every atom of this element
        walker = walker->next;
        IonMass = walker->type->mass;
        sigma  = sqrt(configuration.TargetTemp/IonMass); // sigma = (k_b T)/m (Hartree/atomicmass = atomiclength/atomictime)
        U = Trajectories[walker].U.at(MDSteps).x;
        F = Trajectories[walker].F.at(MDSteps).x;
        if (walker->FixedIon == 0) { // even FixedIon moves, only not by other's forces
          // throw a dice to determine whether it gets hit by a heat bath particle
          if (((((rand()/(double)RAND_MAX))*configuration.TempFrequency) < 1.)) {  
            cout << Verbose(3) << "Particle " << *walker << " was hit (sigma " << sigma << "): " << sqrt(U[0]*U[0]+U[1]*U[1]+U[2]*U[2]) << " -> ";
            // pick three random numbers from a Boltzmann distribution around the desired temperature T for each momenta axis
            for (d=0; d<NDIM; d++) {
              U[d] = gsl_ran_gaussian (r, sigma);
            }
            cout << sqrt(U[0]*U[0]+U[1]*U[1]+U[2]*U[2]) << endl;
          }
          for (d=0; d<NDIM; d++)
            ekin += 0.5*IonMass * U[d]*U[d];
        }
      }
      break;
     case Berendsen:
      cout << Verbose(2) <<  "Applying Berendsen-VanGunsteren thermostat..." << endl;
      walker = start;
      while (walker->next != end) { // go through every atom of this element
        walker = walker->next;
        IonMass = walker->type->mass;
        U = Trajectories[walker].U.at(MDSteps).x;
        F = Trajectories[walker].F.at(MDSteps).x;
        if (walker->FixedIon == 0) { // even FixedIon moves, only not by other's forces
          for (d=0; d<NDIM; d++) {
            U[d] *= sqrt(1+(configuration.Deltat/configuration.TempFrequency)*(ScaleTempFactor-1));
            ekin += 0.5*IonMass * U[d]*U[d];
          }
        }
      }
      break;
     case NoseHoover:
      cout << Verbose(2) <<  "Applying Nose-Hoover thermostat..." << endl;
      // dynamically evolve alpha (the additional degree of freedom)
      delta_alpha = 0.;
      walker = start;
      while (walker->next != end) { // go through every atom of this element
        walker = walker->next;
        IonMass = walker->type->mass;
        U = Trajectories[walker].U.at(MDSteps).x;
        if (walker->FixedIon == 0) { // even FixedIon moves, only not by other's forces
          for (d=0; d<NDIM; d++) {
            delta_alpha += U[d]*U[d]*IonMass;
          }
        }
      }
      delta_alpha = (delta_alpha - (3.*AtomCount+1.) * configuration.TargetTemp)/(configuration.HooverMass*Units2Electronmass);
      configuration.alpha += delta_alpha*configuration.Deltat;
      cout << Verbose(3) << "alpha = " << delta_alpha << " * " << configuration.Deltat << " = " << configuration.alpha << "." << endl;
      // apply updated alpha as additional force
      walker = start;
      while (walker->next != end) { // go through every atom of this element
        walker = walker->next;
        IonMass = walker->type->mass;
        U = Trajectories[walker].U.at(MDSteps).x;
        if (walker->FixedIon == 0) { // even FixedIon moves, only not by other's forces
          for (d=0; d<NDIM; d++) {
              FConstraint[d] = - configuration.alpha * (U[d] * IonMass);
              U[d] += configuration.Deltat/IonMass * (FConstraint[d]);
              ekin += (0.5*IonMass) * U[d]*U[d];
            }
        }
      }
      break;
  }    
  cout << Verbose(1) << "Kinetic energy is " << ekin << "." << endl;
};

/** Align all atoms in such a manner that given vector \a *n is along z axis. 
 * \param n[] alignment vector.
 */
void molecule::Align(Vector *n)
{
  atom *ptr = start;
  double alpha, tmp;
  Vector z_axis;
  z_axis.x[0] = 0.;
  z_axis.x[1] = 0.;
  z_axis.x[2] = 1.;

  // rotate on z-x plane
  cout << Verbose(0) << "Begin of Aligning all atoms." << endl;
  alpha = atan(-n->x[0]/n->x[2]);
  cout << Verbose(1) << "Z-X-angle: " << alpha << " ... ";
  while (ptr->next != end) {
    ptr = ptr->next;
    tmp = ptr->x.x[0];
    ptr->x.x[0] =  cos(alpha) * tmp + sin(alpha) * ptr->x.x[2];
    ptr->x.x[2] = -sin(alpha) * tmp + cos(alpha) * ptr->x.x[2];
    for (int j=0;j<MDSteps;j++) {
      tmp = Trajectories[ptr].R.at(j).x[0];
      Trajectories[ptr].R.at(j).x[0] =  cos(alpha) * tmp + sin(alpha) * Trajectories[ptr].R.at(j).x[2];
      Trajectories[ptr].R.at(j).x[2] = -sin(alpha) * tmp + cos(alpha) * Trajectories[ptr].R.at(j).x[2];
    }
  }
  // rotate n vector
  tmp = n->x[0];
  n->x[0] =  cos(alpha) * tmp +  sin(alpha) * n->x[2];
  n->x[2] = -sin(alpha) * tmp +  cos(alpha) * n->x[2];
  cout << Verbose(1) << "alignment vector after first rotation: ";
  n->Output((ofstream *)&cout);
  cout << endl;

  // rotate on z-y plane
  ptr = start;
  alpha = atan(-n->x[1]/n->x[2]);
  cout << Verbose(1) << "Z-Y-angle: " << alpha << " ... ";
  while (ptr->next != end) {
    ptr = ptr->next;
    tmp = ptr->x.x[1];
    ptr->x.x[1] =  cos(alpha) * tmp + sin(alpha) * ptr->x.x[2];
    ptr->x.x[2] = -sin(alpha) * tmp + cos(alpha) * ptr->x.x[2];
    for (int j=0;j<MDSteps;j++) {
      tmp = Trajectories[ptr].R.at(j).x[1];
      Trajectories[ptr].R.at(j).x[1] =  cos(alpha) * tmp + sin(alpha) * Trajectories[ptr].R.at(j).x[2];
      Trajectories[ptr].R.at(j).x[2] = -sin(alpha) * tmp + cos(alpha) * Trajectories[ptr].R.at(j).x[2];
    }
  }
  // rotate n vector (for consistency check)
  tmp = n->x[1];
  n->x[1] =  cos(alpha) * tmp +  sin(alpha) * n->x[2];
  n->x[2] = -sin(alpha) * tmp +  cos(alpha) * n->x[2];

  cout << Verbose(1) << "alignment vector after second rotation: ";
  n->Output((ofstream *)&cout);
  cout << Verbose(1) << endl;
  cout << Verbose(0) << "End of Aligning all atoms." << endl;
};

/** Removes atom from molecule list and deletes it.
 * \param *pointer atom to be removed
 * \return true - succeeded, false - atom not found in list
 */
bool molecule::RemoveAtom(atom *pointer)
{
  if (ElementsInMolecule[pointer->type->Z] != 0)  { // this would indicate an error
    ElementsInMolecule[pointer->type->Z]--;  // decrease number of atom of this element
    AtomCount--;
  } else
    cerr << "ERROR: Atom " << pointer->Name << " is of element " << pointer->type->Z << " but the entry in the table of the molecule is 0!" << endl;
  if (ElementsInMolecule[pointer->type->Z] == 0)  // was last atom of this element?
    ElementCount--;
  Trajectories.erase(pointer);
  return remove(pointer, start, end);
};

/** Removes atom from molecule list, but does not delete it.
 * \param *pointer atom to be removed
 * \return true - succeeded, false - atom not found in list
 */
bool molecule::UnlinkAtom(atom *pointer)
{
  if (pointer == NULL)
    return false;
  if (ElementsInMolecule[pointer->type->Z] != 0)  // this would indicate an error
    ElementsInMolecule[pointer->type->Z]--; // decrease number of atom of this element
  else
    cerr << "ERROR: Atom " << pointer->Name << " is of element " << pointer->type->Z << " but the entry in the table of the molecule is 0!" << endl;
  if (ElementsInMolecule[pointer->type->Z] == 0)  // was last atom of this element?
    ElementCount--;
  Trajectories.erase(pointer);
  unlink(pointer);
  return true;
};

/** Removes every atom from molecule list.
 * \return true - succeeded, false - atom not found in list
 */
bool molecule::CleanupMolecule()
{
  return (cleanup(start,end) && cleanup(first,last));
};

/** Finds an atom specified by its continuous number.
 * \param Nr number of atom withim molecule
 * \return pointer to atom or NULL
 */
atom * molecule::FindAtom(int Nr)  const{
  atom * walker = find(&Nr, start,end);
  if (walker != NULL) {
    //cout << Verbose(0) << "Found Atom Nr. " << walker->nr << endl;
    return walker;
  } else {
    cout << Verbose(0) << "Atom not found in list." << endl;
    return NULL;
  }
};

/** Asks for atom number, and checks whether in list.
 * \param *text question before entering
 */
atom * molecule::AskAtom(string text)
{
  int No;
  atom *ion = NULL;
  do {
    //cout << Verbose(0) << "============Atom list==========================" << endl;
    //mol->Output((ofstream *)&cout);
    //cout << Verbose(0) << "===============================================" << endl;
    cout << Verbose(0) << text;
    cin >> No;
    ion = this->FindAtom(No);
  } while (ion == NULL);
  return ion;
};

/** Checks if given coordinates are within cell volume.
 * \param *x array of coordinates
 * \return true - is within, false - out of cell
 */
bool molecule::CheckBounds(const Vector *x) const
{
  bool result = true;
  int j =-1;
  for (int i=0;i<NDIM;i++) {
    j += i+1;
    result = result && ((x->x[i] >= 0) && (x->x[i] < cell_size[j]));
  }
  //return result;
  return true; /// probably not gonna use the check no more
};

/** Calculates sum over least square distance to line hidden in \a *x.
 * \param *x offset and direction vector
 * \param *params pointer to lsq_params structure
 * \return \f$ sum_i^N | y_i - (a + t_i b)|^2\f$
 */
double LeastSquareDistance (const gsl_vector * x, void * params)
{
  double res = 0, t;
  Vector a,b,c,d;
  struct lsq_params *par = (struct lsq_params *)params;
  atom *ptr = par->mol->start;

  // initialize vectors
  a.x[0] = gsl_vector_get(x,0);
  a.x[1] = gsl_vector_get(x,1);
  a.x[2] = gsl_vector_get(x,2);
  b.x[0] = gsl_vector_get(x,3);
  b.x[1] = gsl_vector_get(x,4);
  b.x[2] = gsl_vector_get(x,5);
  // go through all atoms
  while (ptr != par->mol->end) {
    ptr = ptr->next;
    if (ptr->type == ((struct lsq_params *)params)->type) { // for specific type
      c.CopyVector(&ptr->x);  // copy vector to temporary one
      c.SubtractVector(&a);   // subtract offset vector
      t = c.ScalarProduct(&b);           // get direction parameter
      d.CopyVector(&b);       // and create vector
      d.Scale(&t);
      c.SubtractVector(&d);   // ... yielding distance vector
      res += d.ScalarProduct((const Vector *)&d);        // add squared distance
    }
  }
  return res;
};

/** By minimizing the least square distance gains alignment vector.
 * \bug this is not yet working properly it seems
 */
void molecule::GetAlignvector(struct lsq_params * par) const
{
    int np = 6;

   const gsl_multimin_fminimizer_type *T =
     gsl_multimin_fminimizer_nmsimplex;
   gsl_multimin_fminimizer *s = NULL;
   gsl_vector *ss;
   gsl_multimin_function minex_func;

   size_t iter = 0, i;
   int status;
   double size;

   /* Initial vertex size vector */
   ss = gsl_vector_alloc (np);

   /* Set all step sizes to 1 */
   gsl_vector_set_all (ss, 1.0);

   /* Starting point */
   par->x = gsl_vector_alloc (np);
   par->mol = this;

   gsl_vector_set (par->x, 0, 0.0);  // offset
   gsl_vector_set (par->x, 1, 0.0);
   gsl_vector_set (par->x, 2, 0.0);
   gsl_vector_set (par->x, 3, 0.0);  // direction
   gsl_vector_set (par->x, 4, 0.0);
   gsl_vector_set (par->x, 5, 1.0);

   /* Initialize method and iterate */
   minex_func.f = &LeastSquareDistance;
   minex_func.n = np;
   minex_func.params = (void *)par;

   s = gsl_multimin_fminimizer_alloc (T, np);
   gsl_multimin_fminimizer_set (s, &minex_func, par->x, ss);

   do
     {
       iter++;
       status = gsl_multimin_fminimizer_iterate(s);

       if (status)
         break;

       size = gsl_multimin_fminimizer_size (s);
       status = gsl_multimin_test_size (size, 1e-2);

       if (status == GSL_SUCCESS)
         {
           printf ("converged to minimum at\n");
         }

       printf ("%5d ", (int)iter);
       for (i = 0; i < (size_t)np; i++)
         {
           printf ("%10.3e ", gsl_vector_get (s->x, i));
         }
       printf ("f() = %7.3f size = %.3f\n", s->fval, size);
     }
   while (status == GSL_CONTINUE && iter < 100);

  for (i=0;i<(size_t)np;i++)
    gsl_vector_set(par->x, i, gsl_vector_get(s->x, i));
   //gsl_vector_free(par->x);
   gsl_vector_free(ss);
   gsl_multimin_fminimizer_free (s);
};

/** Prints molecule to *out.
 * \param *out output stream
 */
bool molecule::Output(ofstream *out)
{
  atom *walker = NULL;
  int ElementNo[MAX_ELEMENTS], AtomNo[MAX_ELEMENTS];
  CountElements();

  for (int i=0;i<MAX_ELEMENTS;++i) {
    AtomNo[i] = 0;
    ElementNo[i] = 0;
  }
  if (out == NULL) {
    return false;
  } else {
    *out << "#Ion_TypeNr._Nr.R[0]    R[1]    R[2]    MoveType (0 MoveIon, 1 FixedIon)" << endl;
    walker = start;
    while (walker->next != end) { // go through every atom of this element
      walker = walker->next;
      ElementNo[walker->type->Z] = 1;
    }
    int current=1;
    for (int i=0;i<MAX_ELEMENTS;++i) {
      if (ElementNo[i] == 1)
        ElementNo[i] = current++;
    }
    walker = start;
    while (walker->next != end) { // go through every atom of this element
      walker = walker->next;
      AtomNo[walker->type->Z]++;
      walker->Output(ElementNo[walker->type->Z], AtomNo[walker->type->Z], out); // removed due to trajectories
    }
    return true;
  }
};

/** Prints molecule with all atomic trajectory positions to *out.
 * \param *out output stream
 */
bool molecule::OutputTrajectories(ofstream *out)
{
  atom *walker = NULL;
  int ElementNo[MAX_ELEMENTS], AtomNo[MAX_ELEMENTS];
  CountElements();

  if (out == NULL) {
    return false;
  } else {
    for (int step = 0; step < MDSteps; step++) {
      if (step == 0) {
        *out << "#Ion_TypeNr._Nr.R[0]    R[1]    R[2]    MoveType (0 MoveIon, 1 FixedIon)" << endl;
      } else {
        *out << "# ====== MD step " << step << " =========" << endl;
      }
      for (int i=0;i<MAX_ELEMENTS;++i) {
        AtomNo[i] = 0;
        ElementNo[i] = 0;
      }
    walker = start;
    while (walker->next != end) { // go through every atom of this element
      walker = walker->next;
      ElementNo[walker->type->Z] = 1;
    }
    int current=1;
    for (int i=0;i<MAX_ELEMENTS;++i) {
      if (ElementNo[i] == 1)
        ElementNo[i] = current++;
    }
    walker = start;
      while (walker->next != end) { // go through every atom of this element
        walker = walker->next;
        AtomNo[walker->type->Z]++;
        *out << "Ion_Type" << ElementNo[walker->type->Z] << "_" << AtomNo[walker->type->Z] << "\t"  << fixed << setprecision(9) << showpoint;
        *out << Trajectories[walker].R.at(step).x[0] << "\t" << Trajectories[walker].R.at(step).x[1] << "\t" << Trajectories[walker].R.at(step).x[2];
        *out << "\t" << walker->FixedIon;
        if (Trajectories[walker].U.at(step).Norm() > MYEPSILON)
          *out << "\t" << scientific << setprecision(6) << Trajectories[walker].U.at(step).x[0] << "\t" << Trajectories[walker].U.at(step).x[1] << "\t" << Trajectories[walker].U.at(step).x[2] << "\t";
        if (Trajectories[walker].F.at(step).Norm() > MYEPSILON)
          *out << "\t" << scientific << setprecision(6) << Trajectories[walker].F.at(step).x[0] << "\t" << Trajectories[walker].F.at(step).x[1] << "\t" << Trajectories[walker].F.at(step).x[2] << "\t";
        *out << "\t# Number in molecule " << walker->nr << endl;
      }
    }
    return true;
  }
};

/** Outputs contents of molecule::ListOfBondsPerAtom.
 * \param *out output stream
 */
void molecule::OutputListOfBonds(ofstream *out) const
{
  *out << Verbose(2) << endl << "From Contents of ListOfBondsPerAtom, all non-hydrogen atoms:" << endl;
  atom *Walker = start;
  while (Walker->next != end) {
    Walker = Walker->next;
#ifdef ADDHYDROGEN
    if (Walker->type->Z != 1) {   // regard only non-hydrogen
#endif
      *out << Verbose(2) << "Atom " << Walker->Name << " has Bonds: "<<endl;
      for(int j=0;j<NumberOfBondsPerAtom[Walker->nr];j++) {
        *out << Verbose(3) << *(ListOfBondsPerAtom)[Walker->nr][j] << endl;
      }
#ifdef ADDHYDROGEN
    }
#endif
  }
  *out << endl;
};

/** Output of element before the actual coordination list.
 * \param *out stream pointer
 */
bool molecule::Checkout(ofstream *out)  const
{
  return elemente->Checkout(out, ElementsInMolecule);
};

/** Prints molecule with all its trajectories to *out as xyz file.
 * \param *out output stream
 */
bool molecule::OutputTrajectoriesXYZ(ofstream *out)
{
  atom *walker = NULL;
  int No = 0;
  time_t now;

  now = time((time_t *)NULL);   // Get the system time and put it into 'now' as 'calender time'
  walker = start;
  while (walker->next != end) { // go through every atom and count
    walker = walker->next;
    No++;
  }
  if (out != NULL) {
    for (int step=0;step<MDSteps;step++) {
      *out << No << "\n\tCreated by molecuilder, step " << step << ", on " << ctime(&now);
      walker = start;
      while (walker->next != end) { // go through every atom of this element
        walker = walker->next;
        *out << walker->type->symbol << "\t" << Trajectories[walker].R.at(step).x[0] << "\t" << Trajectories[walker].R.at(step).x[1] << "\t" << Trajectories[walker].R.at(step).x[2] << endl;
      }
    }
    return true;
  } else
    return false;
};

/** Prints molecule to *out as xyz file.
* \param *out output stream
 */
bool molecule::OutputXYZ(ofstream *out) const
{
  atom *walker = NULL;
  int AtomNo = 0;
  time_t now;

  now = time((time_t *)NULL);   // Get the system time and put it into 'now' as 'calender time'
  walker = start;
  while (walker->next != end) { // go through every atom and count
    walker = walker->next;
    AtomNo++;
  }
  if (out != NULL) {
    *out << AtomNo << "\n\tCreated by molecuilder on " << ctime(&now);
    walker = start;
    while (walker->next != end) { // go through every atom of this element
      walker = walker->next;
      walker->OutputXYZLine(out);
    }
    return true;
  } else
    return false;
};

/** Brings molecule::AtomCount and atom::*Name up-to-date.
 * \param *out output stream for debugging
 */
void molecule::CountAtoms(ofstream *out)
{
  int i = 0;
  atom *Walker = start;
  while (Walker->next != end) {
    Walker = Walker->next;
    i++;
  }
  if ((AtomCount == 0) || (i != AtomCount)) {
    *out << Verbose(3) << "Mismatch in AtomCount " << AtomCount << " and recounted number " << i << ", renaming all." << endl;
    AtomCount = i;

    // count NonHydrogen atoms and give each atom a unique name
    if (AtomCount != 0) {
      i=0;
      NoNonHydrogen = 0;
      Walker = start;
      while (Walker->next != end) {
        Walker = Walker->next;
        Walker->nr = i;   // update number in molecule (for easier referencing in FragmentMolecule lateron)
        if (Walker->type->Z != 1) // count non-hydrogen atoms whilst at it
          NoNonHydrogen++;
        Free((void **)&Walker->Name, "molecule::CountAtoms: *walker->Name");
        Walker->Name = (char *) Malloc(sizeof(char)*6, "molecule::CountAtoms: *walker->Name");
        sprintf(Walker->Name, "%2s%02d", Walker->type->symbol, Walker->nr+1);
        *out << "Naming atom nr. " << Walker->nr << " " << Walker->Name << "." << endl;
        i++;
      }
    } else
      *out << Verbose(3) << "AtomCount is still " << AtomCount << ", thus counting nothing." << endl;
  }
};

/** Brings molecule::ElementCount and molecule::ElementsInMolecule up-to-date.
 */
void molecule::CountElements()
{
  int i = 0;
  for(i=MAX_ELEMENTS;i--;)
    ElementsInMolecule[i] = 0;
  ElementCount = 0;

  atom *walker = start;
  while (walker->next != end) {
    walker = walker->next;
    ElementsInMolecule[walker->type->Z]++;
    i++;
  }
  for(i=MAX_ELEMENTS;i--;)
    ElementCount += (ElementsInMolecule[i] != 0 ? 1 : 0);
};

/** Counts all cyclic bonds and returns their number.
 * \note Hydrogen bonds can never by cyclic, thus no check for that
 * \param *out output stream for debugging
 * \return number opf cyclic bonds
 */
int molecule::CountCyclicBonds(ofstream *out)
{
  int No = 0;
  int *MinimumRingSize = NULL;
  MoleculeLeafClass *Subgraphs = NULL;
  class StackClass<bond *> *BackEdgeStack = NULL;
  bond *Binder = first;
  if ((Binder->next != last) && (Binder->next->Type == Undetermined)) {
    *out << Verbose(0) << "No Depth-First-Search analysis performed so far, calling ..." << endl;
    Subgraphs = DepthFirstSearchAnalysis(out, BackEdgeStack);
    while (Subgraphs->next != NULL) {
      Subgraphs = Subgraphs->next;
      delete(Subgraphs->previous);
    }
    delete(Subgraphs);
    delete[](MinimumRingSize);
  }
  while(Binder->next != last) {
    Binder = Binder->next;
    if (Binder->Cyclic)
      No++;
  }
  delete(BackEdgeStack);
  return No;
};
/** Returns Shading as a char string.
 * \param color the Shading
 * \return string of the flag
 */
string molecule::GetColor(enum Shading color)
{
  switch(color) {
    case white:
      return "white";
      break;
    case lightgray:
      return "lightgray";
      break;
    case darkgray:
      return "darkgray";
      break;
    case black:
      return "black";
      break;
    default:
      return "uncolored";
      break;
  };
};


/** Counts necessary number of valence electrons and returns number and SpinType.
 * \param configuration containing everything
 */
void molecule::CalculateOrbitals(class config &configuration)
{
  configuration.MaxPsiDouble = configuration.PsiMaxNoDown = configuration.PsiMaxNoUp = configuration.PsiType = 0;
  for(int i=MAX_ELEMENTS;i--;) {
    if (ElementsInMolecule[i] != 0) {
      //cout << "CalculateOrbitals: " << elemente->FindElement(i)->name << " has a valence of " << (int)elemente->FindElement(i)->Valence << " and there are " << ElementsInMolecule[i] << " of it." << endl;
      configuration.MaxPsiDouble += ElementsInMolecule[i]*((int)elemente->FindElement(i)->Valence);
    }
  }
  configuration.PsiMaxNoDown = configuration.MaxPsiDouble/2 + (configuration.MaxPsiDouble % 2);
  configuration.PsiMaxNoUp = configuration.MaxPsiDouble/2;
  configuration.MaxPsiDouble /= 2;
  configuration.PsiType = (configuration.PsiMaxNoDown == configuration.PsiMaxNoUp) ? 0 : 1;
  if ((configuration.PsiType == 1) && (configuration.ProcPEPsi < 2)) {
    configuration.ProcPEGamma /= 2;
    configuration.ProcPEPsi *= 2;
  } else {
    configuration.ProcPEGamma *= configuration.ProcPEPsi;
    configuration.ProcPEPsi = 1;
  }
  configuration.InitMaxMinStopStep = configuration.MaxMinStopStep = configuration.MaxPsiDouble;
};

/** Creates an adjacency list of the molecule.
 * We obtain an outside file with the indices of atoms which are bondmembers.
 */
void molecule::CreateAdjacencyList2(ofstream *out, ifstream *input)
{

  // 1 We will parse bonds out of the dbond file created by tremolo.
      int atom1, atom2, temp;
      atom *Walker, *OtherWalker;

          if (!input)
          {
            cout << Verbose(1) << "Opening silica failed \n";
          };

      *input >> ws >> atom1;
      *input >> ws >> atom2;
          cout << Verbose(1) << "Scanning file\n";
          while (!input->eof()) // Check whether we read everything already
          {
        *input >> ws >> atom1;
        *input >> ws >> atom2;
            if(atom2<atom1) //Sort indices of atoms in order
            {
              temp=atom1;
              atom1=atom2;
              atom2=temp;
            };

            Walker=start;
            while(Walker-> nr != atom1) // Find atom corresponding to first index
            {
              Walker = Walker->next;
            };
            OtherWalker = Walker->next;
            while(OtherWalker->nr != atom2) // Find atom corresponding to second index
            {
              OtherWalker= OtherWalker->next;
            };
            AddBond(Walker, OtherWalker); //Add the bond between the two atoms with respective indices.

          }

          CreateListOfBondsPerAtom(out);

};


/** Creates an adjacency list of the molecule.
 * Generally, we use the CSD approach to bond recognition, that is the the distance
 * between two atoms A and B must be within [Rcov(A)+Rcov(B)-t,Rcov(A)+Rcov(B)+t] with
 * a threshold t = 0.4 Angstroem.
 * To make it O(N log N) the function uses the linked-cell technique as follows:
 * The procedure is step-wise:
 *  -# Remove every bond in list
 *  -# Count the atoms in the molecule with CountAtoms()
 *  -# partition cell into smaller linked cells of size \a bonddistance
 *  -# put each atom into its corresponding cell
 *  -# go through every cell, check the atoms therein against all possible bond partners in the 27 adjacent cells, add bond if true
 *  -# create the list of bonds via CreateListOfBondsPerAtom()
 *  -# correct the bond degree iteratively (single->double->triple bond)
 *  -# finally print the bond list to \a *out if desired
 * \param *out out stream for printing the matrix, NULL if no output
 * \param bonddistance length of linked cells (i.e. maximum minimal length checked)
 * \param IsAngstroem whether coordinate system is gauged to Angstroem or Bohr radii
 */
void molecule::CreateAdjacencyList(ofstream *out, double bonddistance, bool IsAngstroem)
{

  atom *Walker = NULL, *OtherWalker = NULL, *Candidate = NULL;
  int No, NoBonds, CandidateBondNo;
  int NumberCells, divisor[NDIM], n[NDIM], N[NDIM], index, Index, j;
  molecule **CellList;
  double distance, MinDistance, MaxDistance;
  double *matrix = ReturnFullMatrixforSymmetric(cell_size);
  Vector x;
  int FalseBondDegree = 0;

  BondDistance = bonddistance; // * ((IsAngstroem) ? 1. : 1./AtomicLengthToAngstroem);
  *out << Verbose(0) << "Begin of CreateAdjacencyList." << endl;
  // remove every bond from the list
  if ((first->next != last) && (last->previous != first)) {  // there are bonds present
    cleanup(first,last);
  }

  // count atoms in molecule = dimension of matrix (also give each unique name and continuous numbering)
  CountAtoms(out);
  *out << Verbose(1) << "AtomCount " << AtomCount << "." << endl;

  if (AtomCount != 0) {
    // 1. find divisor for each axis, such that a sphere with radius of at least bonddistance can be placed into each cell
    j=-1;
    for (int i=0;i<NDIM;i++) {
      j += i+1;
      divisor[i] = (int)floor(cell_size[j]/bonddistance); // take smaller value such that size of linked cell is at least bonddistance
      //*out << Verbose(1) << "divisor[" << i << "]  = " << divisor[i] << "." << endl;
    }
    // 2a. allocate memory for the cell list
    NumberCells = divisor[0]*divisor[1]*divisor[2];
    *out << Verbose(1) << "Allocating " << NumberCells << " cells." << endl;
    CellList = (molecule **) Malloc(sizeof(molecule *)*NumberCells, "molecule::CreateAdjacencyList - ** CellList");
    for (int i=NumberCells;i--;)
      CellList[i] = NULL;

    // 2b. put all atoms into its corresponding list
    Walker = start;
    while(Walker->next != end) {
      Walker = Walker->next;
      //*out << Verbose(1) << "Current atom is " << *Walker << " with coordinates ";
      //Walker->x.Output(out);
      //*out << "." << endl;
      // compute the cell by the atom's coordinates
      j=-1;
      for (int i=0;i<NDIM;i++) {
        j += i+1;
        x.CopyVector(&(Walker->x));
        x.KeepPeriodic(out, matrix);
        n[i] = (int)floor(x.x[i]/cell_size[j]*(double)divisor[i]);
      }
      index = n[2] + (n[1] + n[0] * divisor[1]) * divisor[2];
      //*out << Verbose(1) << "Atom " << *Walker << " goes into cell number [" << n[0] << "," << n[1] << "," << n[2] << "] = " << index << "." << endl;
      // add copy atom to this cell
      if (CellList[index] == NULL)  // allocate molecule if not done
        CellList[index] = new molecule(elemente);
      OtherWalker = CellList[index]->AddCopyAtom(Walker); // add a copy of walker to this atom, father will be walker for later reference
      //*out << Verbose(1) << "Copy Atom is " << *OtherWalker << "." << endl;
    }
    //for (int i=0;i<NumberCells;i++)
      //*out << Verbose(1) << "Cell number " << i << ": " << CellList[i] << "." << endl;


    // 3a. go through every cell
    for (N[0]=divisor[0];N[0]--;)
      for (N[1]=divisor[1];N[1]--;)
        for (N[2]=divisor[2];N[2]--;) {
          Index = N[2] + (N[1] + N[0] * divisor[1]) * divisor[2];
          if (CellList[Index] != NULL) { // if there atoms in this cell
            //*out << Verbose(1) << "Current cell is " << Index << "." << endl;
            // 3b. for every atom therein
            Walker = CellList[Index]->start;
            while (Walker->next != CellList[Index]->end) {  // go through every atom
              Walker = Walker->next;
              //*out << Verbose(0) << "Current Atom is " << *Walker << "." << endl;
              // 3c. check for possible bond between each atom in this and every one in the 27 cells
              for (n[0]=-1;n[0]<=1;n[0]++)
                for (n[1]=-1;n[1]<=1;n[1]++)
                  for (n[2]=-1;n[2]<=1;n[2]++) {
                     // compute the index of this comparison cell and make it periodic
                    index = ((N[2]+n[2]+divisor[2])%divisor[2]) + (((N[1]+n[1]+divisor[1])%divisor[1]) + ((N[0]+n[0]+divisor[0])%divisor[0]) * divisor[1]) * divisor[2];
                    //*out << Verbose(1) << "Number of comparison cell is " << index << "." << endl;
                    if (CellList[index] != NULL) {  // if there are any atoms in this cell
                      OtherWalker = CellList[index]->start;
                      while(OtherWalker->next != CellList[index]->end) {  // go through every atom in this cell
                        OtherWalker = OtherWalker->next;
                        //*out << Verbose(0) << "Current comparison atom is " << *OtherWalker << "." << endl;
                        /// \todo periodic check is missing here!
                        //*out << Verbose(1) << "Checking distance " << OtherWalker->x.PeriodicDistanceSquared(&(Walker->x), cell_size) << " against typical bond length of " << bonddistance*bonddistance << "." << endl;
                        MinDistance = OtherWalker->type->CovalentRadius + Walker->type->CovalentRadius;
                        MinDistance *= (IsAngstroem) ? 1. : 1./AtomicLengthToAngstroem;
                        MaxDistance = MinDistance + BONDTHRESHOLD;
                        MinDistance -= BONDTHRESHOLD;
                        distance = OtherWalker->x.PeriodicDistanceSquared(&(Walker->x), cell_size);
                        if ((OtherWalker->father->nr > Walker->father->nr) && (distance <= MaxDistance*MaxDistance) && (distance >= MinDistance*MinDistance)) { // create bond if distance is smaller
                          //*out << Verbose(1) << "Adding Bond between " << *Walker << " and " << *OtherWalker << " in distance " << sqrt(distance) << "." << endl;
                          AddBond(Walker->father, OtherWalker->father, 1);  // also increases molecule::BondCount
                        } else {
                          //*out << Verbose(1) << "Not Adding: Wrong label order or distance too great." << endl;
                        }
                      }
                    }
                  }
            }
          }
        }



    // 4. free the cell again
    for (int i=NumberCells;i--;)
      if (CellList[i] != NULL) {
        delete(CellList[i]);
      }
    Free((void **)&CellList, "molecule::CreateAdjacencyList - ** CellList");

    // create the adjacency list per atom
    CreateListOfBondsPerAtom(out);

    // correct Bond degree of each bond by checking both bond partners for a mismatch between valence and current sum of bond degrees,
    // iteratively increase the one first where the other bond partner has the fewest number of bonds (i.e. in general bonds oxygene
    // preferred over carbon bonds). Beforehand, we had picked the first mismatching partner, which lead to oxygenes with single instead of
    // double bonds as was expected.
    if (BondCount != 0) {
      NoCyclicBonds = 0;
      *out << Verbose(1) << "Correcting Bond degree of each bond ... ";
      do {
        No = 0; // No acts as breakup flag (if 1 we still continue)
        Walker = start;
        while (Walker->next != end) { // go through every atom
          Walker = Walker->next;
          // count valence of first partner
          NoBonds = 0;
          for(j=0;j<NumberOfBondsPerAtom[Walker->nr];j++)
            NoBonds += ListOfBondsPerAtom[Walker->nr][j]->BondDegree;
          *out << Verbose(3) << "Walker " << *Walker << ": " << (int)Walker->type->NoValenceOrbitals << " > " << NoBonds << "?" << endl;
          if ((int)(Walker->type->NoValenceOrbitals) > NoBonds) { // we have a mismatch, check all bonding partners for mismatch
            Candidate = NULL;
            CandidateBondNo = -1;
            for(int i=0;i<NumberOfBondsPerAtom[Walker->nr];i++) { // go through each of its bond partners
              OtherWalker = ListOfBondsPerAtom[Walker->nr][i]->GetOtherAtom(Walker);
              // count valence of second partner
              NoBonds = 0;
              for(j=0;j<NumberOfBondsPerAtom[OtherWalker->nr];j++)
                NoBonds += ListOfBondsPerAtom[OtherWalker->nr][j]->BondDegree;
              *out << Verbose(3) << "OtherWalker " << *OtherWalker << ": " << (int)OtherWalker->type->NoValenceOrbitals << " > " << NoBonds << "?" << endl;
              if ((int)(OtherWalker->type->NoValenceOrbitals) > NoBonds) { // check if possible candidate
                if ((Candidate == NULL) || (NumberOfBondsPerAtom[Candidate->nr] > NumberOfBondsPerAtom[OtherWalker->nr])) { // pick the one with fewer number of bonds first
                  Candidate = OtherWalker;
                  CandidateBondNo = i;
                  *out << Verbose(3) << "New candidate is " << *Candidate << "." << endl;
                }
              }
            }
            if ((Candidate != NULL) && (CandidateBondNo != -1)) {
              ListOfBondsPerAtom[Walker->nr][CandidateBondNo]->BondDegree++;
              *out << Verbose(2) << "Increased bond degree for bond " << *ListOfBondsPerAtom[Walker->nr][CandidateBondNo] << "." << endl;
            } else
              *out << Verbose(2) << "Could not find correct degree for atom " << *Walker << "." << endl;
              FalseBondDegree++;
          }
        }
      } while (No);
    *out << " done." << endl;
    } else
      *out << Verbose(1) << "BondCount is " << BondCount << ", no bonds between any of the " << AtomCount << " atoms." << endl;
    *out << Verbose(1) << "I detected " << BondCount << " bonds in the molecule with distance " << bonddistance << ", " << FalseBondDegree << " bonds could not be corrected." << endl;

    // output bonds for debugging (if bond chain list was correctly installed)
    *out << Verbose(1) << endl << "From contents of bond chain list:";
    bond *Binder = first;
    while(Binder->next != last) {
      Binder = Binder->next;
      *out << *Binder << "\t" << endl;
    }
    *out << endl;
  } else
    *out << Verbose(1) << "AtomCount is " << AtomCount << ", thus no bonds, no connections!." << endl;
  *out << Verbose(0) << "End of CreateAdjacencyList." << endl;
  Free((void **)&matrix, "molecule::CreateAdjacencyList: *matrix");

};



/** Performs a Depth-First search on this molecule.
 * Marks bonds in molecule as cyclic, bridge, ... and atoms as
 * articulations points, ...
 * We use the algorithm from [Even, Graph Algorithms, p.62].
 * \param *out output stream for debugging
 * \param *&BackEdgeStack NULL pointer to StackClass with all the found back edges, allocated and filled on return
 * \return list of each disconnected subgraph as an individual molecule class structure
 */
MoleculeLeafClass * molecule::DepthFirstSearchAnalysis(ofstream *out, class StackClass<bond *> *&BackEdgeStack)
{
  class StackClass<atom *> *AtomStack = new StackClass<atom *>(AtomCount);
  BackEdgeStack = new StackClass<bond *> (BondCount);
  MoleculeLeafClass *SubGraphs = new MoleculeLeafClass(NULL);
  MoleculeLeafClass *LeafWalker = SubGraphs;
  int CurrentGraphNr = 0, OldGraphNr;
  int ComponentNumber = 0;
  atom *Walker = NULL, *OtherAtom = NULL, *Root = start->next;
  bond *Binder = NULL;
  bool BackStepping = false;

  *out << Verbose(0) << "Begin of DepthFirstSearchAnalysis" << endl;

  ResetAllBondsToUnused();
  ResetAllAtomNumbers();
  InitComponentNumbers();
  BackEdgeStack->ClearStack();
  while (Root != end) { // if there any atoms at all
    // (1) mark all edges unused, empty stack, set atom->GraphNr = 0 for all
    AtomStack->ClearStack();

    // put into new subgraph molecule and add this to list of subgraphs
    LeafWalker = new MoleculeLeafClass(LeafWalker);
    LeafWalker->Leaf = new molecule(elemente);
    LeafWalker->Leaf->AddCopyAtom(Root);

    OldGraphNr = CurrentGraphNr;
    Walker = Root;
    do { // (10)
      do { // (2) set number and Lowpoint of Atom to i, increase i, push current atom
        if (!BackStepping) { // if we don't just return from (8)
          Walker->GraphNr = CurrentGraphNr;
          Walker->LowpointNr = CurrentGraphNr;
          *out << Verbose(1) << "Setting Walker[" << Walker->Name << "]'s number to " << Walker->GraphNr << " with Lowpoint " << Walker->LowpointNr << "." << endl;
          AtomStack->Push(Walker);
          CurrentGraphNr++;
        }
        do { // (3) if Walker has no unused egdes, go to (5)
          BackStepping = false; // reset backstepping flag for (8)
          if (Binder == NULL) // if we don't just return from (11), Binder is already set to next unused
            Binder = FindNextUnused(Walker);
          if (Binder == NULL)
            break;
          *out << Verbose(2) << "Current Unused Bond is " << *Binder << "." << endl;
          // (4) Mark Binder used, ...
          Binder->MarkUsed(black);
          OtherAtom = Binder->GetOtherAtom(Walker);
          *out << Verbose(2) << "(4) OtherAtom is " << OtherAtom->Name << "." << endl;
          if (OtherAtom->GraphNr != -1) {
            // (4a) ... if "other" atom has been visited (GraphNr != 0), set lowpoint to minimum of both, go to (3)
            Binder->Type = BackEdge;
            BackEdgeStack->Push(Binder);
            Walker->LowpointNr = ( Walker->LowpointNr < OtherAtom->GraphNr ) ? Walker->LowpointNr : OtherAtom->GraphNr;
            *out << Verbose(3) << "(4a) Visited: Setting Lowpoint of Walker[" << Walker->Name << "] to " << Walker->LowpointNr << "." << endl;
          } else {
            // (4b) ... otherwise set OtherAtom as Ancestor of Walker and Walker as OtherAtom, go to (2)
            Binder->Type = TreeEdge;
            OtherAtom->Ancestor = Walker;
            Walker = OtherAtom;
            *out << Verbose(3) << "(4b) Not Visited: OtherAtom[" << OtherAtom->Name << "]'s Ancestor is now " << OtherAtom->Ancestor->Name << ", Walker is OtherAtom " << OtherAtom->Name << "." << endl;
            break;
          }
          Binder = NULL;
        } while (1);  // (3)
        if (Binder == NULL) {
          *out << Verbose(2) << "No more Unused Bonds." << endl;
          break;
        } else
          Binder = NULL;
      } while (1);  // (2)

      // if we came from backstepping, yet there were no more unused bonds, we end up here with no Ancestor, because Walker is Root! Then we are finished!
      if ((Walker == Root) && (Binder == NULL))
        break;

      // (5) if Ancestor of Walker is ...
      *out << Verbose(1) << "(5) Number of Walker[" << Walker->Name << "]'s Ancestor[" << Walker->Ancestor->Name << "] is " << Walker->Ancestor->GraphNr << "." << endl;
      if (Walker->Ancestor->GraphNr != Root->GraphNr) {
        // (6)  (Ancestor of Walker is not Root)
        if (Walker->LowpointNr < Walker->Ancestor->GraphNr) {
          // (6a) set Ancestor's Lowpoint number to minimum of of its Ancestor and itself, go to Step(8)
          Walker->Ancestor->LowpointNr = (Walker->Ancestor->LowpointNr < Walker->LowpointNr) ? Walker->Ancestor->LowpointNr : Walker->LowpointNr;
          *out << Verbose(2) << "(6) Setting Walker[" << Walker->Name << "]'s Ancestor[" << Walker->Ancestor->Name << "]'s Lowpoint to " << Walker->Ancestor->LowpointNr << "." << endl;
        } else {
          // (7) (Ancestor of Walker is a separating vertex, remove all from stack till Walker (including), these and Ancestor form a component
          Walker->Ancestor->SeparationVertex = true;
          *out << Verbose(2) << "(7) Walker[" << Walker->Name << "]'s Ancestor[" << Walker->Ancestor->Name << "]'s is a separating vertex, creating component." << endl;
          SetNextComponentNumber(Walker->Ancestor, ComponentNumber);
          *out << Verbose(3) << "(7) Walker[" << Walker->Name << "]'s Ancestor's Compont is " << ComponentNumber << "." << endl;
          SetNextComponentNumber(Walker, ComponentNumber);
          *out << Verbose(3) << "(7) Walker[" << Walker->Name << "]'s Compont is " << ComponentNumber << "." << endl;
          do {
            OtherAtom = AtomStack->PopLast();
            LeafWalker->Leaf->AddCopyAtom(OtherAtom);
            SetNextComponentNumber(OtherAtom, ComponentNumber);
            *out << Verbose(3) << "(7) Other[" << OtherAtom->Name << "]'s Compont is " << ComponentNumber << "." << endl;
          } while (OtherAtom != Walker);
          ComponentNumber++;
        }
        // (8) Walker becomes its Ancestor, go to (3)
        *out << Verbose(2) << "(8) Walker[" << Walker->Name << "] is now its Ancestor " << Walker->Ancestor->Name << ", backstepping. " << endl;
        Walker = Walker->Ancestor;
        BackStepping = true;
      }
      if (!BackStepping) {  // coming from (8) want to go to (3)
        // (9) remove all from stack till Walker (including), these and Root form a component
        AtomStack->Output(out);
        SetNextComponentNumber(Root, ComponentNumber);
        *out << Verbose(3) << "(9) Root[" << Root->Name << "]'s Component is " << ComponentNumber << "." << endl;
        SetNextComponentNumber(Walker, ComponentNumber);
        *out << Verbose(3) << "(9) Walker[" << Walker->Name << "]'s Component is " << ComponentNumber << "." << endl;
        do {
          OtherAtom = AtomStack->PopLast();
          LeafWalker->Leaf->AddCopyAtom(OtherAtom);
          SetNextComponentNumber(OtherAtom, ComponentNumber);
          *out << Verbose(3) << "(7) Other[" << OtherAtom->Name << "]'s Compont is " << ComponentNumber << "." << endl;
        } while (OtherAtom != Walker);
        ComponentNumber++;

        // (11) Root is separation vertex,  set Walker to Root and go to (4)
        Walker = Root;
        Binder = FindNextUnused(Walker);
        *out << Verbose(1) << "(10) Walker is Root[" << Root->Name << "], next Unused Bond is " << Binder << "." << endl;
        if (Binder != NULL) { // Root is separation vertex
          *out << Verbose(1) << "(11) Root is a separation vertex." << endl;
          Walker->SeparationVertex = true;
        }
      }
    } while ((BackStepping) || (Binder != NULL)); // (10) halt only if Root has no unused edges

    // From OldGraphNr to CurrentGraphNr ranges an disconnected subgraph
    *out << Verbose(0) << "Disconnected subgraph ranges from " << OldGraphNr << " to " << CurrentGraphNr << "." << endl;
    LeafWalker->Leaf->Output(out);
    *out << endl;

    // step on to next root
    while ((Root != end) && (Root->GraphNr != -1)) {
      //*out << Verbose(1) << "Current next subgraph root candidate is " << Root->Name << "." << endl;
      if (Root->GraphNr != -1) // if already discovered, step on
        Root = Root->next;
    }
  }
  // set cyclic bond criterium on "same LP" basis
  Binder = first;
  while(Binder->next != last) {
    Binder = Binder->next;
    if (Binder->rightatom->LowpointNr == Binder->leftatom->LowpointNr) { // cyclic ??
      Binder->Cyclic = true;
      NoCyclicBonds++;
    }
  }


  *out << Verbose(1) << "Final graph info for each atom is:" << endl;
  Walker = start;
  while (Walker->next != end) {
    Walker = Walker->next;
    *out << Verbose(2) << "Atom " << Walker->Name << " is " << ((Walker->SeparationVertex) ? "a" : "not a") << " separation vertex, components are ";
    OutputComponentNumber(out, Walker);
    *out << " with Lowpoint " << Walker->LowpointNr << " and Graph Nr. " << Walker->GraphNr << "." << endl;
  }

  *out << Verbose(1) << "Final graph info for each bond is:" << endl;
  Binder = first;
  while(Binder->next != last) {
    Binder = Binder->next;
    *out << Verbose(2) << ((Binder->Type == TreeEdge) ? "TreeEdge " : "BackEdge ") << *Binder << ": <";
    *out << ((Binder->leftatom->SeparationVertex) ? "SP," : "") << "L" << Binder->leftatom->LowpointNr << " G" << Binder->leftatom->GraphNr << " Comp.";
    OutputComponentNumber(out, Binder->leftatom);
    *out << " ===  ";
    *out << ((Binder->rightatom->SeparationVertex) ? "SP," : "") << "L" << Binder->rightatom->LowpointNr << " G" << Binder->rightatom->GraphNr << " Comp.";
    OutputComponentNumber(out, Binder->rightatom);
    *out << ">." << endl;
    if (Binder->Cyclic) // cyclic ??
      *out << Verbose(3) << "Lowpoint at each side are equal: CYCLIC!" << endl;
  }

  // free all and exit
  delete(AtomStack);
  *out << Verbose(0) << "End of DepthFirstSearchAnalysis" << endl;
  return SubGraphs;
};

/** Analyses the cycles found and returns minimum of all cycle lengths.
 * We begin with a list of Back edges found during DepthFirstSearchAnalysis(). We go through this list - one end is the Root,
 * the other our initial Walker - and do a Breadth First Search for the Root. We mark down each Predecessor and as soon as
 * we have found the Root via BFS, we may climb back the closed cycle via the Predecessors. Thereby we mark atoms and bonds
 * as cyclic and print out the cycles.
 * \param *out output stream for debugging
 * \param *BackEdgeStack stack with all back edges found during DFS scan. Beware: This stack contains the bonds from the total molecule, not from the subgraph!
 * \param *&MinimumRingSize contains smallest ring size in molecular structure on return or -1 if no rings were found, if set is maximum search distance
 * \todo BFS from the not-same-LP to find back to starting point of tributary cycle over more than one bond
 */
void molecule::CyclicStructureAnalysis(ofstream *out, class StackClass<bond *> *  BackEdgeStack, int *&MinimumRingSize)
{
  atom **PredecessorList = (atom **) Malloc(sizeof(atom *)*AtomCount, "molecule::CyclicStructureAnalysis: **PredecessorList");
  int *ShortestPathList = (int *) Malloc(sizeof(int)*AtomCount, "molecule::CyclicStructureAnalysis: *ShortestPathList");
  enum Shading *ColorList = (enum Shading *) Malloc(sizeof(enum Shading)*AtomCount, "molecule::CyclicStructureAnalysis: *ColorList");
  class StackClass<atom *> *BFSStack = new StackClass<atom *> (AtomCount);   // will hold the current ring
  class StackClass<atom *> *TouchedStack = new StackClass<atom *> (AtomCount);   // contains all "touched" atoms (that need to be reset after BFS loop)
  atom *Walker = NULL, *OtherAtom = NULL, *Root = NULL;
  bond *Binder = NULL, *BackEdge = NULL;
  int RingSize, NumCycles, MinRingSize = -1;

  // initialise each vertex as white with no predecessor, empty queue, color Root lightgray
  for (int i=AtomCount;i--;) {
    PredecessorList[i] = NULL;
    ShortestPathList[i] = -1;
    ColorList[i] = white;
  }

  *out << Verbose(1) << "Back edge list - ";
  BackEdgeStack->Output(out);

  *out << Verbose(1) << "Analysing cycles ... " << endl;
  NumCycles = 0;
  while (!BackEdgeStack->IsEmpty()) {
    BackEdge = BackEdgeStack->PopFirst();
    // this is the target
    Root = BackEdge->leftatom;
    // this is the source point
    Walker = BackEdge->rightatom;
    ShortestPathList[Walker->nr] = 0;
    BFSStack->ClearStack();  // start with empty BFS stack
    BFSStack->Push(Walker);
    TouchedStack->Push(Walker);
    *out << Verbose(1) << "---------------------------------------------------------------------------------------------------------" << endl;
    OtherAtom = NULL;
    do {  // look for Root
      Walker = BFSStack->PopFirst();
      *out << Verbose(2) << "Current Walker is " << *Walker << ", we look for SP to Root " << *Root << "." << endl;
      for(int i=0;i<NumberOfBondsPerAtom[Walker->nr];i++) {
        Binder = ListOfBondsPerAtom[Walker->nr][i];
        if (Binder != BackEdge) { // only walk along DFS spanning tree (otherwise we always find SP of one being backedge Binder)
          OtherAtom = Binder->GetOtherAtom(Walker);
#ifdef ADDHYDROGEN
          if (OtherAtom->type->Z != 1) {
#endif
            *out << Verbose(2) << "Current OtherAtom is: " << OtherAtom->Name << " for bond " << *Binder << "." << endl;
            if (ColorList[OtherAtom->nr] == white) {
              TouchedStack->Push(OtherAtom);
              ColorList[OtherAtom->nr] = lightgray;
              PredecessorList[OtherAtom->nr] = Walker;  // Walker is the predecessor
              ShortestPathList[OtherAtom->nr] = ShortestPathList[Walker->nr]+1;
              *out << Verbose(2) << "Coloring OtherAtom " << OtherAtom->Name << " lightgray, its predecessor is " << Walker->Name << " and its Shortest Path is " << ShortestPathList[OtherAtom->nr] << " egde(s) long." << endl;
              //if (ShortestPathList[OtherAtom->nr] < MinimumRingSize[Walker->GetTrueFather()->nr]) { // Check for maximum distance
                *out << Verbose(3) << "Putting OtherAtom into queue." << endl;
                BFSStack->Push(OtherAtom);
              //}
            } else {
              *out << Verbose(3) << "Not Adding, has already been visited." << endl;
            }
            if (OtherAtom == Root)
              break;
#ifdef ADDHYDROGEN
          } else {
            *out << Verbose(2) << "Skipping hydrogen atom " << *OtherAtom << "." << endl;
            ColorList[OtherAtom->nr] = black;
          }
#endif
        } else {
          *out << Verbose(2) << "Bond " << *Binder << " not Visiting, is the back edge." << endl;
        }
      }
      ColorList[Walker->nr] = black;
      *out << Verbose(1) << "Coloring Walker " << Walker->Name << " black." << endl;
      if (OtherAtom == Root) { // if we have found the root, check whether this cycle wasn't already found beforehand
        // step through predecessor list
        while (OtherAtom != BackEdge->rightatom) {
          if (!OtherAtom->GetTrueFather()->IsCyclic)  // if one bond in the loop is not marked as cyclic, we haven't found this cycle yet
            break;
          else
            OtherAtom = PredecessorList[OtherAtom->nr];
        }
        if (OtherAtom == BackEdge->rightatom) { // if each atom in found cycle is cyclic, loop's been found before already
          *out << Verbose(3) << "This cycle was already found before, skipping and removing seeker from search." << endl;\
          do {
            OtherAtom = TouchedStack->PopLast();
            if (PredecessorList[OtherAtom->nr] == Walker) {
              *out << Verbose(4) << "Removing " << *OtherAtom << " from lists and stacks." << endl;
              PredecessorList[OtherAtom->nr] = NULL;
              ShortestPathList[OtherAtom->nr] = -1;
              ColorList[OtherAtom->nr] = white;
              BFSStack->RemoveItem(OtherAtom);
            }
          } while ((!TouchedStack->IsEmpty()) && (PredecessorList[OtherAtom->nr] == NULL));
          TouchedStack->Push(OtherAtom);  // last was wrongly popped
          OtherAtom = BackEdge->rightatom; // set to not Root
        } else
          OtherAtom = Root;
      }
    } while ((!BFSStack->IsEmpty()) && (OtherAtom != Root) && (OtherAtom != NULL)); // || (ShortestPathList[OtherAtom->nr] < MinimumRingSize[Walker->GetTrueFather()->nr])));

    if (OtherAtom == Root) {
      // now climb back the predecessor list and thus find the cycle members
      NumCycles++;
      RingSize = 1;
      Root->GetTrueFather()->IsCyclic = true;
      *out << Verbose(1) << "Found ring contains: ";
      Walker = Root;
      while (Walker != BackEdge->rightatom) {
        *out << Walker->Name << " <-> ";
        Walker = PredecessorList[Walker->nr];
        Walker->GetTrueFather()->IsCyclic = true;
        RingSize++;
      }
      *out << Walker->Name << "  with a length of " << RingSize << "." << endl << endl;
      // walk through all and set MinimumRingSize
      Walker = Root;
      MinimumRingSize[Walker->GetTrueFather()->nr] = RingSize;
      while (Walker != BackEdge->rightatom) {
        Walker = PredecessorList[Walker->nr];
        if (RingSize < MinimumRingSize[Walker->GetTrueFather()->nr])
          MinimumRingSize[Walker->GetTrueFather()->nr] = RingSize;
      }
      if ((RingSize < MinRingSize) || (MinRingSize == -1))
        MinRingSize = RingSize;
    } else {
      *out << Verbose(1) << "No ring containing " << *Root << " with length equal to or smaller than " << MinimumRingSize[Walker->GetTrueFather()->nr] << " found." << endl;
    }

    // now clean the lists
    while (!TouchedStack->IsEmpty()){
      Walker = TouchedStack->PopFirst();
      PredecessorList[Walker->nr] = NULL;
      ShortestPathList[Walker->nr] = -1;
      ColorList[Walker->nr] = white;
    }
  }
  if (MinRingSize != -1) {
    // go over all atoms
    Root = start;
    while(Root->next != end) {
      Root = Root->next;

      if (MinimumRingSize[Root->GetTrueFather()->nr] == AtomCount) { // check whether MinimumRingSize is set, if not BFS to next where it is
        Walker = Root;
        ShortestPathList[Walker->nr] = 0;
        BFSStack->ClearStack();  // start with empty BFS stack
        BFSStack->Push(Walker);
        TouchedStack->Push(Walker);
        //*out << Verbose(1) << "---------------------------------------------------------------------------------------------------------" << endl;
        OtherAtom = Walker;
        while (OtherAtom != NULL) {  // look for Root
          Walker = BFSStack->PopFirst();
          //*out << Verbose(2) << "Current Walker is " << *Walker << ", we look for SP to Root " << *Root << "." << endl;
          for(int i=0;i<NumberOfBondsPerAtom[Walker->nr];i++) {
            Binder = ListOfBondsPerAtom[Walker->nr][i];
            if ((Binder != BackEdge) || (NumberOfBondsPerAtom[Walker->nr] == 1)) { // only walk along DFS spanning tree (otherwise we always find SP of 1 being backedge Binder), but terminal hydrogens may be connected via backedge, hence extra check
              OtherAtom = Binder->GetOtherAtom(Walker);
              //*out << Verbose(2) << "Current OtherAtom is: " << OtherAtom->Name << " for bond " << *Binder << "." << endl;
              if (ColorList[OtherAtom->nr] == white) {
                TouchedStack->Push(OtherAtom);
                ColorList[OtherAtom->nr] = lightgray;
                PredecessorList[OtherAtom->nr] = Walker;  // Walker is the predecessor
                ShortestPathList[OtherAtom->nr] = ShortestPathList[Walker->nr]+1;
                //*out << Verbose(2) << "Coloring OtherAtom " << OtherAtom->Name << " lightgray, its predecessor is " << Walker->Name << " and its Shortest Path is " << ShortestPathList[OtherAtom->nr] << " egde(s) long." << endl;
                if (OtherAtom->GetTrueFather()->IsCyclic) { // if the other atom is connected to a ring
                  MinimumRingSize[Root->GetTrueFather()->nr] = ShortestPathList[OtherAtom->nr]+MinimumRingSize[OtherAtom->GetTrueFather()->nr];
                  OtherAtom = NULL; //break;
                  break;
                } else
                  BFSStack->Push(OtherAtom);
              } else {
                //*out << Verbose(3) << "Not Adding, has already been visited." << endl;
              }
            } else {
              //*out << Verbose(3) << "Not Visiting, is a back edge." << endl;
            }
          }
          ColorList[Walker->nr] = black;
          //*out << Verbose(1) << "Coloring Walker " << Walker->Name << " black." << endl;
        }

        // now clean the lists
        while (!TouchedStack->IsEmpty()){
          Walker = TouchedStack->PopFirst();
          PredecessorList[Walker->nr] = NULL;
          ShortestPathList[Walker->nr] = -1;
          ColorList[Walker->nr] = white;
        }
      }
      *out << Verbose(1) << "Minimum ring size of " << *Root << " is " << MinimumRingSize[Root->GetTrueFather()->nr] << "." << endl;
    }
    *out << Verbose(1) << "Minimum ring size is " << MinRingSize << ", over " << NumCycles << " cycles total." << endl;
  } else
    *out << Verbose(1) << "No rings were detected in the molecular structure." << endl;

  Free((void **)&PredecessorList, "molecule::CyclicStructureAnalysis: **PredecessorList");
  Free((void **)&ShortestPathList, "molecule::CyclicStructureAnalysis: **ShortestPathList");
  Free((void **)&ColorList, "molecule::CyclicStructureAnalysis: **ColorList");
  delete(BFSStack);
};

/** Sets the next component number.
 * This is O(N) as the number of bonds per atom is bound.
 * \param *vertex atom whose next atom::*ComponentNr is to be set
 * \param nr number to use
 */
void molecule::SetNextComponentNumber(atom *vertex, int nr)
{
  int i=0;
  if (vertex != NULL) {
    for(;i<NumberOfBondsPerAtom[vertex->nr];i++) {
      if (vertex->ComponentNr[i] == -1) {   // check if not yet used
        vertex->ComponentNr[i] = nr;
        break;
      }
      else if (vertex->ComponentNr[i] == nr) // if number is already present, don't add another time
        break;  // breaking here will not cause error!
    }
    if (i == NumberOfBondsPerAtom[vertex->nr])
      cerr << "Error: All Component entries are already occupied!" << endl;
  } else
      cerr << "Error: Given vertex is NULL!" << endl;
};

/** Output a list of flags, stating whether the bond was visited or not.
 * \param *out output stream for debugging
 */
void molecule::OutputComponentNumber(ofstream *out, atom *vertex)
{
  for(int i=0;i<NumberOfBondsPerAtom[vertex->nr];i++)
    *out << vertex->ComponentNr[i] << "  ";
};

/** Allocates memory for all atom::*ComponentNr in this molecule and sets each entry to -1.
 */
void molecule::InitComponentNumbers()
{
  atom *Walker = start;
  while(Walker->next != end) {
    Walker = Walker->next;
    if (Walker->ComponentNr != NULL)
      Free((void **)&Walker->ComponentNr, "molecule::InitComponentNumbers: **Walker->ComponentNr");
    Walker->ComponentNr = (int *) Malloc(sizeof(int)*NumberOfBondsPerAtom[Walker->nr], "molecule::InitComponentNumbers: *Walker->ComponentNr");
    for (int i=NumberOfBondsPerAtom[Walker->nr];i--;)
      Walker->ComponentNr[i] = -1;
  }
};

/** Returns next unused bond for this atom \a *vertex or NULL of none exists.
 * \param *vertex atom to regard
 * \return bond class or NULL
 */
bond * molecule::FindNextUnused(atom *vertex)
{
  for(int i=0;i<NumberOfBondsPerAtom[vertex->nr];i++)
    if (ListOfBondsPerAtom[vertex->nr][i]->IsUsed() == white)
      return(ListOfBondsPerAtom[vertex->nr][i]);
  return NULL;
};

/** Resets bond::Used flag of all bonds in this molecule.
 * \return true - success, false - -failure
 */
void molecule::ResetAllBondsToUnused()
{
  bond *Binder = first;
  while (Binder->next != last) {
    Binder = Binder->next;
    Binder->ResetUsed();
  }
};

/** Resets atom::nr to -1 of all atoms in this molecule.
 */
void molecule::ResetAllAtomNumbers()
{
  atom *Walker = start;
  while (Walker->next != end) {
    Walker = Walker->next;
    Walker->GraphNr  = -1;
  }
};

/** Output a list of flags, stating whether the bond was visited or not.
 * \param *out output stream for debugging
 * \param *list
 */
void OutputAlreadyVisited(ofstream *out, int *list)
{
  *out << Verbose(4) << "Already Visited Bonds:\t";
  for(int i=1;i<=list[0];i++) *out << Verbose(0) << list[i] << "  ";
  *out << endl;
};

/** Estimates by educated guessing (using upper limit) the expected number of fragments.
 * The upper limit is
 * \f[
 *  n = N \cdot C^k
 * \f]
 * where \f$C=2^c\f$ and c is the maximum bond degree over N number of atoms.
 * \param *out output stream for debugging
 * \param order bond order k
 * \return number n of fragments
 */
int molecule::GuesstimateFragmentCount(ofstream *out, int order)
{
  int c = 0;
  int FragmentCount;
  // get maximum bond degree
  atom *Walker = start;
  while (Walker->next != end) {
    Walker = Walker->next;
    c = (NumberOfBondsPerAtom[Walker->nr] > c) ? NumberOfBondsPerAtom[Walker->nr] : c;
  }
  FragmentCount = NoNonHydrogen*(1 << (c*order));
  *out << Verbose(1) << "Upper limit for this subgraph is " << FragmentCount << " for " << NoNonHydrogen << " non-H atoms with maximum bond degree of " << c << "." << endl;
  return FragmentCount;
};

/** Scans a single line for number and puts them into \a KeySet.
 * \param *out output stream for debugging
 * \param *buffer buffer to scan
 * \param &CurrentSet filled KeySet on return
 * \return true - at least one valid atom id parsed, false - CurrentSet is empty
 */
bool molecule::ScanBufferIntoKeySet(ofstream *out, char *buffer, KeySet &CurrentSet)
{
  stringstream line;
  int AtomNr;
  int status = 0;

  line.str(buffer);
  while (!line.eof()) {
    line >> AtomNr;
    if ((AtomNr >= 0) && (AtomNr < AtomCount)) {
      CurrentSet.insert(AtomNr);  // insert at end, hence in same order as in file!
      status++;
    } // else it's "-1" or else and thus must not be added
  }
  *out << Verbose(1) << "The scanned KeySet is ";
  for(KeySet::iterator runner = CurrentSet.begin(); runner != CurrentSet.end(); runner++) {
    *out << (*runner) << "\t";
  }
  *out << endl;
  return (status != 0);
};

/** Parses the KeySet file and fills \a *FragmentList from the known molecule structure.
 * Does two-pass scanning:
 * -# Scans the keyset file and initialises a temporary graph
 * -# Scans TEFactors file and sets the TEFactor of each key set in the temporary graph accordingly
 * Finally, the temporary graph is inserted into the given \a FragmentList for return.
 * \param *out output stream for debugging
 * \param *path path to file
 * \param *FragmentList empty, filled on return
 * \return true - parsing successfully, false - failure on parsing (FragmentList will be NULL)
 */
bool molecule::ParseKeySetFile(ofstream *out, char *path, Graph *&FragmentList)
{
  bool status = true;
  ifstream InputFile;
  stringstream line;
  GraphTestPair testGraphInsert;
  int NumberOfFragments = 0;
  double TEFactor;
  char *filename = (char *) Malloc(sizeof(char)*MAXSTRINGSIZE, "molecule::ParseKeySetFile - filename");

  if (FragmentList == NULL) { // check list pointer
    FragmentList = new Graph;
  }

  // 1st pass: open file and read
  *out << Verbose(1) << "Parsing the KeySet file ... " << endl;
  sprintf(filename, "%s/%s%s", path, FRAGMENTPREFIX, KEYSETFILE);
  InputFile.open(filename);
  if (InputFile != NULL) {
    // each line represents a new fragment
    char *buffer = (char *) Malloc(sizeof(char)*MAXSTRINGSIZE, "molecule::ParseKeySetFile - *buffer");
    // 1. parse keysets and insert into temp. graph
    while (!InputFile.eof()) {
      InputFile.getline(buffer, MAXSTRINGSIZE);
      KeySet CurrentSet;
      if ((strlen(buffer) > 0) && (ScanBufferIntoKeySet(out, buffer, CurrentSet))) {  // if at least one valid atom was added, write config
        testGraphInsert = FragmentList->insert(GraphPair (CurrentSet,pair<int,double>(NumberOfFragments++,1)));  // store fragment number and current factor
        if (!testGraphInsert.second) {
          cerr << "KeySet file must be corrupt as there are two equal key sets therein!" << endl;
        }
      }
    }
    // 2. Free and done
    InputFile.close();
    InputFile.clear();
    Free((void **)&buffer, "molecule::ParseKeySetFile - *buffer");
    *out << Verbose(1) << "done." << endl;
  } else {
    *out << Verbose(1) << "File " << filename << " not found." << endl;
    status = false;
  }

  // 2nd pass: open TEFactors file and read
  *out << Verbose(1) << "Parsing the TEFactors file ... " << endl;
  sprintf(filename, "%s/%s%s", path, FRAGMENTPREFIX, TEFACTORSFILE);
  InputFile.open(filename);
  if (InputFile != NULL) {
    // 3. add found TEFactors to each keyset
    NumberOfFragments = 0;
    for(Graph::iterator runner = FragmentList->begin();runner != FragmentList->end(); runner++) {
      if (!InputFile.eof()) {
        InputFile >> TEFactor;
        (*runner).second.second = TEFactor;
        *out << Verbose(2) << "Setting " << ++NumberOfFragments << " fragment's TEFactor to " << (*runner).second.second << "." << endl;
      } else {
        status = false;
        break;
      }
    }
    // 4. Free and done
    InputFile.close();
    *out << Verbose(1) << "done." << endl;
  } else {
    *out << Verbose(1) << "File " << filename << " not found." << endl;
    status = false;
  }

  // free memory
  Free((void **)&filename, "molecule::ParseKeySetFile - filename");

  return status;
};

/** Stores keysets and TEFactors to file.
 * \param *out output stream for debugging
 * \param KeySetList Graph with Keysets and factors
 * \param *path path to file
 * \return true - file written successfully, false - writing failed
 */
bool molecule::StoreKeySetFile(ofstream *out, Graph &KeySetList, char *path)
{
  ofstream output;
  bool status =  true;
  string line;

  // open KeySet file
  line = path;
  line.append("/");
  line += FRAGMENTPREFIX;
  line += KEYSETFILE;
  output.open(line.c_str(), ios::out);
  *out << Verbose(1) << "Saving key sets of the total graph ... ";
  if(output != NULL) {
    for(Graph::iterator runner = KeySetList.begin(); runner != KeySetList.end(); runner++) {
      for (KeySet::iterator sprinter = (*runner).first.begin();sprinter != (*runner).first.end(); sprinter++) {
        if (sprinter != (*runner).first.begin())
          output << "\t";
        output << *sprinter;
      }
      output << endl;
    }
    *out << "done." << endl;
  } else {
    cerr << "Unable to open " << line << " for writing keysets!" << endl;
    status = false;
  }
  output.close();
  output.clear();

  // open TEFactors file
  line = path;
  line.append("/");
  line += FRAGMENTPREFIX;
  line += TEFACTORSFILE;
  output.open(line.c_str(), ios::out);
  *out << Verbose(1) << "Saving TEFactors of the total graph ... ";
  if(output != NULL) {
    for(Graph::iterator runner = KeySetList.begin(); runner != KeySetList.end(); runner++)
      output << (*runner).second.second << endl;
    *out << Verbose(1) << "done." << endl;
  } else {
    *out << Verbose(1) << "failed to open " << line << "." << endl;
    status = false;
  }
  output.close();

  return status;
};

/** Storing the bond structure of a molecule to file.
 * Simply stores Atom::nr and then the Atom::nr of all bond partners per line.
 * \param *out output stream for debugging
 * \param *path path to file
 * \return true - file written successfully, false - writing failed
 */
bool molecule::StoreAdjacencyToFile(ofstream *out, char *path)
{
  ofstream AdjacencyFile;
  atom *Walker = NULL;
  stringstream line;
  bool status = true;

  line << path << "/" << FRAGMENTPREFIX << ADJACENCYFILE;
  AdjacencyFile.open(line.str().c_str(), ios::out);
  *out << Verbose(1) << "Saving adjacency list ... ";
  if (AdjacencyFile != NULL) {
    Walker = start;
    while(Walker->next != end) {
      Walker = Walker->next;
      AdjacencyFile << Walker->nr << "\t";
      for (int i=0;i<NumberOfBondsPerAtom[Walker->nr];i++)
        AdjacencyFile << ListOfBondsPerAtom[Walker->nr][i]->GetOtherAtom(Walker)->nr << "\t";
      AdjacencyFile << endl;
    }
    AdjacencyFile.close();
    *out << Verbose(1) << "done." << endl;
  } else {
    *out << Verbose(1) << "failed to open file " << line.str() << "." << endl;
    status = false;
  }

  return status;
};

/** Checks contents of adjacency file against bond structure in structure molecule.
 * \param *out output stream for debugging
 * \param *path path to file
 * \param **ListOfAtoms allocated (molecule::AtomCount) and filled lookup table for ids (Atom::nr) to *Atom
 * \return true - structure is equal, false - not equivalence
 */
bool molecule::CheckAdjacencyFileAgainstMolecule(ofstream *out, char *path, atom **ListOfAtoms)
{
  ifstream File;
  stringstream filename;
  bool status = true;
  char *buffer = (char *) Malloc(sizeof(char)*MAXSTRINGSIZE, "molecule::CheckAdjacencyFileAgainstMolecule: *buffer");

  filename << path << "/" << FRAGMENTPREFIX << ADJACENCYFILE;
  File.open(filename.str().c_str(), ios::out);
  *out << Verbose(1) << "Looking at bond structure stored in adjacency file and comparing to present one ... ";
  if (File != NULL) {
    // allocate storage structure
    int NonMatchNumber = 0;   // will number of atoms with differing bond structure
    int *CurrentBonds = (int *) Malloc(sizeof(int)*8, "molecule::CheckAdjacencyFileAgainstMolecule - CurrentBonds"); // contains parsed bonds of current atom
    int CurrentBondsOfAtom;

    // Parse the file line by line and count the bonds
    while (!File.eof()) {
      File.getline(buffer, MAXSTRINGSIZE);
      stringstream line;
      line.str(buffer);
      int AtomNr = -1;
      line >> AtomNr;
      CurrentBondsOfAtom = -1; // we count one too far due to line end
      // parse into structure
      if ((AtomNr >= 0) && (AtomNr < AtomCount)) {
        while (!line.eof())
          line >> CurrentBonds[ ++CurrentBondsOfAtom ];
        // compare against present bonds
        //cout << Verbose(2) << "Walker is " << *Walker << ", bond partners: ";
        if (CurrentBondsOfAtom == NumberOfBondsPerAtom[AtomNr]) {
          for(int i=0;i<NumberOfBondsPerAtom[AtomNr];i++) {
            int id = ListOfBondsPerAtom[AtomNr][i]->GetOtherAtom(ListOfAtoms[AtomNr])->nr;
            int j = 0;
            for (;(j<CurrentBondsOfAtom) && (CurrentBonds[j++] != id);); // check against all parsed bonds
            if (CurrentBonds[j-1] != id) { // no match ? Then mark in ListOfAtoms
              ListOfAtoms[AtomNr] = NULL;
              NonMatchNumber++;
              status = false;
              //out << "[" << id << "]\t";
            } else {
              //out << id << "\t";
            }
          }
          //out << endl;
        } else {
          *out << "Number of bonds for Atom " << *ListOfAtoms[AtomNr] << " does not match, parsed " << CurrentBondsOfAtom << " against " << NumberOfBondsPerAtom[AtomNr] << "." << endl;
          status = false;
        }
      }
    }
    File.close();
    File.clear();
    if (status) { // if equal we parse the KeySetFile
      *out << Verbose(1) << "done: Equal." << endl;
      status = true;
    } else
      *out << Verbose(1) << "done: Not equal by " << NonMatchNumber << " atoms." << endl;
    Free((void **)&CurrentBonds, "molecule::CheckAdjacencyFileAgainstMolecule - **CurrentBonds");
  } else {
    *out << Verbose(1) << "Adjacency file not found." << endl;
    status = false;
  }
  *out << endl;
  Free((void **)&buffer, "molecule::CheckAdjacencyFileAgainstMolecule: *buffer");

  return status;
};

/** Checks whether the OrderAtSite is still below \a Order at some site.
 * \param *out output stream for debugging
 * \param *AtomMask defines true/false per global Atom::nr to mask in/out each nuclear site, used to activate given number of site to increment order adaptively
 * \param *GlobalKeySetList list of keysets with global ids (valid in "this" molecule) needed for adaptive increase
 * \param Order desired Order if positive, desired exponent in threshold criteria if negative (0 is single-step)
 * \param *MinimumRingSize array of max. possible order to avoid loops
 * \param *path path to ENERGYPERFRAGMENT file (may be NULL if Order is non-negative)
 * \return true - needs further fragmentation, false - does not need fragmentation
 */
bool molecule::CheckOrderAtSite(ofstream *out, bool *AtomMask, Graph *GlobalKeySetList, int Order, int *MinimumRingSize, char *path)
{
  atom *Walker = start;
  bool status = false;
  ifstream InputFile;

  // initialize mask list
  for(int i=AtomCount;i--;)
    AtomMask[i] = false;

  if (Order < 0) { // adaptive increase of BondOrder per site
    if (AtomMask[AtomCount] == true)  // break after one step
      return false;
    // parse the EnergyPerFragment file
    char *buffer = (char *) Malloc(sizeof(char)*MAXSTRINGSIZE, "molecule::CheckOrderAtSite: *buffer");
    sprintf(buffer, "%s/%s%s.dat", path, FRAGMENTPREFIX, ENERGYPERFRAGMENT);
    InputFile.open(buffer, ios::in);
    if ((InputFile != NULL) && (GlobalKeySetList != NULL)) {
      // transmorph graph keyset list into indexed KeySetList
      map<int,KeySet> IndexKeySetList;
      for(Graph::iterator runner = GlobalKeySetList->begin(); runner != GlobalKeySetList->end(); runner++) {
        IndexKeySetList.insert( pair<int,KeySet>(runner->second.first,runner->first) );
      }
      int lines = 0;
      // count the number of lines, i.e. the number of fragments
      InputFile.getline(buffer, MAXSTRINGSIZE); // skip comment lines
      InputFile.getline(buffer, MAXSTRINGSIZE);
      while(!InputFile.eof()) {
        InputFile.getline(buffer, MAXSTRINGSIZE);
        lines++;
      }
      //*out << Verbose(2) << "Scanned " << lines-1 << " lines." << endl;   // one endline too much
      InputFile.clear();
      InputFile.seekg(ios::beg);
      map<int, pair<double,int> > AdaptiveCriteriaList;  // (Root No., (Value, Order)) !
      int No, FragOrder;
      double Value;
      // each line represents a fragment root (Atom::nr) id and its energy contribution
      InputFile.getline(buffer, MAXSTRINGSIZE); // skip comment lines
      InputFile.getline(buffer, MAXSTRINGSIZE);
      while(!InputFile.eof()) {
        InputFile.getline(buffer, MAXSTRINGSIZE);
        if (strlen(buffer) > 2) {
          //*out << Verbose(2) << "Scanning: " << buffer << endl;
          stringstream line(buffer);
          line >> FragOrder;
          line >> ws >> No;
          line >> ws >> Value; // skip time entry
          line >> ws >> Value;
          No -= 1;  // indices start at 1 in file, not 0
          //*out << Verbose(2) << " - yields (" << No << "," << Value << ", " << FragOrder << ")" << endl;

          // clean the list of those entries that have been superceded by higher order terms already
          map<int,KeySet>::iterator marker = IndexKeySetList.find(No);    // find keyset to Frag No.
          if (marker != IndexKeySetList.end()) {  // if found
            Value *= 1 + MYEPSILON*(*((*marker).second.begin()));     // in case of equal energies this makes em not equal without changing anything actually
            // as the smallest number in each set has always been the root (we use global id to keep the doubles away), seek smallest and insert into AtomMask
            pair <map<int, pair<double,int> >::iterator, bool> InsertedElement = AdaptiveCriteriaList.insert( make_pair(*((*marker).second.begin()), pair<double,int>( fabs(Value), FragOrder) ));
            map<int, pair<double,int> >::iterator PresentItem = InsertedElement.first;
            if (!InsertedElement.second) { // this root is already present
              if ((*PresentItem).second.second < FragOrder)  // if order there is lower, update entry with higher-order term
                //if ((*PresentItem).second.first < (*runner).first)    // as higher-order terms are not always better, we skip this part (which would always include this site into adaptive increase)
                {  // if value is smaller, update value and order
                (*PresentItem).second.first = fabs(Value);
                (*PresentItem).second.second = FragOrder;
                *out << Verbose(2) << "Updated element (" <<  (*PresentItem).first << ",[" << (*PresentItem).second.first << "," << (*PresentItem).second.second << "])." << endl;
              } else {
                *out << Verbose(2) << "Did not update element " <<  (*PresentItem).first << " as " << FragOrder << " is less than or equal to " << (*PresentItem).second.second << "." << endl;
              }
            } else {
              *out << Verbose(2) << "Inserted element (" <<  (*PresentItem).first << ",[" << (*PresentItem).second.first << "," << (*PresentItem).second.second << "])." << endl;
            }
          } else {
            *out << Verbose(1) << "No Fragment under No. " << No << "found." << endl;
          }
        }
      }
      // then map back onto (Value, (Root Nr., Order)) (i.e. sorted by value to pick the highest ones)
      map<double, pair<int,int> > FinalRootCandidates;
      *out << Verbose(1) << "Root candidate list is: " << endl;
      for(map<int, pair<double,int> >::iterator runner = AdaptiveCriteriaList.begin(); runner != AdaptiveCriteriaList.end(); runner++) {
        Walker = FindAtom((*runner).first);
        if (Walker != NULL) {
          //if ((*runner).second.second >= Walker->AdaptiveOrder) { // only insert if this is an "active" root site for the current order
          if (!Walker->MaxOrder) {
            *out << Verbose(2) << "(" << (*runner).first << ",[" << (*runner).second.first << "," << (*runner).second.second << "])" << endl;
            FinalRootCandidates.insert( make_pair( (*runner).second.first, pair<int,int>((*runner).first, (*runner).second.second) ) );
          } else {
            *out << Verbose(2) << "Excluding (" << *Walker << ", " << (*runner).first << ",[" << (*runner).second.first << "," << (*runner).second.second << "]), as it has reached its maximum order." << endl;
          }
        } else {
          cerr << "Atom No. " << (*runner).second.first << " was not found in this molecule." << endl;
        }
      }
      // pick the ones still below threshold and mark as to be adaptively updated
      for(map<double, pair<int,int> >::iterator runner = FinalRootCandidates.upper_bound(pow(10.,Order)); runner != FinalRootCandidates.end(); runner++) {
        No = (*runner).second.first;
        Walker = FindAtom(No);
        //if (Walker->AdaptiveOrder < MinimumRingSize[Walker->nr]) {
          *out << Verbose(2) << "Root " << No << " is still above threshold (10^{" << Order <<"}: " << runner->first << ", setting entry " << No << " of Atom mask to true." << endl;
          AtomMask[No] = true;
          status = true;
        //} else
          //*out << Verbose(2) << "Root " << No << " is still above threshold (10^{" << Order <<"}: " << runner->first << ", however MinimumRingSize of " << MinimumRingSize[Walker->nr] << " does not allow further adaptive increase." << endl;
      }
      // close and done
      InputFile.close();
      InputFile.clear();
    } else {
      cerr << "Unable to parse " << buffer << " file, incrementing all." << endl;
      while (Walker->next != end) {
        Walker = Walker->next;
    #ifdef ADDHYDROGEN
        if (Walker->type->Z != 1) // skip hydrogen
    #endif
        {
          AtomMask[Walker->nr] = true;  // include all (non-hydrogen) atoms
          status = true;
        }
      }
    }
    Free((void **)&buffer, "molecule::CheckOrderAtSite: *buffer");
    // pick a given number of highest values and set AtomMask
  } else { // global increase of Bond Order
    while (Walker->next != end) {
      Walker = Walker->next;
  #ifdef ADDHYDROGEN
      if (Walker->type->Z != 1) // skip hydrogen
  #endif
      {
        AtomMask[Walker->nr] = true;  // include all (non-hydrogen) atoms
        if ((Order != 0) && (Walker->AdaptiveOrder < Order)) // && (Walker->AdaptiveOrder < MinimumRingSize[Walker->nr]))
          status = true;
      }
    }
    if ((Order == 0) && (AtomMask[AtomCount] == false))  // single stepping, just check
      status = true;

    if (!status) {
      if (Order == 0)
        *out << Verbose(1) << "Single stepping done." << endl;
      else
        *out << Verbose(1) << "Order at every site is already equal or above desired order " << Order << "." << endl;
    }
  }

  // print atom mask for debugging
  *out << "              ";
  for(int i=0;i<AtomCount;i++)
    *out << (i % 10);
  *out << endl << "Atom mask is: ";
  for(int i=0;i<AtomCount;i++)
    *out << (AtomMask[i] ? "t" : "f");
  *out << endl;

  return status;
};

/** Create a SortIndex to map from atomic labels to the sequence in which the atoms are given in the config file.
 * \param *out output stream for debugging
 * \param *&SortIndex Mapping array of size molecule::AtomCount
 * \return true - success, false - failure of SortIndex alloc
 */
bool molecule::CreateMappingLabelsToConfigSequence(ofstream *out, int *&SortIndex)
{
  element *runner = elemente->start;
  int AtomNo = 0;
  atom *Walker = NULL;

  if (SortIndex != NULL) {
    *out << Verbose(1) << "SortIndex is " << SortIndex << " and not NULL as expected." << endl;
    return false;
  }
  SortIndex = (int *) Malloc(sizeof(int)*AtomCount, "molecule::FragmentMolecule: *SortIndex");
  for(int i=AtomCount;i--;)
    SortIndex[i] = -1;
  while (runner->next != elemente->end) { // go through every element
    runner = runner->next;
    if (ElementsInMolecule[runner->Z]) { // if this element got atoms
      Walker = start;
      while (Walker->next != end) { // go through every atom of this element
        Walker = Walker->next;
        if (Walker->type->Z == runner->Z) // if this atom fits to element
          SortIndex[Walker->nr] = AtomNo++;
      }
    }
  }
  return true;
};

/** Performs a many-body bond order analysis for a given bond order.
 * -# parses adjacency, keysets and orderatsite files
 * -# performs DFS to find connected subgraphs (to leave this in was a design decision: might be useful later)
 * -# RootStack is created for every subgraph (here, later we implement the "update 10 sites with highest energ
y contribution", and that's why this consciously not done in the following loop)
 * -# in a loop over all subgraphs
 *  -# calls FragmentBOSSANOVA with this RootStack and within the subgraph molecule structure
 *  -# creates molecule (fragment)s from the returned keysets (StoreFragmentFromKeySet)
 * -# combines the generated molecule lists from all subgraphs
 * -# saves to disk: fragment configs, adjacency, orderatsite, keyset files
 * Note that as we split "this" molecule up into a list of subgraphs, i.e. a MoleculeListClass, we have two sets
 * of vertex indices: Global always means the index in "this" molecule, whereas local refers to the molecule or
 * subgraph in the MoleculeListClass.
 * \param *out output stream for debugging
 * \param Order up to how many neighbouring bonds a fragment contains in BondOrderScheme::BottumUp scheme
 * \param *configuration configuration for writing config files for each fragment
 * \return 1 - continue, 2 - stop (no fragmentation occured)
 */
int molecule::FragmentMolecule(ofstream *out, int Order, config *configuration)
{
  MoleculeListClass *BondFragments = NULL;
  int *SortIndex = NULL;
  int *MinimumRingSize = new int[AtomCount];
  int FragmentCounter;
  MoleculeLeafClass *MolecularWalker = NULL;
  MoleculeLeafClass *Subgraphs = NULL;      // list of subgraphs from DFS analysis
  fstream File;
  bool FragmentationToDo = true;
  class StackClass<bond *> *BackEdgeStack = NULL, *LocalBackEdgeStack = NULL;
  bool CheckOrder = false;
  Graph **FragmentList = NULL;
  Graph *ParsedFragmentList = NULL;
  Graph TotalGraph;     // graph with all keysets however local numbers
  int TotalNumberOfKeySets = 0;
  atom **ListOfAtoms = NULL;
  atom ***ListOfLocalAtoms = NULL;
  bool *AtomMask = NULL;

  *out << endl;
#ifdef ADDHYDROGEN
  *out << Verbose(0) << "I will treat hydrogen special and saturate dangling bonds with it." << endl;
#else
  *out << Verbose(0) << "Hydrogen is treated just like the rest of the lot." << endl;
#endif

  // ++++++++++++++++++++++++++++ INITIAL STUFF: Bond structure analysis, file parsing, ... ++++++++++++++++++++++++++++++++++++++++++

  // ===== 1. Check whether bond structure is same as stored in files ====

  // fill the adjacency list
  CreateListOfBondsPerAtom(out);

  // create lookup table for Atom::nr
  FragmentationToDo = FragmentationToDo && CreateFatherLookupTable(out, start, end, ListOfAtoms, AtomCount);

  // === compare it with adjacency file ===
  FragmentationToDo = FragmentationToDo && CheckAdjacencyFileAgainstMolecule(out, configuration->configpath, ListOfAtoms);
  Free((void **)&ListOfAtoms, "molecule::FragmentMolecule - **ListOfAtoms");

  // ===== 2. perform a DFS analysis to gather info on cyclic structure and a list of disconnected subgraphs =====
  Subgraphs = DepthFirstSearchAnalysis(out, BackEdgeStack);
  // fill the bond structure of the individually stored subgraphs
  Subgraphs->next->FillBondStructureFromReference(out, this, (FragmentCounter = 0), ListOfLocalAtoms, false);  // we want to keep the created ListOfLocalAtoms
  // analysis of the cycles (print rings, get minimum cycle length) for each subgraph
  for(int i=AtomCount;i--;)
    MinimumRingSize[i] = AtomCount;
  MolecularWalker = Subgraphs;
  FragmentCounter = 0;
  while (MolecularWalker->next != NULL) {
    MolecularWalker = MolecularWalker->next;
    *out << Verbose(0) << "Analysing the cycles of subgraph " << MolecularWalker->Leaf << " with nr. " << FragmentCounter << "." << endl;
    LocalBackEdgeStack = new StackClass<bond *> (MolecularWalker->Leaf->BondCount);
//    // check the list of local atoms for debugging
//    *out << Verbose(0) << "ListOfLocalAtoms for this subgraph is:" << endl;
//    for (int i=0;i<AtomCount;i++)
//      if (ListOfLocalAtoms[FragmentCounter][i] == NULL)
//        *out << "\tNULL";
//      else
//        *out << "\t" << ListOfLocalAtoms[FragmentCounter][i]->Name;
    *out << Verbose(0) << "Gathering local back edges for subgraph " << MolecularWalker->Leaf << " with nr. " << FragmentCounter << "." << endl;
    MolecularWalker->Leaf->PickLocalBackEdges(out, ListOfLocalAtoms[FragmentCounter++], BackEdgeStack, LocalBackEdgeStack);
    *out << Verbose(0) << "Analysing the cycles of subgraph " << MolecularWalker->Leaf << " with nr. " << FragmentCounter << "." << endl;
    MolecularWalker->Leaf->CyclicStructureAnalysis(out, LocalBackEdgeStack, MinimumRingSize);
    *out << Verbose(0) << "Done with Analysing the cycles of subgraph " << MolecularWalker->Leaf << " with nr. " << FragmentCounter << "." << endl;
    delete(LocalBackEdgeStack);
  }
  
  // ===== 3. if structure still valid, parse key set file and others =====
  FragmentationToDo = FragmentationToDo && ParseKeySetFile(out, configuration->configpath, ParsedFragmentList);

  // ===== 4. check globally whether there's something to do actually (first adaptivity check)
  FragmentationToDo = FragmentationToDo && ParseOrderAtSiteFromFile(out, configuration->configpath);
  
  // =================================== Begin of FRAGMENTATION =============================== 
  // ===== 6a. assign each keyset to its respective subgraph ===== 
  Subgraphs->next->AssignKeySetsToFragment(out, this, ParsedFragmentList, ListOfLocalAtoms, FragmentList, (FragmentCounter = 0), true);

  // ===== 6b. prepare and go into the adaptive (Order<0), single-step (Order==0) or incremental (Order>0) cycle
  KeyStack *RootStack = new KeyStack[Subgraphs->next->Count()];
  AtomMask = new bool[AtomCount+1];
  AtomMask[AtomCount] = false;
  FragmentationToDo = false;  // if CheckOrderAtSite just ones recommends fragmentation, we will save fragments afterwards
  while ((CheckOrder = CheckOrderAtSite(out, AtomMask, ParsedFragmentList, Order, MinimumRingSize, configuration->configpath))) {
    FragmentationToDo = FragmentationToDo || CheckOrder;
    AtomMask[AtomCount] = true;   // last plus one entry is used as marker that we have been through this loop once already in CheckOrderAtSite()
    // ===== 6b. fill RootStack for each subgraph (second adaptivity check) =====
    Subgraphs->next->FillRootStackForSubgraphs(out, RootStack, AtomMask, (FragmentCounter = 0));

    // ===== 7. fill the bond fragment list =====
    FragmentCounter = 0;
    MolecularWalker = Subgraphs;
    while (MolecularWalker->next != NULL) {
      MolecularWalker = MolecularWalker->next;
      *out << Verbose(1) << "Fragmenting subgraph " << MolecularWalker << "." << endl;
      //MolecularWalker->Leaf->OutputListOfBonds(out);  // output ListOfBondsPerAtom for debugging
      if (MolecularWalker->Leaf->first->next != MolecularWalker->Leaf->last) {
        // call BOSSANOVA method
        *out << Verbose(0) << endl << " ========== BOND ENERGY of subgraph " << FragmentCounter << " ========================= " << endl;
        MolecularWalker->Leaf->FragmentBOSSANOVA(out, FragmentList[FragmentCounter], RootStack[FragmentCounter], MinimumRingSize);
      } else {
        cerr << "Subgraph " << MolecularWalker << " has no atoms!" << endl;
      }
      FragmentCounter++;  // next fragment list
    }
  }
  delete[](RootStack);
  delete[](AtomMask);
  delete(ParsedFragmentList);
  delete[](MinimumRingSize);
  

  // ==================================== End of FRAGMENTATION ============================================

  // ===== 8a. translate list into global numbers (i.e. ones that are valid in "this" molecule, not in MolecularWalker->Leaf)
  Subgraphs->next->TranslateIndicesToGlobalIDs(out, FragmentList, (FragmentCounter = 0), TotalNumberOfKeySets, TotalGraph);

  // free subgraph memory again
  FragmentCounter = 0;
  if (Subgraphs != NULL) {
    while (Subgraphs->next != NULL) {
      Subgraphs = Subgraphs->next;
      delete(FragmentList[FragmentCounter++]);
      delete(Subgraphs->previous);
    }
    delete(Subgraphs);
  }
  Free((void **)&FragmentList, "molecule::FragmentMolecule - **FragmentList");

  // ===== 8b. gather keyset lists (graphs) from all subgraphs and transform into MoleculeListClass =====
  //if (FragmentationToDo) {    // we should always store the fragments again as coordination might have changed slightly without changing bond structure
    // allocate memory for the pointer array and transmorph graphs into full molecular fragments
    BondFragments = new MoleculeListClass();
    int k=0;
    for(Graph::iterator runner = TotalGraph.begin(); runner != TotalGraph.end(); runner++) {
      KeySet test = (*runner).first;
      *out << "Fragment No." << (*runner).second.first << " with TEFactor " << (*runner).second.second << "." << endl;
      BondFragments->insert(StoreFragmentFromKeySet(out, test, configuration));
      k++;
    }
    *out << k << "/" << BondFragments->ListOfMolecules.size() << " fragments generated from the keysets." << endl;

    // ===== 9. Save fragments' configuration and keyset files et al to disk ===
    if (BondFragments->ListOfMolecules.size() != 0) {
      // create the SortIndex from BFS labels to order in the config file
      CreateMappingLabelsToConfigSequence(out, SortIndex);

      *out << Verbose(1) << "Writing " << BondFragments->ListOfMolecules.size() << " possible bond fragmentation configs" << endl;
      if (BondFragments->OutputConfigForListOfFragments(out, configuration, SortIndex))
        *out << Verbose(1) << "All configs written." << endl;
      else
        *out << Verbose(1) << "Some config writing failed." << endl;

      // store force index reference file
      BondFragments->StoreForcesFile(out, configuration->configpath, SortIndex);

      // store keysets file
      StoreKeySetFile(out, TotalGraph, configuration->configpath);

      // store Adjacency file
      StoreAdjacencyToFile(out, configuration->configpath);

      // store Hydrogen saturation correction file
      BondFragments->AddHydrogenCorrection(out, configuration->configpath);

      // store adaptive orders into file
      StoreOrderAtSiteFile(out, configuration->configpath);

      // restore orbital and Stop values
      CalculateOrbitals(*configuration);

      // free memory for bond part
      *out << Verbose(1) << "Freeing bond memory" << endl;
      delete(FragmentList); // remove bond molecule from memory
      Free((void **)&SortIndex, "molecule::FragmentMolecule: *SortIndex");
    } else
      *out << Verbose(1) << "FragmentList is zero on return, splitting failed." << endl;
  //} else
  //  *out << Verbose(1) << "No fragments to store." << endl;
  *out << Verbose(0) << "End of bond fragmentation." << endl;

  return ((int)(!FragmentationToDo)+1);    // 1 - continue, 2 - stop (no fragmentation occured)
};


/** Picks from a global stack with all back edges the ones in the fragment.
 * \param *out output stream for debugging
 * \param **ListOfLocalAtoms array of father atom::nr to local atom::nr (reverse of atom::father)
 * \param *ReferenceStack stack with all the back egdes
 * \param *LocalStack stack to be filled
 * \return true - everything ok, false - ReferenceStack was empty
 */
bool molecule::PickLocalBackEdges(ofstream *out, atom **ListOfLocalAtoms, class StackClass<bond *> *&ReferenceStack, class StackClass<bond *> *&LocalStack)
{
  bool status = true;
  if (ReferenceStack->IsEmpty()) {
    cerr << "ReferenceStack is empty!" << endl;
    return false;
  }
  bond *Binder = ReferenceStack->PopFirst();
  bond *FirstBond = Binder;   // mark the first bond, so that we don't loop through the stack indefinitely
  atom *Walker = NULL, *OtherAtom = NULL;
  ReferenceStack->Push(Binder);
  
  do {  // go through all bonds and push local ones
    Walker = ListOfLocalAtoms[Binder->leftatom->nr];  // get one atom in the reference molecule
    if (Walker != NULL) // if this Walker exists in the subgraph ...
      for(int i=0;i<NumberOfBondsPerAtom[Walker->nr];i++) {    // go through the local list of bonds
        OtherAtom = ListOfBondsPerAtom[Walker->nr][i]->GetOtherAtom(Walker);
        if (OtherAtom == ListOfLocalAtoms[Binder->rightatom->nr]) { // found the bond
          LocalStack->Push(ListOfBondsPerAtom[Walker->nr][i]);
          *out << Verbose(3) << "Found local edge " << *(ListOfBondsPerAtom[Walker->nr][i]) << "." << endl;
          break;
        }
      }
    Binder = ReferenceStack->PopFirst();  // loop the stack for next item
    *out << Verbose(3) << "Current candidate edge " << Binder << "." << endl;
    ReferenceStack->Push(Binder);
  } while (FirstBond != Binder);

  return status;
};

/** Stores pairs (Atom::nr, Atom::AdaptiveOrder) into file.
 * Atoms not present in the file get "-1".
 * \param *out output stream for debugging
 * \param *path path to file ORDERATSITEFILE
 * \return true - file writable, false - not writable
 */
bool molecule::StoreOrderAtSiteFile(ofstream *out, char *path)
{
  stringstream line;
  ofstream file;

  line << path << "/" << FRAGMENTPREFIX << ORDERATSITEFILE;
  file.open(line.str().c_str());
  *out << Verbose(1) << "Writing OrderAtSite " << ORDERATSITEFILE << " ... " << endl;
  if (file != NULL) {
    atom *Walker = start;
    while (Walker->next != end) {
      Walker = Walker->next;
      file << Walker->nr << "\t" << (int)Walker->AdaptiveOrder << "\t" << (int)Walker->MaxOrder << endl;
      *out << Verbose(2) << "Storing: " << Walker->nr << "\t" << (int)Walker->AdaptiveOrder << "\t" << (int)Walker->MaxOrder << "." << endl;
    }
    file.close();
    *out << Verbose(1) << "done." << endl;
    return true;
  } else {
    *out << Verbose(1) << "failed to open file " << line.str() << "." << endl;
    return false;
  }
};

/** Parses pairs(Atom::nr, Atom::AdaptiveOrder) from file and stores in molecule's Atom's.
 * Atoms not present in the file get "0".
 * \param *out output stream for debugging
 * \param *path path to file ORDERATSITEFILEe
 * \return true - file found and scanned, false - file not found
 * \sa ParseKeySetFile() and CheckAdjacencyFileAgainstMolecule() as this is meant to be used in conjunction with the two
 */
bool molecule::ParseOrderAtSiteFromFile(ofstream *out, char *path)
{
  unsigned char *OrderArray = (unsigned char *) Malloc(sizeof(unsigned char)*AtomCount, "molecule::ParseOrderAtSiteFromFile - *OrderArray");
  bool *MaxArray = (bool *) Malloc(sizeof(bool)*AtomCount, "molecule::ParseOrderAtSiteFromFile - *MaxArray");
  bool status;
  int AtomNr, value;
  stringstream line;
  ifstream file;

  *out << Verbose(1) << "Begin of ParseOrderAtSiteFromFile" << endl;
  for(int i=AtomCount;i--;)
    OrderArray[i] = 0;
  line << path << "/" << FRAGMENTPREFIX << ORDERATSITEFILE;
  file.open(line.str().c_str());
  if (file != NULL) {
    for (int i=AtomCount;i--;) { // initialise with 0
      OrderArray[i] = 0;
      MaxArray[i] = 0;
    }
    while (!file.eof()) { // parse from file
      AtomNr = -1;
      file >> AtomNr;
      if (AtomNr != -1) {   // test whether we really parsed something (this is necessary, otherwise last atom is set twice and to 0 on second time)
        file >> value;
        OrderArray[AtomNr] = value;
        file >> value;
        MaxArray[AtomNr] = value;
        //*out << Verbose(2) << "AtomNr " << AtomNr << " with order " << (int)OrderArray[AtomNr] << " and max order set to " << (int)MaxArray[AtomNr] << "." << endl;
      }
    }
    atom *Walker = start;
    while (Walker->next != end) { // fill into atom classes
      Walker = Walker->next;
      Walker->AdaptiveOrder = OrderArray[Walker->nr];
      Walker->MaxOrder = MaxArray[Walker->nr];
      *out << Verbose(2) << *Walker << " gets order " << (int)Walker->AdaptiveOrder << " and is " << (!Walker->MaxOrder ? "not " : " ") << "maxed." << endl;
    }
    file.close();
    *out << Verbose(1) << "done." << endl;
    status = true;
  } else {
    *out << Verbose(1) << "failed to open file " << line.str() << "." << endl;
    status = false;
  }
  Free((void **)&OrderArray, "molecule::ParseOrderAtSiteFromFile - *OrderArray");
  Free((void **)&MaxArray, "molecule::ParseOrderAtSiteFromFile - *MaxArray");

  *out << Verbose(1) << "End of ParseOrderAtSiteFromFile" << endl;
  return status;
};

/** Creates an 2d array of pointer with an entry for each atom and each bond it has.
 * Updates molecule::ListOfBondsPerAtom, molecule::NumberOfBondsPerAtom by parsing through
 * bond chain list, using molecule::AtomCount and molecule::BondCount.
 * Allocates memory, fills the array and exits
 * \param *out output stream for debugging
 */
void molecule::CreateListOfBondsPerAtom(ofstream *out)
{
  bond *Binder = NULL;
  atom *Walker = NULL;
  int TotalDegree;
  *out << Verbose(1) << "Begin of Creating ListOfBondsPerAtom: AtomCount = " << AtomCount << "\tBondCount = " << BondCount << "\tNoNonBonds = " << NoNonBonds << "." << endl;

  // re-allocate memory
  *out << Verbose(2) << "(Re-)Allocating memory." << endl;
  if (ListOfBondsPerAtom != NULL) {
    for(int i=AtomCount;i--;)
      Free((void **)&ListOfBondsPerAtom[i], "molecule::CreateListOfBondsPerAtom: ListOfBondsPerAtom[i]");
    Free((void **)&ListOfBondsPerAtom, "molecule::CreateListOfBondsPerAtom: ListOfBondsPerAtom");
  }
  if (NumberOfBondsPerAtom != NULL)
    Free((void **)&NumberOfBondsPerAtom, "molecule::CreateListOfBondsPerAtom: NumberOfBondsPerAtom");
  ListOfBondsPerAtom = (bond ***) Malloc(sizeof(bond **)*AtomCount, "molecule::CreateListOfBondsPerAtom: ***ListOfBondsPerAtom");
  NumberOfBondsPerAtom = (int *) Malloc(sizeof(int)*AtomCount, "molecule::CreateListOfBondsPerAtom: *NumberOfBondsPerAtom");

  // reset bond counts per atom
  for(int i=AtomCount;i--;)
    NumberOfBondsPerAtom[i] = 0;
  // count bonds per atom
  Binder = first;
  while (Binder->next != last) {
    Binder = Binder->next;
    NumberOfBondsPerAtom[Binder->leftatom->nr]++;
    NumberOfBondsPerAtom[Binder->rightatom->nr]++;
  }
  for(int i=AtomCount;i--;) {
    // allocate list of bonds per atom
    ListOfBondsPerAtom[i] = (bond **) Malloc(sizeof(bond *)*NumberOfBondsPerAtom[i], "molecule::CreateListOfBondsPerAtom: **ListOfBondsPerAtom[]");
    // clear the list again, now each NumberOfBondsPerAtom marks current free field
    NumberOfBondsPerAtom[i] = 0;
  }
  // fill the list
  Binder = first;
  while (Binder->next != last) {
    Binder = Binder->next;
    ListOfBondsPerAtom[Binder->leftatom->nr][NumberOfBondsPerAtom[Binder->leftatom->nr]++] = Binder;
    ListOfBondsPerAtom[Binder->rightatom->nr][NumberOfBondsPerAtom[Binder->rightatom->nr]++] = Binder;
  }

  // output list for debugging
  *out << Verbose(3) << "ListOfBondsPerAtom for each atom:" << endl;
  Walker = start;
  while (Walker->next != end) {
    Walker = Walker->next;
    *out << Verbose(4) << "Atom " << Walker->Name << "/" << Walker->nr << " with " << NumberOfBondsPerAtom[Walker->nr] << " bonds: ";
    TotalDegree = 0;
    for (int j=0;j<NumberOfBondsPerAtom[Walker->nr];j++) {
      *out << *ListOfBondsPerAtom[Walker->nr][j] << "\t";
      TotalDegree += ListOfBondsPerAtom[Walker->nr][j]->BondDegree;
    }
    *out << " -- TotalDegree: " << TotalDegree << endl;
  }
  *out << Verbose(1) << "End of Creating ListOfBondsPerAtom." << endl << endl;
};

/** Adds atoms up to \a BondCount distance from \a *Root and notes them down in \a **AddedAtomList.
 * Gray vertices are always enqueued in an StackClass<atom *> FIFO queue, the rest is usual BFS with adding vertices found was
 * white and putting into queue.
 * \param *out output stream for debugging
 * \param *Mol Molecule class to add atoms to
 * \param **AddedAtomList list with added atom pointers, index is atom father's number
 * \param **AddedBondList list with added bond pointers, index is bond father's number
 * \param *Root root vertex for BFS
 * \param *Bond bond not to look beyond
 * \param BondOrder maximum distance for vertices to add
 * \param IsAngstroem lengths are in angstroem or bohrradii
 */
void molecule::BreadthFirstSearchAdd(ofstream *out, molecule *Mol, atom **&AddedAtomList, bond **&AddedBondList, atom *Root, bond *Bond, int BondOrder, bool IsAngstroem)
{
  atom **PredecessorList = (atom **) Malloc(sizeof(atom *)*AtomCount, "molecule::BreadthFirstSearchAdd: **PredecessorList");
  int *ShortestPathList = (int *) Malloc(sizeof(int)*AtomCount, "molecule::BreadthFirstSearchAdd: *ShortestPathList");
  enum Shading *ColorList = (enum Shading *) Malloc(sizeof(enum Shading)*AtomCount, "molecule::BreadthFirstSearchAdd: *ColorList");
  class StackClass<atom *> *AtomStack = new StackClass<atom *>(AtomCount);
  atom *Walker = NULL, *OtherAtom = NULL;
  bond *Binder = NULL;

  // add Root if not done yet
  AtomStack->ClearStack();
  if (AddedAtomList[Root->nr] == NULL)  // add Root if not yet present
    AddedAtomList[Root->nr] = Mol->AddCopyAtom(Root);
  AtomStack->Push(Root);

  // initialise each vertex as white with no predecessor, empty queue, color Root lightgray
  for (int i=AtomCount;i--;) {
    PredecessorList[i] = NULL;
    ShortestPathList[i] = -1;
    if (AddedAtomList[i] != NULL) // mark already present atoms (i.e. Root and maybe others) as visited
      ColorList[i] = lightgray;
    else
      ColorList[i] = white;
  }
  ShortestPathList[Root->nr] = 0;

  // and go on ... Queue always contains all lightgray vertices
  while (!AtomStack->IsEmpty()) {
    // 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 = AtomStack->PopFirst(); // pop oldest added
    *out << Verbose(1) << "Current Walker is: " << Walker->Name << ", and has " << NumberOfBondsPerAtom[Walker->nr] << " bonds." << endl;
    for(int i=0;i<NumberOfBondsPerAtom[Walker->nr];i++) {
      Binder = ListOfBondsPerAtom[Walker->nr][i];
      if (Binder != NULL) { // don't look at bond equal NULL
        OtherAtom = Binder->GetOtherAtom(Walker);
        *out << Verbose(2) << "Current OtherAtom is: " << OtherAtom->Name << " for bond " << *Binder << "." << endl;
        if (ColorList[OtherAtom->nr] == white) {
          if (Binder != Bond) // let other atom white if it's via Root bond. In case it's cyclic it has to be reached again (yet Root is from OtherAtom already black, thus no problem)
            ColorList[OtherAtom->nr] = lightgray;
          PredecessorList[OtherAtom->nr] = Walker;  // Walker is the predecessor
          ShortestPathList[OtherAtom->nr] = ShortestPathList[Walker->nr]+1;
          *out << Verbose(2) << "Coloring OtherAtom " << OtherAtom->Name << " " << ((ColorList[OtherAtom->nr] == white) ? "white" : "lightgray") << ", its predecessor is " << Walker->Name << " and its Shortest Path is " << ShortestPathList[OtherAtom->nr] << " egde(s) long." << endl;
          if ((((ShortestPathList[OtherAtom->nr] < BondOrder) && (Binder != Bond))) ) { // Check for maximum distance
            *out << Verbose(3);
            if (AddedAtomList[OtherAtom->nr] == NULL) { // add if it's not been so far
              AddedAtomList[OtherAtom->nr] = Mol->AddCopyAtom(OtherAtom);
              *out << "Added OtherAtom " << OtherAtom->Name;
              AddedBondList[Binder->nr] = Mol->AddBond(AddedAtomList[Walker->nr], AddedAtomList[OtherAtom->nr], Binder->BondDegree);
              AddedBondList[Binder->nr]->Cyclic = Binder->Cyclic;
              AddedBondList[Binder->nr]->Type = Binder->Type;
              *out << " and bond " << *(AddedBondList[Binder->nr]) << ", ";
            } else {  // this code should actually never come into play (all white atoms are not yet present in BondMolecule, that's why they are white in the first place)
              *out << "Not adding OtherAtom " << OtherAtom->Name;
              if (AddedBondList[Binder->nr] == NULL) {
                AddedBondList[Binder->nr] = Mol->AddBond(AddedAtomList[Walker->nr], AddedAtomList[OtherAtom->nr], Binder->BondDegree);
                AddedBondList[Binder->nr]->Cyclic = Binder->Cyclic;
                AddedBondList[Binder->nr]->Type = Binder->Type;
                *out << ", added Bond " << *(AddedBondList[Binder->nr]);
              } else
                *out << ", not added Bond ";
            }
            *out << ", putting OtherAtom into queue." << endl;
            AtomStack->Push(OtherAtom);
          } else { // out of bond order, then replace
            if ((AddedAtomList[OtherAtom->nr] == NULL) && (Binder->Cyclic))
              ColorList[OtherAtom->nr] = white; // unmark if it has not been queued/added, to make it available via its other bonds (cyclic)
            if (Binder == Bond)
              *out << Verbose(3) << "Not Queueing, is the Root bond";
            else if (ShortestPathList[OtherAtom->nr] >= BondOrder)
              *out << Verbose(3) << "Not Queueing, is out of Bond Count of " << BondOrder;
            if (!Binder->Cyclic)
              *out << ", is not part of a cyclic bond, saturating bond with Hydrogen." << endl;
            if (AddedBondList[Binder->nr] == NULL) {
              if ((AddedAtomList[OtherAtom->nr] != NULL)) { // .. whether we add or saturate
                AddedBondList[Binder->nr] = Mol->AddBond(AddedAtomList[Walker->nr], AddedAtomList[OtherAtom->nr], Binder->BondDegree);
                AddedBondList[Binder->nr]->Cyclic = Binder->Cyclic;
                AddedBondList[Binder->nr]->Type = Binder->Type;
              } else {
#ifdef ADDHYDROGEN
                if (!Mol->AddHydrogenReplacementAtom(out, Binder, AddedAtomList[Walker->nr], Walker, OtherAtom, ListOfBondsPerAtom[Walker->nr], NumberOfBondsPerAtom[Walker->nr], IsAngstroem))
                  exit(1);
#endif
              }
            }
          }
        } else {
          *out << Verbose(3) << "Not Adding, has already been visited." << endl;
          // This has to be a cyclic bond, check whether it's present ...
          if (AddedBondList[Binder->nr] == NULL) {
            if ((Binder != Bond) && (Binder->Cyclic) && (((ShortestPathList[Walker->nr]+1) < BondOrder))) {
              AddedBondList[Binder->nr] = Mol->AddBond(AddedAtomList[Walker->nr], AddedAtomList[OtherAtom->nr], Binder->BondDegree);
              AddedBondList[Binder->nr]->Cyclic = Binder->Cyclic;
              AddedBondList[Binder->nr]->Type = Binder->Type;
            } else { // if it's root bond it has to broken (otherwise we would not create the fragments)
#ifdef ADDHYDROGEN
              if(!Mol->AddHydrogenReplacementAtom(out, Binder, AddedAtomList[Walker->nr], Walker, OtherAtom, ListOfBondsPerAtom[Walker->nr], NumberOfBondsPerAtom[Walker->nr], IsAngstroem))
                exit(1);
#endif
            }
          }
        }
      }
    }
    ColorList[Walker->nr] = black;
    *out << Verbose(1) << "Coloring Walker " << Walker->Name << " black." << endl;
  }
  Free((void **)&PredecessorList, "molecule::BreadthFirstSearchAdd: **PredecessorList");
  Free((void **)&ShortestPathList, "molecule::BreadthFirstSearchAdd: **ShortestPathList");
  Free((void **)&ColorList, "molecule::BreadthFirstSearchAdd: **ColorList");
  delete(AtomStack);
};

/** Adds bond structure to this molecule from \a Father molecule.
 * This basically causes this molecule to become an induced subgraph of the \a Father, i.e. for every bond in Father
 * with end points present in this molecule, bond is created in this molecule.
 * Special care was taken to ensure that this is of complexity O(N), where N is the \a Father's molecule::AtomCount.
 * \param *out output stream for debugging
 * \param *Father father molecule
 * \return true - is induced subgraph, false - there are atoms with fathers not in \a Father
 * \todo not checked, not fully working probably
 */
bool molecule::BuildInducedSubgraph(ofstream *out, const molecule *Father)
{
  atom *Walker = NULL, *OtherAtom = NULL;
  bool status = true;
  atom **ParentList = (atom **) Malloc(sizeof(atom *)*Father->AtomCount, "molecule::BuildInducedSubgraph: **ParentList");

  *out << Verbose(2) << "Begin of BuildInducedSubgraph." << endl;

  // reset parent list
  *out << Verbose(3) << "Resetting ParentList." << endl;
  for (int i=Father->AtomCount;i--;)
    ParentList[i] = NULL;

  // fill parent list with sons
  *out << Verbose(3) << "Filling Parent List." << endl;
  Walker = start;
  while (Walker->next != end) {
    Walker = Walker->next;
    ParentList[Walker->father->nr] = Walker;
    // Outputting List for debugging
    *out << Verbose(4) << "Son["<< Walker->father->nr <<"] of " << Walker->father <<  " is " << ParentList[Walker->father->nr] << "." << endl;
  }

  // check each entry of parent list and if ok (one-to-and-onto matching) create bonds
  *out << Verbose(3) << "Creating bonds." << endl;
  Walker = Father->start;
  while (Walker->next != Father->end) {
    Walker = Walker->next;
    if (ParentList[Walker->nr] != NULL) {
      if (ParentList[Walker->nr]->father != Walker) {
        status = false;
      } else {
        for (int i=0;i<Father->NumberOfBondsPerAtom[Walker->nr];i++) {
          OtherAtom = Father->ListOfBondsPerAtom[Walker->nr][i]->GetOtherAtom(Walker);
          if (ParentList[OtherAtom->nr] != NULL) { // if otheratom is also a father of an atom on this molecule, create the bond
            *out << Verbose(4) << "Endpoints of Bond " << Father->ListOfBondsPerAtom[Walker->nr][i] << " are both present: " << ParentList[Walker->nr]->Name << " and " << ParentList[OtherAtom->nr]->Name << "." << endl;
            AddBond(ParentList[Walker->nr], ParentList[OtherAtom->nr], Father->ListOfBondsPerAtom[Walker->nr][i]->BondDegree);
          }
        }
      }
    }
  }

  Free((void **)&ParentList, "molecule::BuildInducedSubgraph: **ParentList");
  *out << Verbose(2) << "End of BuildInducedSubgraph." << endl;
  return status;
};


/** Looks through a StackClass<atom *> and returns the likeliest removal candiate.
 * \param *out output stream for debugging messages
 * \param *&Leaf KeySet to look through
 * \param *&ShortestPathList list of the shortest path to decide which atom to suggest as removal candidate in the end
 * \param index of the atom suggested for removal
 */
int molecule::LookForRemovalCandidate(ofstream *&out, KeySet *&Leaf, int *&ShortestPathList)
{
  atom *Runner = NULL;
  int SP, Removal;

  *out << Verbose(2) << "Looking for removal candidate." << endl;
  SP = -1; //0;  // not -1, so that Root is never removed
  Removal = -1;
  for (KeySet::iterator runner = Leaf->begin(); runner != Leaf->end(); runner++) {
    Runner = FindAtom((*runner));
    if (Runner->type->Z != 1) { // skip all those added hydrogens when re-filling snake stack
      if (ShortestPathList[(*runner)] > SP) {  // remove the oldest one with longest shortest path
        SP = ShortestPathList[(*runner)];
        Removal = (*runner);
      }
    }
  }
  return Removal;
};

/** Stores a fragment from \a KeySet into \a molecule.
 * First creates the minimal set of atoms from the KeySet, then creates the bond structure from the complete
 * molecule and adds missing hydrogen where bonds were cut.
 * \param *out output stream for debugging messages
 * \param &Leaflet pointer to KeySet structure
 * \param IsAngstroem whether we have Ansgtroem or bohrradius
 * \return pointer to constructed molecule
 */
molecule * molecule::StoreFragmentFromKeySet(ofstream *out, KeySet &Leaflet, bool IsAngstroem)
{
  atom *Runner = NULL, *FatherOfRunner = NULL, *OtherFather = NULL;
  atom **SonList = (atom **) Malloc(sizeof(atom *)*AtomCount, "molecule::StoreFragmentFromStack: **SonList");
  molecule *Leaf = new molecule(elemente);
  bool LonelyFlag = false;
  int size;

//  *out << Verbose(1) << "Begin of StoreFragmentFromKeyset." << endl;

  Leaf->BondDistance = BondDistance;
  for(int i=NDIM*2;i--;)
    Leaf->cell_size[i] = cell_size[i];

  // initialise SonList (indicates when we need to replace a bond with hydrogen instead)
  for(int i=AtomCount;i--;)
    SonList[i] = NULL;

  // first create the minimal set of atoms from the KeySet
  size = 0;
  for(KeySet::iterator runner = Leaflet.begin(); runner != Leaflet.end(); runner++) {
    FatherOfRunner = FindAtom((*runner));  // find the id
    SonList[FatherOfRunner->nr] = Leaf->AddCopyAtom(FatherOfRunner);
    size++;
  }

  // create the bonds between all: Make it an induced subgraph and add hydrogen
//  *out << Verbose(2) << "Creating bonds from father graph (i.e. induced subgraph creation)." << endl;
  Runner = Leaf->start;
  while (Runner->next != Leaf->end) {
    Runner = Runner->next;
    LonelyFlag = true;
    FatherOfRunner = Runner->father;
    if (SonList[FatherOfRunner->nr] != NULL)  {  // check if this, our father, is present in list
      // create all bonds
      for (int i=0;i<NumberOfBondsPerAtom[FatherOfRunner->nr];i++) { // go through every bond of father
        OtherFather = ListOfBondsPerAtom[FatherOfRunner->nr][i]->GetOtherAtom(FatherOfRunner);
//        *out << Verbose(2) << "Father " << *FatherOfRunner << " of son " << *SonList[FatherOfRunner->nr] << " is bound to " << *OtherFather;
        if (SonList[OtherFather->nr] != NULL) {
//          *out << ", whose son is " << *SonList[OtherFather->nr] << "." << endl;
          if (OtherFather->nr > FatherOfRunner->nr) { // add bond (nr check is for adding only one of both variants: ab, ba)
//            *out << Verbose(3) << "Adding Bond: ";
//            *out <<
            Leaf->AddBond(Runner, SonList[OtherFather->nr], ListOfBondsPerAtom[FatherOfRunner->nr][i]->BondDegree);
//            *out << "." << endl;
            //NumBonds[Runner->nr]++;
          } else {
//            *out << Verbose(3) << "Not adding bond, labels in wrong order." << endl;
          }
          LonelyFlag = false;
        } else {
//          *out << ", who has no son in this fragment molecule." << endl;
#ifdef ADDHYDROGEN
          //*out << Verbose(3) << "Adding Hydrogen to " << Runner->Name << " and a bond in between." << endl;
          if(!Leaf->AddHydrogenReplacementAtom(out, ListOfBondsPerAtom[FatherOfRunner->nr][i], Runner, FatherOfRunner, OtherFather, ListOfBondsPerAtom[FatherOfRunner->nr],NumberOfBondsPerAtom[FatherOfRunner->nr], IsAngstroem))
            exit(1);
#endif
          //NumBonds[Runner->nr] += ListOfBondsPerAtom[FatherOfRunner->nr][i]->BondDegree;
        }
      }
    } else {
      *out << Verbose(0) << "ERROR: Son " << Runner->Name << " has father " << FatherOfRunner->Name << " but its entry in SonList is " << SonList[FatherOfRunner->nr] << "!" << endl;
    }
    if ((LonelyFlag) && (size > 1)) {
      *out << Verbose(0) << *Runner << "has got bonds only to hydrogens!" << endl;
    }
#ifdef ADDHYDROGEN
    while ((Runner->next != Leaf->end) && (Runner->next->type->Z == 1)) // skip added hydrogen
      Runner = Runner->next;
#endif
  }
  Leaf->CreateListOfBondsPerAtom(out);
  //Leaflet->Leaf->ScanForPeriodicCorrection(out);
  Free((void **)&SonList, "molecule::StoreFragmentFromStack: **SonList");
//  *out << Verbose(1) << "End of StoreFragmentFromKeyset." << endl;
  return Leaf;
};

/** Creates \a MoleculeListClass of all unique fragments of the \a molecule containing \a Order atoms or vertices.
 * The picture to have in mind is that of a DFS "snake" of a certain length \a Order, i.e. as in the infamous
 * computer game, that winds through the connected graph representing the molecule. Color (white,
 * lightgray, darkgray, black) indicates whether a vertex has been discovered so far or not. Labels will help in
 * creating only unique fragments and not additional ones with vertices simply in different sequence.
 * The Predecessor is always the one that came before in discovering, needed on backstepping. And
 * finally, the ShortestPath is needed for removing vertices from the snake stack during the back-
 * stepping.
 * \param *out output stream for debugging
 * \param Order number of atoms in each fragment
 * \param *configuration configuration for writing config files for each fragment
 * \return List of all unique fragments with \a Order atoms
 */
/*
MoleculeListClass * molecule::CreateListOfUniqueFragmentsOfOrder(ofstream *out, int Order, config *configuration)
{
  atom **PredecessorList = (atom **) Malloc(sizeof(atom *)*AtomCount, "molecule::CreateListOfUniqueFragmentsOfOrder: **PredecessorList");
  int *ShortestPathList = (int *) Malloc(sizeof(int)*AtomCount, "molecule::CreateListOfUniqueFragmentsOfOrder: *ShortestPathList");
  int *Labels = (int *) Malloc(sizeof(int)*AtomCount, "molecule::CreateListOfUniqueFragmentsOfOrder: *Labels");
  enum Shading *ColorVertexList = (enum Shading *) Malloc(sizeof(enum Shading)*AtomCount, "molecule::CreateListOfUniqueFragmentsOfOrder: *ColorList");
  enum Shading *ColorEdgeList = (enum Shading *) Malloc(sizeof(enum Shading)*BondCount, "molecule::CreateListOfUniqueFragmentsOfOrder: *ColorBondList");
  StackClass<atom *> *RootStack = new StackClass<atom *>(AtomCount);
  StackClass<atom *> *TouchedStack = new StackClass<atom *>((int)pow(4,Order)+2); // number of atoms reached from one with maximal 4 bonds plus Root itself
  StackClass<atom *> *SnakeStack = new StackClass<atom *>(Order+1); // equal to Order is not possible, as then the StackClass<atom *> cannot discern between full and empty stack!
  MoleculeLeafClass *Leaflet = NULL, *TempLeaf = NULL;
  MoleculeListClass *FragmentList = NULL;
  atom *Walker = NULL, *OtherAtom = NULL, *Root = NULL, *Removal = NULL;
  bond *Binder = NULL;
  int RunningIndex = 0, FragmentCounter = 0;

  *out << Verbose(1) << "Begin of CreateListOfUniqueFragmentsOfOrder." << endl;

  // reset parent list
  *out << Verbose(3) << "Resetting labels, parent, predecessor, color and shortest path lists." << endl;
  for (int i=0;i<AtomCount;i++) { // reset all atom labels
    // initialise each vertex as white with no predecessor, empty queue, color lightgray, not labelled, no sons
    Labels[i] = -1;
    SonList[i] = NULL;
    PredecessorList[i] = NULL;
    ColorVertexList[i] = white;
    ShortestPathList[i] = -1;
  }
  for (int i=0;i<BondCount;i++)
    ColorEdgeList[i] = white;
  RootStack->ClearStack();  // clearstack and push first atom if exists
  TouchedStack->ClearStack();
  Walker = start->next;
  while ((Walker != end)
#ifdef ADDHYDROGEN
   && (Walker->type->Z == 1)
        }
      }
      *out << ", SP of " << ShortestPathList[Walker->nr]  << " and its color is " << GetColor(ColorVertexList[Walker->nr]) << "." << endl;

      // then check the stack for a newly stumbled upon fragment
      if (SnakeStack->ItemCount() == Order) { // is stack full?
        // store the fragment if it is one and get a removal candidate
        Removal = StoreFragmentFromStack(out, Root, Walker, Leaflet, SnakeStack, ShortestPathList, SonList, Labels, &FragmentCounter, configuration);
        // remove the candidate if one was found
        if (Removal != NULL) {
          *out << Verbose(2) << "Removing item " << Removal->Name << " with SP of " << ShortestPathList[Removal->nr] << " from snake stack." << endl;
          SnakeStack->RemoveItem(Removal);
          ColorVertexList[Removal->nr] = lightgray; // return back to not on snake stack but explored marking
          if (Walker == Removal) { // if the current atom is to be removed, we also have to take a step back
            Walker = PredecessorList[Removal->nr];
            *out << Verbose(2) << "Stepping back to " << Walker->Name << "." << endl;
          }
        }
      } else
        Removal = NULL;

      // finally, look for a white neighbour as the next Walker
      Binder = NULL;
      if ((Removal == NULL) || (Walker != PredecessorList[Removal->nr])) {  // don't look, if a new walker has been set above
        *out << Verbose(2) << "Snake has currently " << SnakeStack->ItemCount() << " item(s)." << endl;
        OtherAtom = NULL; // this is actually not needed, every atom has at least one neighbour
        if (ShortestPathList[Walker->nr] < Order) {
          for(int i=0;i<NumberOfBondsPerAtom[Walker->nr];i++) {
            Binder = ListOfBondsPerAtom[Walker->nr][i];
            *out << Verbose(2) << "Current bond is " << *Binder << ": ";
            OtherAtom = Binder->GetOtherAtom(Walker);
            if ((Labels[OtherAtom->nr] != -1) && (Labels[OtherAtom->nr] < Labels[Root->nr])) { // we don't step up to labels bigger than us
              *out << "Label " << Labels[OtherAtom->nr] << " is smaller than Root's " << Labels[Root->nr] << "." << endl;
              //ColorVertexList[OtherAtom->nr] = lightgray;    // mark as explored
            } else { // otherwise check its colour and element
              if (
              (OtherAtom->type->Z != 1) &&
#endif
                    (ColorEdgeList[Binder->nr] == white)) {  // skip hydrogen, look for unexplored vertices
                *out << "Moving along " << GetColor(ColorEdgeList[Binder->nr]) << " bond " << Binder << " to " << ((ColorVertexList[OtherAtom->nr] == white) ? "unexplored" : "explored") << " item: " << OtherAtom->Name << "." << endl;
                // i find it currently rather sensible to always set the predecessor in order to find one's way back
                //if (PredecessorList[OtherAtom->nr] == NULL) {
                PredecessorList[OtherAtom->nr] = Walker;
                *out << Verbose(3) << "Setting Predecessor of " << OtherAtom->Name << " to " << PredecessorList[OtherAtom->nr]->Name << "." << endl;
                //} else {
                //  *out << Verbose(3) << "Predecessor of " << OtherAtom->Name << " is " << PredecessorList[OtherAtom->nr]->Name << "." << endl;
                //}
                Walker = OtherAtom;
                break;
              } else {
                if (OtherAtom->type->Z == 1)
                  *out << "Links to a hydrogen atom." << endl;
                else
                  *out << "Bond has not white but " << GetColor(ColorEdgeList[Binder->nr]) << " color." << endl;
              }
            }
          }
        } else {  // means we have stepped beyond the horizon: Return!
          Walker = PredecessorList[Walker->nr];
          OtherAtom = Walker;
          *out << Verbose(3) << "We have gone too far, stepping back to " << Walker->Name << "." << endl;
        }
        if (Walker != OtherAtom) {  // if no white neighbours anymore, color it black
          *out << Verbose(2) << "Coloring " << Walker->Name << " black." << endl;
          ColorVertexList[Walker->nr] = black;
          Walker = PredecessorList[Walker->nr];
        }
      }
    } while ((Walker != Root) || (ColorVertexList[Root->nr] != black));
    *out << Verbose(2) << "Inner Looping is finished." << endl;

    // if we reset all AtomCount atoms, we have again technically O(N^2) ...
    *out << Verbose(2) << "Resetting lists." << endl;
    Walker = NULL;
    Binder = NULL;
    while (!TouchedStack->IsEmpty()) {
      Walker = TouchedStack->PopLast();
      *out << Verbose(3) << "Re-initialising entries of " << *Walker << "." << endl;
      for(int i=0;i<NumberOfBondsPerAtom[Walker->nr];i++)
        ColorEdgeList[ListOfBondsPerAtom[Walker->nr][i]->nr] = white;
      PredecessorList[Walker->nr] = NULL;
      ColorVertexList[Walker->nr] = white;
      ShortestPathList[Walker->nr] = -1;
    }
  }
  *out << Verbose(1) << "Outer Looping over all vertices is done." << endl;

  // copy together
  *out << Verbose(1) << "Copying all fragments into MoleculeList structure." << endl;
  FragmentList = new MoleculeListClass(FragmentCounter, AtomCount);
  RunningIndex = 0;
  while ((Leaflet != NULL) && (RunningIndex < FragmentCounter))  {
    FragmentList->ListOfMolecules[RunningIndex++] = Leaflet->Leaf;
    Leaflet->Leaf = NULL; // prevent molecule from being removed
    TempLeaf = Leaflet;
    Leaflet = Leaflet->previous;
    delete(TempLeaf);
  };

  // free memory and exit
  Free((void **)&PredecessorList, "molecule::CreateListOfUniqueFragmentsOfOrder: **PredecessorList");
  Free((void **)&ShortestPathList, "molecule::CreateListOfUniqueFragmentsOfOrder: *ShortestPathList");
  Free((void **)&Labels, "molecule::CreateListOfUniqueFragmentsOfOrder: *Labels");
  Free((void **)&ColorVertexList, "molecule::CreateListOfUniqueFragmentsOfOrder: *ColorList");
  delete(RootStack);
  delete(TouchedStack);
  delete(SnakeStack);

  *out << Verbose(1) << "End of CreateListOfUniqueFragmentsOfOrder." << endl;
  return FragmentList;
};
*/

/** Structure containing all values in power set combination generation.
 */
struct UniqueFragments {
  config *configuration;
  atom *Root;
  Graph *Leaflet;
  KeySet *FragmentSet;
  int ANOVAOrder;
  int FragmentCounter;
  int CurrentIndex;
  double TEFactor;
  int *ShortestPathList;
  bool **UsedList;
  bond **BondsPerSPList;
  int *BondsPerSPCount;
};

/** From a given set of Bond sorted by Shortest Path distance, create all possible fragments of size \a SetDimension.
 * -# loops over every possible combination (2^dimension of edge set)
 *  -# inserts current set, if there's still space left
 *    -# yes: calls SPFragmentGenerator with structure, created new edge list and size respective to root dist
ance+1
 *    -# no: stores fragment into keyset list by calling InsertFragmentIntoGraph
 *  -# removes all items added into the snake stack (in UniqueFragments structure) added during level (root
distance) and current set
 * \param *out output stream for debugging
 * \param FragmentSearch UniqueFragments structure with all values needed
 * \param RootDistance current shortest path level, whose set of edges is represented by **BondsSet
 * \param SetDimension Number of possible bonds on this level (i.e. size of the array BondsSet[])
 * \param SubOrder remaining number of allowed vertices to add
 */
void molecule::SPFragmentGenerator(ofstream *out, struct UniqueFragments *FragmentSearch, int RootDistance, bond **BondsSet, int SetDimension, int SubOrder)
{
  atom *OtherWalker = NULL;
  int verbosity = 0; //FragmentSearch->ANOVAOrder-SubOrder;
  int NumCombinations;
  bool bit;
  int bits, TouchedIndex, SubSetDimension, SP, Added;
  int Removal;
  int SpaceLeft;
  int *TouchedList = (int *) Malloc(sizeof(int)*(SubOrder+1), "molecule::SPFragmentGenerator: *TouchedList");
  bond *Binder = NULL;
  bond **BondsList = NULL;
  KeySetTestPair TestKeySetInsert;

  NumCombinations = 1 << SetDimension;

  // Hier muessen von 1 bis NumberOfBondsPerAtom[Walker->nr] alle Kombinationen
  // von Endstuecken (aus den Bonds) hinzugefￜￜgt werden und fￜￜr verbleibende ANOVAOrder
  // rekursiv GraphCrawler in der nￜￜchsten Ebene aufgerufen werden

  *out << Verbose(1+verbosity) << "Begin of SPFragmentGenerator." << endl;
  *out << Verbose(1+verbosity) << "We are " << RootDistance << " away from Root, which is " << *FragmentSearch->Root << ", SubOrder is " << SubOrder << ", SetDimension is " << SetDimension << " and this means " <<  NumCombinations-1 << " combination(s)." << endl;

  // initialised touched list (stores added atoms on this level)
  *out << Verbose(1+verbosity) << "Clearing touched list." << endl;
  for (TouchedIndex=SubOrder+1;TouchedIndex--;)  // empty touched list
    TouchedList[TouchedIndex] = -1;
  TouchedIndex = 0;

  // create every possible combination of the endpieces
  *out << Verbose(1+verbosity) << "Going through all combinations of the power set." << endl;
  for (int i=1;i<NumCombinations;i++) {  // sweep through all power set combinations (skip empty set!)
    // count the set bit of i
    bits = 0;
    for (int j=SetDimension;j--;)
      bits += (i & (1 << j)) >> j;

    *out << Verbose(1+verbosity) << "Current set is " << Binary(i | (1 << SetDimension)) << ", number of bits is " << bits << "." << endl;
    if (bits <= SubOrder) { // if not greater than additional atoms allowed on stack, continue
      // --1-- add this set of the power set of bond partners to the snake stack
      Added = 0;
      for (int j=0;j<SetDimension;j++) {  // pull out every bit by shifting
        bit = ((i & (1 << j)) != 0);  // mask the bit for the j-th bond
        if (bit) {  // if bit is set, we add this bond partner
          OtherWalker = BondsSet[j]->rightatom;  // rightatom is always the one more distant, i.e. the one to add
          //*out << Verbose(1+verbosity) << "Current Bond is " << ListOfBondsPerAtom[Walker->nr][i] << ", checking on " << *OtherWalker << "." << endl;
          *out << Verbose(2+verbosity) << "Adding " << *OtherWalker << " with nr " << OtherWalker->nr << "." << endl;
          TestKeySetInsert = FragmentSearch->FragmentSet->insert(OtherWalker->nr);
          if (TestKeySetInsert.second) {
            TouchedList[TouchedIndex++] = OtherWalker->nr;  // note as added
            Added++;
          } else {
            *out << Verbose(2+verbosity) << "This was item was already present in the keyset." << endl;
          }
            //FragmentSearch->UsedList[OtherWalker->nr][i] = true;
          //}
        } else {
          *out << Verbose(2+verbosity) << "Not adding." << endl;
        }
      }

      SpaceLeft = SubOrder - Added ;// SubOrder - bits; // due to item's maybe being already present, this does not work anymore
      if (SpaceLeft > 0) {
        *out << Verbose(1+verbosity) << "There's still some space left on stack: " << SpaceLeft << "." << endl;
        if (SubOrder > 1) {    // Due to Added above we have to check extra whether we're not already reaching beyond the desired Order
          // --2-- look at all added end pieces of this combination, construct bond subsets and sweep through a power set of these by recursion
          SP = RootDistance+1;  // this is the next level
          // first count the members in the subset
          SubSetDimension = 0;
          Binder = FragmentSearch->BondsPerSPList[2*SP];    // start node for this level
          while (Binder->next != FragmentSearch->BondsPerSPList[2*SP+1]) {    // compare to end node of this level
            Binder = Binder->next;
            for (int k=TouchedIndex;k--;) {
              if (Binder->Contains(TouchedList[k]))   // if we added this very endpiece
                SubSetDimension++;
            }
          }
          // then allocate and fill the list
          BondsList = (bond **) Malloc(sizeof(bond *)*SubSetDimension, "molecule::SPFragmentGenerator: **BondsList");
          SubSetDimension = 0;
          Binder = FragmentSearch->BondsPerSPList[2*SP];
          while (Binder->next != FragmentSearch->BondsPerSPList[2*SP+1]) {
            Binder = Binder->next;
            for (int k=0;k<TouchedIndex;k++) {
              if (Binder->leftatom->nr == TouchedList[k])   // leftatom is always the close one
                BondsList[SubSetDimension++] = Binder;
            }
          }
          *out << Verbose(2+verbosity) << "Calling subset generator " << SP << " away from root " << *FragmentSearch->Root << " with sub set dimension " << SubSetDimension << "." << endl;
          SPFragmentGenerator(out, FragmentSearch, SP, BondsList, SubSetDimension, SubOrder-bits);
          Free((void **)&BondsList, "molecule::SPFragmentGenerator: **BondsList");
        }
      } else {
        // --2-- otherwise store the complete fragment
        *out << Verbose(1+verbosity) << "Enough items on stack for a fragment!" << endl;
        // store fragment as a KeySet
        *out << Verbose(2) << "Found a new fragment[" << FragmentSearch->FragmentCounter << "], local nr.s are: ";
        for(KeySet::iterator runner = FragmentSearch->FragmentSet->begin(); runner != FragmentSearch->FragmentSet->end(); runner++)
          *out << (*runner) << " ";
        *out << endl;
        //if (!CheckForConnectedSubgraph(out, FragmentSearch->FragmentSet))
          //*out << Verbose(0) << "ERROR: The found fragment is not a connected subgraph!" << endl;
        InsertFragmentIntoGraph(out, FragmentSearch);
        //Removal = LookForRemovalCandidate(out, FragmentSearch->FragmentSet, FragmentSearch->ShortestPathList);
        //Removal = StoreFragmentFromStack(out, FragmentSearch->Root, FragmentSearch->Leaflet, FragmentSearch->FragmentStack, FragmentSearch->ShortestPathList, &FragmentSearch->FragmentCounter, FragmentSearch->configuration);
      }

      // --3-- remove all added items in this level from snake stack
      *out << Verbose(1+verbosity) << "Removing all items that were added on this SP level " << RootDistance << "." << endl;
      for(int j=0;j<TouchedIndex;j++) {
        Removal = TouchedList[j];
        *out << Verbose(2+verbosity) << "Removing item nr. " << Removal << " from snake stack." << endl;
        FragmentSearch->FragmentSet->erase(Removal);
        TouchedList[j] = -1;
      }
      *out << Verbose(2) << "Remaining local nr.s on snake stack are: ";
      for(KeySet::iterator runner = FragmentSearch->FragmentSet->begin(); runner != FragmentSearch->FragmentSet->end(); runner++)
        *out << (*runner) << " ";
      *out << endl;
      TouchedIndex = 0; // set Index to 0 for list of atoms added on this level
    } else {
      *out << Verbose(2+verbosity) << "More atoms to add for this set (" << bits << ") than space left on stack " << SubOrder << ", skipping this set." << endl;
    }
  }
  Free((void **)&TouchedList, "molecule::SPFragmentGenerator: *TouchedList");
  *out << Verbose(1+verbosity) << "End of SPFragmentGenerator, " << RootDistance << " away from Root " << *FragmentSearch->Root << " and SubOrder is " << SubOrder << "." << endl;
};

/** For a given keyset \a *Fragment, checks whether it is connected in the current molecule.
 * \param *out output stream for debugging
 * \param *Fragment Keyset of fragment's vertices
 * \return true - connected, false - disconnected
 * \note this is O(n^2) for it's just a bug checker not meant for permanent use!
 */
bool molecule::CheckForConnectedSubgraph(ofstream *out, KeySet *Fragment)
{
  atom *Walker = NULL, *Walker2 = NULL;
  bool BondStatus = false;
  int size;

  *out << Verbose(1) << "Begin of CheckForConnectedSubgraph" << endl;
  *out << Verbose(2) << "Disconnected atom: ";

  // count number of atoms in graph
  size = 0;
  for(KeySet::iterator runner = Fragment->begin(); runner != Fragment->end(); runner++)
    size++;
  if (size > 1)
    for(KeySet::iterator runner = Fragment->begin(); runner != Fragment->end(); runner++) {
      Walker = FindAtom(*runner);
      BondStatus = false;
      for(KeySet::iterator runners = Fragment->begin(); runners != Fragment->end(); runners++) {
        Walker2 = FindAtom(*runners);
        for (int i=0;i<NumberOfBondsPerAtom[Walker->nr]; i++) {
          if (ListOfBondsPerAtom[Walker->nr][i]->GetOtherAtom(Walker) == Walker2) {
            BondStatus = true;
            break;
          }
          if (BondStatus)
            break;
        }
      }
      if (!BondStatus) {
        *out << (*Walker) << endl;
        return false;
      }
    }
  else {
    *out << "none." << endl;
    return true;
  }
  *out << "none." << endl;

  *out << Verbose(1) << "End of CheckForConnectedSubgraph" << endl;

  return true;
}

/** Creates a list of all unique fragments of certain vertex size from a given graph \a Fragment for a given root vertex in the context of \a this molecule.
 * -# initialises UniqueFragments structure
 * -# fills edge list via BFS
 * -# creates the fragment by calling recursive function SPFragmentGenerator with UniqueFragments structure, 0 as
 root distance, the edge set, its dimension and the current suborder
 * -# Free'ing structure
 * Note that we may use the fact that the atoms are SP-ordered on the atomstack. I.e. when popping always the last, we first get all
 * with SP of 2, then those with SP of 3, then those with SP of 4 and so on.
 * \param *out output stream for debugging
 * \param Order bond order (limits BFS exploration and "number of digits" in power set generation
 * \param FragmentSearch UniqueFragments structure containing TEFactor, root atom and so on
 * \param RestrictedKeySet Restricted vertex set to use in context of molecule
 * \return number of inserted fragments
 * \note ShortestPathList in FragmentSearch structure is probably due to NumberOfAtomsSPLevel and SP not needed anymore
 */
int molecule::PowerSetGenerator(ofstream *out, int Order, struct UniqueFragments &FragmentSearch, KeySet RestrictedKeySet)
{
  int SP, AtomKeyNr;
  atom *Walker = NULL, *OtherWalker = NULL, *Predecessor = NULL;
  bond *Binder = NULL;
  bond *CurrentEdge = NULL;
  bond **BondsList = NULL;
  int RootKeyNr = FragmentSearch.Root->GetTrueFather()->nr;
  int Counter = FragmentSearch.FragmentCounter;
  int RemainingWalkers;

  *out << endl;
  *out << Verbose(0) << "Begin of PowerSetGenerator with order " << Order << " at Root " << *FragmentSearch.Root << "." << endl;

  // prepare Label and SP arrays of the BFS search
  FragmentSearch.ShortestPathList[FragmentSearch.Root->nr] = 0;

  // prepare root level (SP = 0) and a loop bond denoting Root
  for (int i=1;i<Order;i++)
    FragmentSearch.BondsPerSPCount[i] = 0;
  FragmentSearch.BondsPerSPCount[0] = 1;
  Binder = new bond(FragmentSearch.Root, FragmentSearch.Root);
  add(Binder, FragmentSearch.BondsPerSPList[1]);

  // do a BFS search to fill the SP lists and label the found vertices
  // 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.
  *out << endl;
  *out << Verbose(0) << "Starting BFS analysis ..." << endl;
  for (SP = 0; SP < (Order-1); SP++) {
    *out << Verbose(1) << "New SP level reached: " << SP << ", creating new SP list with " << FragmentSearch.BondsPerSPCount[SP] << " item(s)";
    if (SP > 0) {
      *out << ", old level closed with " << FragmentSearch.BondsPerSPCount[SP-1] << " item(s)." << endl;
      FragmentSearch.BondsPerSPCount[SP] = 0;
    } else
      *out << "." << endl;

    RemainingWalkers = FragmentSearch.BondsPerSPCount[SP];
    CurrentEdge = FragmentSearch.BondsPerSPList[2*SP];    /// start of this SP level's list
    while (CurrentEdge->next != FragmentSearch.BondsPerSPList[2*SP+1]) {    /// end of this SP level's list
      CurrentEdge = CurrentEdge->next;
      RemainingWalkers--;
      Walker = CurrentEdge->rightatom;    // rightatom is always the one more distant
      Predecessor = CurrentEdge->leftatom;    // ... and leftatom is predecessor
      AtomKeyNr = Walker->nr;
      *out << Verbose(0) << "Current Walker is: " << *Walker << " with nr " << Walker->nr << " and SP of " << SP << ", with " << RemainingWalkers << " remaining walkers on this level." << endl;
      // check for new sp level
      // go through all its bonds
      *out << Verbose(1) << "Going through all bonds of Walker." << endl;
      for (int i=0;i<NumberOfBondsPerAtom[AtomKeyNr];i++) {
        Binder = ListOfBondsPerAtom[AtomKeyNr][i];
        OtherWalker = Binder->GetOtherAtom(Walker);
        if ((RestrictedKeySet.find(OtherWalker->nr) != RestrictedKeySet.end())
  #ifdef ADDHYDROGEN
         && (OtherWalker->type->Z != 1)
  #endif
                                                              ) {  // skip hydrogens and restrict to fragment
          *out << Verbose(2) << "Current partner is " << *OtherWalker << " with nr " << OtherWalker->nr << " in bond " << *Binder << "." << endl;
          // set the label if not set (and push on root stack as well)
          if ((OtherWalker != Predecessor) && (OtherWalker->GetTrueFather()->nr > RootKeyNr)) { // only pass through those with label bigger than Root's
            FragmentSearch.ShortestPathList[OtherWalker->nr] = SP+1;
            *out << Verbose(3) << "Set Shortest Path to " << FragmentSearch.ShortestPathList[OtherWalker->nr] << "." << endl;
            // 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
            add(Binder, FragmentSearch.BondsPerSPList[2*(SP+1)+1]);
            FragmentSearch.BondsPerSPCount[SP+1]++;
            *out << Verbose(3) << "Added its bond to SP list, having now " << FragmentSearch.BondsPerSPCount[SP+1] << " item(s)." << endl;
          } else {
            if (OtherWalker != Predecessor)
              *out << Verbose(3) << "Not passing on, as index of " << *OtherWalker << " " << OtherWalker->GetTrueFather()->nr << " is smaller than that of Root " << RootKeyNr << "." << endl;
            else
              *out << Verbose(3) << "This is my predecessor " << *Predecessor << "." << endl;
          }
        } else *out << Verbose(2) << "Is not in the restricted keyset or skipping hydrogen " << *OtherWalker << "." << endl;
      }
    }
  }

  // outputting all list for debugging
  *out << Verbose(0) << "Printing all found lists." << endl;
  for(int i=1;i<Order;i++) {    // skip the root edge in the printing
    Binder = FragmentSearch.BondsPerSPList[2*i];
    *out << Verbose(1) << "Current SP level is " << i << "." << endl;
    while (Binder->next != FragmentSearch.BondsPerSPList[2*i+1]) {
      Binder = Binder->next;
      *out << Verbose(2) << *Binder << endl;
    }
  }

  // creating fragments with the found edge sets  (may be done in reverse order, faster)
  SP = -1;  // the Root <-> Root edge must be subtracted!
  for(int i=Order;i--;) { // sum up all found edges
    Binder = FragmentSearch.BondsPerSPList[2*i];
    while (Binder->next != FragmentSearch.BondsPerSPList[2*i+1]) {
      Binder = Binder->next;
      SP ++;
    }
  }
  *out << Verbose(0) << "Total number of edges is " << SP << "." << endl;
  if (SP >= (Order-1)) {
    // start with root (push on fragment stack)
    *out << Verbose(0) << "Starting fragment generation with " << *FragmentSearch.Root << ", local nr is " << FragmentSearch.Root->nr << "." << endl;
    FragmentSearch.FragmentSet->clear();
    *out << Verbose(0) << "Preparing subset for this root and calling generator." << endl;
    // prepare the subset and call the generator
    BondsList = (bond **) Malloc(sizeof(bond *)*FragmentSearch.BondsPerSPCount[0], "molecule::PowerSetGenerator: **BondsList");
    BondsList[0] = FragmentSearch.BondsPerSPList[0]->next;  // on SP level 0 there's only the root bond

    SPFragmentGenerator(out, &FragmentSearch, 0, BondsList, FragmentSearch.BondsPerSPCount[0], Order);

    Free((void **)&BondsList, "molecule::PowerSetGenerator: **BondsList");
  } else {
    *out << Verbose(0) << "Not enough total number of edges to build " << Order << "-body fragments." << endl;
  }

  // as FragmentSearch structure is used only once, we don't have to clean it anymore
  // remove root from stack
  *out << Verbose(0) << "Removing root again from stack." << endl;
  FragmentSearch.FragmentSet->erase(FragmentSearch.Root->nr);

  // free'ing the bonds lists
  *out << Verbose(0) << "Free'ing all found lists. and resetting index lists" << endl;
  for(int i=Order;i--;) {
    *out << Verbose(1) << "Current SP level is " << i << ": ";
    Binder = FragmentSearch.BondsPerSPList[2*i];
    while (Binder->next != FragmentSearch.BondsPerSPList[2*i+1]) {
      Binder = Binder->next;
      // *out << "Removing atom " << Binder->leftatom->nr << " and " << Binder->rightatom->nr << "." << endl; // make sure numbers are local
      FragmentSearch.ShortestPathList[Binder->leftatom->nr] = -1;
      FragmentSearch.ShortestPathList[Binder->rightatom->nr] = -1;
    }
    // delete added bonds
    cleanup(FragmentSearch.BondsPerSPList[2*i], FragmentSearch.BondsPerSPList[2*i+1]);
    // also start and end node
    *out << "cleaned." << endl;
  }

  // return list
  *out << Verbose(0) << "End of PowerSetGenerator." << endl;
  return (FragmentSearch.FragmentCounter - Counter);
};

/** Corrects the nuclei position if the fragment was created over the cell borders.
 * Scans all bonds, checks the distance, if greater than typical, we have a candidate for the correction.
 * We remove the bond whereafter the graph probably separates. Then, we translate the one component periodically
 * and re-add the bond. Looping on the distance check.
 * \param *out ofstream for debugging messages
 */
void molecule::ScanForPeriodicCorrection(ofstream *out)
{
  bond *Binder = NULL;
  bond *OtherBinder = NULL;
  atom *Walker = NULL;
  atom *OtherWalker = NULL;
  double *matrix = ReturnFullMatrixforSymmetric(cell_size);
  enum Shading *ColorList = NULL;
  double tmp;
  Vector Translationvector;
  //class StackClass<atom *> *CompStack = NULL;
  class StackClass<atom *> *AtomStack = new StackClass<atom *>(AtomCount);
  bool flag = true;

  *out << Verbose(2) << "Begin of ScanForPeriodicCorrection." << endl;

  ColorList = (enum Shading *) Malloc(sizeof(enum Shading)*AtomCount, "molecule::ScanForPeriodicCorrection: *ColorList");
  while (flag) {
    // remove bonds that are beyond bonddistance
    for(int i=NDIM;i--;)
      Translationvector.x[i] = 0.;
    // scan all bonds
    Binder = first;
    flag = false;
    while ((!flag) && (Binder->next != last)) {
      Binder = Binder->next;
      for (int i=NDIM;i--;) {
        tmp = fabs(Binder->leftatom->x.x[i] - Binder->rightatom->x.x[i]);
        //*out << Verbose(3) << "Checking " << i << "th distance of " << *Binder->leftatom << " to " << *Binder->rightatom << ": " << tmp << "." << endl;
        if (tmp > BondDistance) {
          OtherBinder = Binder->next; // note down binding partner for later re-insertion
          unlink(Binder);   // unlink bond
          *out << Verbose(2) << "Correcting at bond " << *Binder << "." << endl;
          flag = true;
          break;
        }
      }
    }
    if (flag) {
      // create translation vector from their periodically modified distance
      for (int i=NDIM;i--;) {
        tmp = Binder->leftatom->x.x[i] - Binder->rightatom->x.x[i];
        if (fabs(tmp) > BondDistance)
          Translationvector.x[i] = (tmp < 0) ? +1. : -1.;
      }
      Translationvector.MatrixMultiplication(matrix);
      //*out << Verbose(3) << "Translation vector is ";
      Translationvector.Output(out);
      *out << endl;
      // apply to all atoms of first component via BFS
      for (int i=AtomCount;i--;)
        ColorList[i] = white;
      AtomStack->Push(Binder->leftatom);
      while (!AtomStack->IsEmpty()) {
        Walker = AtomStack->PopFirst();
        //*out << Verbose (3) << "Current Walker is: " << *Walker << "." << endl;
        ColorList[Walker->nr] = black;    // mark as explored
        Walker->x.AddVector(&Translationvector); // translate
        for (int i=0;i<NumberOfBondsPerAtom[Walker->nr];i++) {  // go through all binding partners
          if (ListOfBondsPerAtom[Walker->nr][i] != Binder) {
            OtherWalker = ListOfBondsPerAtom[Walker->nr][i]->GetOtherAtom(Walker);
            if (ColorList[OtherWalker->nr] == white) {
              AtomStack->Push(OtherWalker); // push if yet unexplored
            }
          }
        }
      }
      // re-add bond
      link(Binder, OtherBinder);
    } else {
      *out << Verbose(3) << "No corrections for this fragment." << endl;
    }
    //delete(CompStack);
  }

  // free allocated space from ReturnFullMatrixforSymmetric()
  delete(AtomStack);
  Free((void **)&ColorList, "molecule::ScanForPeriodicCorrection: *ColorList");
  Free((void **)&matrix, "molecule::ScanForPeriodicCorrection: *matrix");
  *out << Verbose(2) << "End of ScanForPeriodicCorrection." << endl;
};

/** Blows the 6-dimensional \a cell_size array up to a full NDIM by NDIM matrix.
 * \param *symm 6-dim array of unique symmetric matrix components
 * \return allocated NDIM*NDIM array with the symmetric matrix
 */
double * molecule::ReturnFullMatrixforSymmetric(double *symm)
{
  double *matrix = (double *) Malloc(sizeof(double)*NDIM*NDIM, "molecule::ReturnFullMatrixforSymmetric: *matrix");
  matrix[0] = symm[0];
  matrix[1] = symm[1];
  matrix[2] = symm[3];
  matrix[3] = symm[1];
  matrix[4] = symm[2];
  matrix[5] = symm[4];
  matrix[6] = symm[3];
  matrix[7] = symm[4];
  matrix[8] = symm[5];
  return matrix;
};

bool KeyCompare::operator() (const KeySet SubgraphA, const KeySet SubgraphB) const
{
  //cout << "my check is used." << endl;
  if (SubgraphA.size() < SubgraphB.size()) {
    return true;
  } else {
    if (SubgraphA.size() > SubgraphB.size()) {
      return false;
    } else {
      KeySet::iterator IteratorA = SubgraphA.begin();
      KeySet::iterator IteratorB = SubgraphB.begin();
      while ((IteratorA != SubgraphA.end()) && (IteratorB != SubgraphB.end())) {
        if ((*IteratorA) <  (*IteratorB))
          return true;
        else if ((*IteratorA) > (*IteratorB)) {
            return false;
          } // else, go on to next index
        IteratorA++;
        IteratorB++;
      } // end of while loop
    }// end of check in case of equal sizes
  }
  return false; // if we reach this point, they are equal
};

//bool operator < (KeySet SubgraphA, KeySet SubgraphB)
//{
//  return KeyCompare(SubgraphA, SubgraphB);
//};

/** Checking whether KeySet is not already present in Graph, if so just adds factor.
 * \param *out output stream for debugging
 * \param &set KeySet to insert
 * \param &graph Graph to insert into
 * \param *counter pointer to unique fragment count
 * \param factor energy factor for the fragment
 */
inline void InsertFragmentIntoGraph(ofstream *out, struct UniqueFragments *Fragment)
{
  GraphTestPair testGraphInsert;

  testGraphInsert = Fragment->Leaflet->insert(GraphPair (*Fragment->FragmentSet,pair<int,double>(Fragment->FragmentCounter,Fragment->TEFactor)));  // store fragment number and current factor
  if (testGraphInsert.second) {
    *out << Verbose(2) << "KeySet " << Fragment->FragmentCounter << " successfully inserted." << endl;
    Fragment->FragmentCounter++;
  } else {
    *out << Verbose(2) << "KeySet " << Fragment->FragmentCounter << " failed to insert, present fragment is " << ((*(testGraphInsert.first)).second).first << endl;
    ((*(testGraphInsert.first)).second).second += Fragment->TEFactor;  // increase the "created" counter
    *out << Verbose(2) << "New factor is " << ((*(testGraphInsert.first)).second).second << "." << endl;
  }
};
//void inline InsertIntoGraph(ofstream *out, KeyStack &stack, Graph &graph, int *counter, double factor)
//{
//  // copy stack contents to set and call overloaded function again
//  KeySet set;
//  for(KeyStack::iterator runner = stack.begin(); runner != stack.begin(); runner++)
//    set.insert((*runner));
//  InsertIntoGraph(out, set, graph, counter, factor);
//};

/** Inserts each KeySet in \a graph2 into \a graph1.
 * \param *out output stream for debugging
 * \param graph1 first (dest) graph
 * \param graph2 second (source) graph
 * \param *counter keyset counter that gets increased
 */
inline void InsertGraphIntoGraph(ofstream *out, Graph &graph1, Graph &graph2, int *counter)
{
  GraphTestPair testGraphInsert;

  for(Graph::iterator runner = graph2.begin(); runner != graph2.end(); runner++) {
    testGraphInsert = graph1.insert(GraphPair ((*runner).first,pair<int,double>((*counter)++,((*runner).second).second)));  // store fragment number and current factor
    if (testGraphInsert.second) {
      *out << Verbose(2) << "KeySet " << (*counter)-1 << " successfully inserted." << endl;
    } else {
      *out << Verbose(2) << "KeySet " << (*counter)-1 << " failed to insert, present fragment is " << ((*(testGraphInsert.first)).second).first << endl;
      ((*(testGraphInsert.first)).second).second += (*runner).second.second;
      *out << Verbose(2) << "New factor is " << (*(testGraphInsert.first)).second.second << "." << endl;
    }
  }
};


/** Performs BOSSANOVA decomposition at selected sites, increasing the cutoff by one at these sites.
 * -# constructs a complete keyset of the molecule
 * -# In a loop over all possible roots from the given rootstack
 *  -# increases order of root site
 *  -# calls PowerSetGenerator with this order, the complete keyset and the rootkeynr
 *  -# for all consecutive lower levels PowerSetGenerator is called with the suborder, the higher order keyset
as the restricted one and each site in the set as the root)
 *  -# these are merged into a fragment list of keysets
 * -# All fragment lists (for all orders, i.e. from all destination fields) are merged into one list for return
 * Important only is that we create all fragments, it is not important if we create them more than once
 * as these copies are filtered out via use of the hash table (KeySet).
 * \param *out output stream for debugging
 * \param Fragment&*List list of already present keystacks (adaptive scheme) or empty list
 * \param &RootStack stack with all root candidates (unequal to each atom in complete molecule if adaptive scheme is applied)
 * \param *MinimumRingSize minimum ring size for each atom (molecule::Atomcount)
 * \return pointer to Graph list
 */
void molecule::FragmentBOSSANOVA(ofstream *out, Graph *&FragmentList, KeyStack &RootStack, int *MinimumRingSize)
{
  Graph ***FragmentLowerOrdersList = NULL;
  int NumLevels, NumMolecules, TotalNumMolecules = 0, *NumMoleculesOfOrder = NULL;
  int counter = 0, Order;
  int UpgradeCount = RootStack.size();
  KeyStack FragmentRootStack;
  int RootKeyNr, RootNr;
  struct UniqueFragments FragmentSearch;

  *out << Verbose(0) << "Begin of FragmentBOSSANOVA." << endl;

  // FragmentLowerOrdersList is a 2D-array of pointer to MoleculeListClass objects, one dimension represents the ANOVA expansion of a single order (i.e. 5)
  // with all needed lower orders that are subtracted, the other dimension is the BondOrder (i.e. from 1 to 5)
  NumMoleculesOfOrder = (int *) Malloc(sizeof(int)*UpgradeCount, "molecule::FragmentBOSSANOVA: *NumMoleculesOfOrder");
  FragmentLowerOrdersList = (Graph ***) Malloc(sizeof(Graph **)*UpgradeCount, "molecule::FragmentBOSSANOVA: ***FragmentLowerOrdersList");

  // initialise the fragments structure
  FragmentSearch.ShortestPathList = (int *) Malloc(sizeof(int)*AtomCount, "molecule::PowerSetGenerator: *ShortestPathList");
  FragmentSearch.FragmentCounter = 0;
  FragmentSearch.FragmentSet = new KeySet;
  FragmentSearch.Root = FindAtom(RootKeyNr);
  for (int i=AtomCount;i--;) {
    FragmentSearch.ShortestPathList[i] = -1;
  }

  // Construct the complete KeySet which we need for topmost level only (but for all Roots)
  atom *Walker = start;
  KeySet CompleteMolecule;
  while (Walker->next != end) {
    Walker = Walker->next;
    CompleteMolecule.insert(Walker->GetTrueFather()->nr);
  }

  // this can easily be seen: if Order is 5, then the number of levels for each lower order is the total sum of the number of levels above, as
  // each has to be split up. E.g. for the second level we have one from 5th, one from 4th, two from 3th (which in turn is one from 5th, one from 4th),
  // hence we have overall four 2th order levels for splitting. This also allows for putting all into a single array (FragmentLowerOrdersList[])
  // with the order along the cells as this: 5433222211111111 for BondOrder 5 needing 16=pow(2,5-1) cells (only we use bit-shifting which is faster)
  RootNr = 0;   // counts through the roots in RootStack
  while ((RootNr < UpgradeCount) && (!RootStack.empty())) {
    RootKeyNr = RootStack.front();
    RootStack.pop_front();
    Walker = FindAtom(RootKeyNr);
    // check cyclic lengths
    //if ((MinimumRingSize[Walker->GetTrueFather()->nr] != -1) && (Walker->GetTrueFather()->AdaptiveOrder+1 > MinimumRingSize[Walker->GetTrueFather()->nr])) {
    //  *out << Verbose(0) << "Bond order " << Walker->GetTrueFather()->AdaptiveOrder << " of Root " << *Walker << " greater than or equal to Minimum Ring size of " << MinimumRingSize << " found is not allowed." << endl;
    //} else
    {
      // increase adaptive order by one
      Walker->GetTrueFather()->AdaptiveOrder++;
      Order = Walker->AdaptiveOrder = Walker->GetTrueFather()->AdaptiveOrder;

      // initialise Order-dependent entries of UniqueFragments structure
      FragmentSearch.BondsPerSPList = (bond **) Malloc(sizeof(bond *)*Order*2, "molecule::PowerSetGenerator: ***BondsPerSPList");
      FragmentSearch.BondsPerSPCount = (int *) Malloc(sizeof(int)*Order, "molecule::PowerSetGenerator: *BondsPerSPCount");
      for (int i=Order;i--;) {
        FragmentSearch.BondsPerSPList[2*i] = new bond();    // start node
        FragmentSearch.BondsPerSPList[2*i+1] = new bond();  // end node
        FragmentSearch.BondsPerSPList[2*i]->next = FragmentSearch.BondsPerSPList[2*i+1];     // intertwine these two
        FragmentSearch.BondsPerSPList[2*i+1]->previous = FragmentSearch.BondsPerSPList[2*i];
        FragmentSearch.BondsPerSPCount[i] = 0;
      }

      // allocate memory for all lower level orders in this 1D-array of ptrs
      NumLevels = 1 << (Order-1); // (int)pow(2,Order);
      FragmentLowerOrdersList[RootNr] = (Graph **) Malloc(sizeof(Graph *)*NumLevels, "molecule::FragmentBOSSANOVA: **FragmentLowerOrdersList[]");
      for (int i=0;i<NumLevels;i++)
        FragmentLowerOrdersList[RootNr][i] = NULL;

      // create top order where nothing is reduced
      *out << Verbose(0) << "==============================================================================================================" << endl;
      *out << Verbose(0) << "Creating KeySets of Bond Order " << Order << " for " << *Walker << ", " << (RootStack.size()-RootNr) << " Roots remaining." << endl; // , NumLevels is " << NumLevels << "

      // Create list of Graphs of current Bond Order (i.e. F_{ij})
      FragmentLowerOrdersList[RootNr][0] =  new Graph;
      FragmentSearch.TEFactor = 1.;
      FragmentSearch.Leaflet = FragmentLowerOrdersList[RootNr][0];      // set to insertion graph
      FragmentSearch.Root = Walker;
      NumMoleculesOfOrder[RootNr] = PowerSetGenerator(out, Walker->AdaptiveOrder, FragmentSearch, CompleteMolecule);
      *out << Verbose(1) << "Number of resulting KeySets is: " << NumMoleculesOfOrder[RootNr] << "." << endl;
      if (NumMoleculesOfOrder[RootNr] != 0) {
        NumMolecules = 0;

        // we don't have to dive into suborders! These keysets are all already created on lower orders!
        // this was all ancient stuff, when we still depended on the TEFactors (and for those the suborders were needed)

//        if ((NumLevels >> 1) > 0) {
//          // create lower order fragments
//          *out << Verbose(0) << "Creating list of unique fragments of lower Bond Order terms to be subtracted." << endl;
//          Order = Walker->AdaptiveOrder;
//          for (int source=0;source<(NumLevels >> 1);source++) { // 1-terms don't need any more splitting, that's why only half is gone through (shift again)
//            // step down to next order at (virtual) boundary of powers of 2 in array
//            while (source >= (1 << (Walker->AdaptiveOrder-Order))) // (int)pow(2,Walker->AdaptiveOrder-Order))
//              Order--;
//            *out << Verbose(0) << "Current Order is: " << Order << "." << endl;
//            for (int SubOrder=Order-1;SubOrder>0;SubOrder--) {
//              int dest = source + (1 << (Walker->AdaptiveOrder-(SubOrder+1)));
//              *out << Verbose(0) << "--------------------------------------------------------------------------------------------------------------" << endl;
//              *out << Verbose(0) << "Current SubOrder is: " << SubOrder << " with source " << source << " to destination " << dest << "." << endl;
//
//              // every molecule is split into a list of again (Order - 1) molecules, while counting all molecules
//              //*out << Verbose(1) << "Splitting the " << (*FragmentLowerOrdersList[RootNr][source]).size() << " molecules of the " << source << "th cell in the array." << endl;
//              //NumMolecules = 0;
//              FragmentLowerOrdersList[RootNr][dest] = new Graph;
//              for(Graph::iterator runner = (*FragmentLowerOrdersList[RootNr][source]).begin();runner != (*FragmentLowerOrdersList[RootNr][source]).end(); runner++) {
//                for (KeySet::iterator sprinter = (*runner).first.begin();sprinter != (*runner).first.end(); sprinter++) {
//                  Graph TempFragmentList;
//                  FragmentSearch.TEFactor = -(*runner).second.second;
//                  FragmentSearch.Leaflet = &TempFragmentList;      // set to insertion graph
//                  FragmentSearch.Root = FindAtom(*sprinter);
//                  NumMoleculesOfOrder[RootNr] += PowerSetGenerator(out, SubOrder, FragmentSearch, (*runner).first);
//                  // insert new keysets FragmentList into FragmentLowerOrdersList[Walker->AdaptiveOrder-1][dest]
//                  *out << Verbose(1) << "Merging resulting key sets with those present in destination " << dest << "." << endl;
//                  InsertGraphIntoGraph(out, *FragmentLowerOrdersList[RootNr][dest], TempFragmentList, &NumMolecules);
//                }
//              }
//              *out << Verbose(1) << "Number of resulting molecules for SubOrder " << SubOrder << " is: " << NumMolecules << "." << endl;
//            }
//          }
//        }
      } else {
        Walker->GetTrueFather()->MaxOrder = true;
//        *out << Verbose(1) << "Hence, we don't dive into SubOrders ... " << endl;
      }
      // now, we have completely filled each cell of FragmentLowerOrdersList[] for the current Walker->AdaptiveOrder
      //NumMoleculesOfOrder[Walker->AdaptiveOrder-1] = NumMolecules;
      TotalNumMolecules += NumMoleculesOfOrder[RootNr];
//      *out << Verbose(1) << "Number of resulting molecules for Order " << (int)Walker->GetTrueFather()->AdaptiveOrder << " is: " << NumMoleculesOfOrder[RootNr] << "." << endl;
      RootStack.push_back(RootKeyNr); // put back on stack
      RootNr++;

      // free Order-dependent entries of UniqueFragments structure for next loop cycle
      Free((void **)&FragmentSearch.BondsPerSPCount, "molecule::PowerSetGenerator: *BondsPerSPCount");
      for (int i=Order;i--;) {
        delete(FragmentSearch.BondsPerSPList[2*i]);
        delete(FragmentSearch.BondsPerSPList[2*i+1]);
      }
      Free((void **)&FragmentSearch.BondsPerSPList, "molecule::PowerSetGenerator: ***BondsPerSPList");
    }
  }
  *out << Verbose(0) << "==============================================================================================================" << endl;
  *out << Verbose(1) << "Total number of resulting molecules is: " << TotalNumMolecules << "." << endl;
  *out << Verbose(0) << "==============================================================================================================" << endl;

  // cleanup FragmentSearch structure
  Free((void **)&FragmentSearch.ShortestPathList, "molecule::PowerSetGenerator: *ShortestPathList");
  delete(FragmentSearch.FragmentSet);

  // now, FragmentLowerOrdersList is complete, it looks - for BondOrder 5 - as this (number is the ANOVA Order of the terms therein)
  // 5433222211111111
  // 43221111
  // 3211
  // 21
  // 1

  // Subsequently, we combine all into a single list (FragmentList)

  *out << Verbose(0) << "Combining the lists of all orders per order and finally into a single one." << endl;
  if (FragmentList == NULL) {
    FragmentList = new Graph;
    counter = 0;
  } else {
    counter = FragmentList->size();
  }
  RootNr = 0;
  while (!RootStack.empty()) {
    RootKeyNr = RootStack.front();
    RootStack.pop_front();
    Walker = FindAtom(RootKeyNr);
    NumLevels = 1 << (Walker->AdaptiveOrder - 1);
    for(int i=0;i<NumLevels;i++) {
      if (FragmentLowerOrdersList[RootNr][i] != NULL) {
        InsertGraphIntoGraph(out, *FragmentList, (*FragmentLowerOrdersList[RootNr][i]), &counter);
        delete(FragmentLowerOrdersList[RootNr][i]);
      }
    }
    Free((void **)&FragmentLowerOrdersList[RootNr], "molecule::FragmentBOSSANOVA: **FragmentLowerOrdersList[]");
    RootNr++;
  }
  Free((void **)&FragmentLowerOrdersList, "molecule::FragmentBOSSANOVA: ***FragmentLowerOrdersList");
  Free((void **)&NumMoleculesOfOrder, "molecule::FragmentBOSSANOVA: *NumMoleculesOfOrder");

  *out << Verbose(0) << "End of FragmentBOSSANOVA." << endl;
};

/** Comparison function for GSL heapsort on distances in two molecules.
 * \param *a
 * \param *b
 * \return <0, \a *a less than \a *b, ==0 if equal, >0 \a *a greater than \a *b
 */
inline int CompareDoubles (const void * a, const void * b)
{
  if (*(double *)a > *(double *)b)
    return -1;
  else if (*(double *)a < *(double *)b)
    return 1;
  else
    return 0;
};

/** Determines whether two molecules actually contain the same atoms and coordination.
 * \param *out output stream for debugging
 * \param *OtherMolecule the molecule to compare this one to
 * \param threshold upper limit of difference when comparing the coordination.
 * \return NULL - not equal, otherwise an allocated (molecule::AtomCount) permutation map of the atom numbers (which corresponds to which)
 */
int * molecule::IsEqualToWithinThreshold(ofstream *out, molecule *OtherMolecule, double threshold)
{
  int flag;
  double *Distances = NULL, *OtherDistances = NULL;
  Vector CenterOfGravity, OtherCenterOfGravity;
  size_t *PermMap = NULL, *OtherPermMap = NULL;
  int *PermutationMap = NULL;
  atom *Walker = NULL;
  bool result = true; // status of comparison

  *out << Verbose(3) << "Begin of IsEqualToWithinThreshold." << endl;
  /// first count both their atoms and elements and update lists thereby ...
  //*out << Verbose(0) << "Counting atoms, updating list" << endl;
  CountAtoms(out);
  OtherMolecule->CountAtoms(out);
  CountElements();
  OtherMolecule->CountElements();

  /// ... and compare:
  /// -# AtomCount
  if (result) {
    if (AtomCount != OtherMolecule->AtomCount) {
      *out << Verbose(4) << "AtomCounts don't match: " << AtomCount << " == " << OtherMolecule->AtomCount << endl;
      result = false;
    } else *out << Verbose(4) << "AtomCounts match: " << AtomCount << " == " << OtherMolecule->AtomCount << endl;
  }
  /// -# ElementCount
  if (result) {
    if (ElementCount != OtherMolecule->ElementCount) {
      *out << Verbose(4) << "ElementCount don't match: " << ElementCount << " == " << OtherMolecule->ElementCount << endl;
      result = false;
    } else *out << Verbose(4) << "ElementCount match: " << ElementCount << " == " << OtherMolecule->ElementCount << endl;
  }
  /// -# ElementsInMolecule
  if (result) {
    for (flag=MAX_ELEMENTS;flag--;) {
      //*out << Verbose(5) << "Element " <<  flag << ": " << ElementsInMolecule[flag] << " <-> " << OtherMolecule->ElementsInMolecule[flag] << "." << endl;
      if (ElementsInMolecule[flag] != OtherMolecule->ElementsInMolecule[flag])
        break;
    }
    if (flag < MAX_ELEMENTS) {
      *out << Verbose(4) << "ElementsInMolecule don't match." << endl;
      result = false;
    } else *out << Verbose(4) << "ElementsInMolecule match." << endl;
  }
  /// then determine and compare center of gravity for each molecule ...
  if (result) {
    *out << Verbose(5) << "Calculating Centers of Gravity" << endl;
    DeterminePeriodicCenter(CenterOfGravity);
    OtherMolecule->DeterminePeriodicCenter(OtherCenterOfGravity);
    *out << Verbose(5) << "Center of Gravity: ";
    CenterOfGravity.Output(out);
    *out << endl << Verbose(5) << "Other Center of Gravity: ";
    OtherCenterOfGravity.Output(out);
    *out << endl;
    if (CenterOfGravity.DistanceSquared(&OtherCenterOfGravity) > threshold*threshold) {
      *out << Verbose(4) << "Centers of gravity don't match." << endl;
      result = false;
    }
  }

  /// ... then make a list with the euclidian distance to this center for each atom of both molecules
  if (result) {
    *out << Verbose(5) << "Calculating distances" << endl;
    Distances = (double *) Malloc(sizeof(double)*AtomCount, "molecule::IsEqualToWithinThreshold: Distances");
    OtherDistances = (double *) Malloc(sizeof(double)*AtomCount, "molecule::IsEqualToWithinThreshold: OtherDistances");
    Walker = start;
    while (Walker->next != end) {
      Walker = Walker->next;
      Distances[Walker->nr] = CenterOfGravity.DistanceSquared(&Walker->x);
    }
    Walker = OtherMolecule->start;
    while (Walker->next != OtherMolecule->end) {
      Walker = Walker->next;
      OtherDistances[Walker->nr] = OtherCenterOfGravity.DistanceSquared(&Walker->x);
    }

    /// ... sort each list (using heapsort (o(N log N)) from GSL)
    *out << Verbose(5) << "Sorting distances" << endl;
    PermMap = (size_t *) Malloc(sizeof(size_t)*AtomCount, "molecule::IsEqualToWithinThreshold: *PermMap");
    OtherPermMap = (size_t *) Malloc(sizeof(size_t)*AtomCount, "molecule::IsEqualToWithinThreshold: *OtherPermMap");
    gsl_heapsort_index (PermMap, Distances, AtomCount, sizeof(double), CompareDoubles);
    gsl_heapsort_index (OtherPermMap, OtherDistances, AtomCount, sizeof(double), CompareDoubles);
    PermutationMap = (int *) Malloc(sizeof(int)*AtomCount, "molecule::IsEqualToWithinThreshold: *PermutationMap");
    *out << Verbose(5) << "Combining Permutation Maps" << endl;
    for(int i=AtomCount;i--;)
      PermutationMap[PermMap[i]] = (int) OtherPermMap[i];

    /// ... and compare them step by step, whether the difference is individiually(!) below \a threshold for all
    *out << Verbose(4) << "Comparing distances" << endl;
    flag = 0;
    for (int i=0;i<AtomCount;i++) {
      *out << Verbose(5) << "Distances squared: |" << Distances[PermMap[i]] << " - " << OtherDistances[OtherPermMap[i]] << "| = " << fabs(Distances[PermMap[i]] - OtherDistances[OtherPermMap[i]]) << " ?<? " <<  threshold << endl;
      if (fabs(Distances[PermMap[i]] - OtherDistances[OtherPermMap[i]]) > threshold*threshold)
        flag = 1;
    }
    Free((void **)&PermMap, "molecule::IsEqualToWithinThreshold: *PermMap");
    Free((void **)&OtherPermMap, "molecule::IsEqualToWithinThreshold: *OtherPermMap");

    /// free memory
    Free((void **)&Distances, "molecule::IsEqualToWithinThreshold: Distances");
    Free((void **)&OtherDistances, "molecule::IsEqualToWithinThreshold: OtherDistances");
    if (flag) { // if not equal
      Free((void **)&PermutationMap, "molecule::IsEqualToWithinThreshold: *PermutationMap");
      result = false;
    }
  }
  /// return pointer to map if all distances were below \a threshold
  *out << Verbose(3) << "End of IsEqualToWithinThreshold." << endl;
  if (result) {
    *out << Verbose(3) << "Result: Equal." << endl;
    return PermutationMap;
  } else {
    *out << Verbose(3) << "Result: Not equal." << endl;
    return NULL;
  }
};

/** Returns an index map for two father-son-molecules.
 * The map tells which atom in this molecule corresponds to which one in the other molecul with their fathers.
 * \param *out output stream for debugging
 * \param *OtherMolecule corresponding molecule with fathers
 * \return allocated map of size molecule::AtomCount with map
 * \todo make this with a good sort O(n), not O(n^2)
 */
int * molecule::GetFatherSonAtomicMap(ofstream *out, molecule *OtherMolecule)
{
  atom *Walker = NULL, *OtherWalker = NULL;
  *out << Verbose(3) << "Begin of GetFatherAtomicMap." << endl;
  int *AtomicMap = (int *) Malloc(sizeof(int)*AtomCount, "molecule::GetAtomicMap: *AtomicMap");  //Calloc
  for (int i=AtomCount;i--;)
    AtomicMap[i] = -1;
  if (OtherMolecule == this) {  // same molecule
    for (int i=AtomCount;i--;) // no need as -1 means already that there is trivial correspondence
      AtomicMap[i] = i;
    *out << Verbose(4) << "Map is trivial." << endl;
  } else {
    *out << Verbose(4) << "Map is ";
    Walker = start;
    while (Walker->next != end) {
      Walker = Walker->next;
      if (Walker->father == NULL) {
        AtomicMap[Walker->nr] = -2;
      } else {
        OtherWalker = OtherMolecule->start;
        while (OtherWalker->next != OtherMolecule->end) {
          OtherWalker = OtherWalker->next;
      //for (int i=0;i<AtomCount;i++) { // search atom
        //for (int j=0;j<OtherMolecule->AtomCount;j++) {
          //*out << Verbose(4) << "Comparing father " << Walker->father << " with the other one " << OtherWalker->father << "." << endl;
          if (Walker->father == OtherWalker)
            AtomicMap[Walker->nr] = OtherWalker->nr;
        }
      }
      *out << AtomicMap[Walker->nr] << "\t";
    }
    *out << endl;
  }
  *out << Verbose(3) << "End of GetFatherAtomicMap." << endl;
  return AtomicMap;
};

/** Stores the temperature evaluated from velocities in molecule::Trajectories.
 * We simply use the formula equivaleting temperature and kinetic energy:
 * \f$k_B T = \sum_i m_i v_i^2\f$
 * \param *out output stream for debugging
 * \param startstep first MD step in molecule::Trajectories
 * \param endstep last plus one MD step in molecule::Trajectories
 * \param *output output stream of temperature file
 * \return file written (true), failure on writing file (false)
 */
bool molecule::OutputTemperatureFromTrajectories(ofstream *out, int startstep, int endstep, ofstream *output)
{
  double temperature;
  atom *Walker = NULL;
  // test stream
  if (output == NULL)
    return false;
  else
    *output << "# Step Temperature [K] Temperature [a.u.]" << endl;
  for (int step=startstep;step < endstep; step++) { // loop over all time steps
    temperature = 0.;
    Walker = start;
    while (Walker->next != end) {
      Walker = Walker->next;
      for (int i=NDIM;i--;)
        temperature += Walker->type->mass * Trajectories[Walker].U.at(step).x[i]* Trajectories[Walker].U.at(step).x[i];
    }
    *output << step << "\t" << temperature*AtomicEnergyToKelvin << "\t" << temperature << endl;
  }
  return true;
};