Index: src/molecule_graph.cpp
===================================================================
--- src/molecule_graph.cpp	(revision 12920404e7a45c1ac4fe563b7c5a29891f5e662a)
+++ src/molecule_graph.cpp	(revision e73ad9a5d1596d6e9a9f9c6a17bf256479595404)
@@ -44,18 +44,4 @@
 #define MAXBONDS 8
 
-struct BFSAccounting
-{
-  atom **PredecessorList;
-  int *ShortestPathList;
-  enum GraphEdge::Shading *ColorList;
-  std::deque<atom *> *BFSStack;
-  std::deque<atom *> *TouchedStack;
-  int AtomCount;
-  int BondOrder;
-  atom *Root;
-  bool BackStepping;
-  int CurrentGraphNr;
-  int ComponentNr;
-};
 
 /** Accounting data for Depth First Search.
@@ -200,5 +186,5 @@
 
 
-/** Sets atom::GraphNr and atom::LowpointNr to BFSAccounting::CurrentGraphNr.
+/** Sets atom::GraphNr and atom::LowpointNr to DFSAccounting::CurrentGraphNr.
  * \param *Walker current node
  * \param &BFS structure with accounting data for BFS
@@ -518,328 +504,4 @@
 }
 ;
-
-/** Initialise each vertex as white with no predecessor, empty queue, color Root lightgray.
- * \param &BFS accounting structure
- * \param AtomCount number of entries in the array to allocate
- */
-void InitializeBFSAccounting(struct BFSAccounting &BFS, int AtomCount)
-{
-  BFS.AtomCount = AtomCount;
-  BFS.PredecessorList = new atom*[AtomCount];
-  BFS.ShortestPathList = new int[AtomCount];
-  BFS.ColorList = new enum GraphEdge::Shading[AtomCount];
-  BFS.BFSStack = new std::deque<atom *> (AtomCount);
-  BFS.TouchedStack = new std::deque<atom *> (AtomCount);
-
-  for (int i = AtomCount; i--;) {
-    BFS.ShortestPathList[i] = -1;
-    BFS.PredecessorList[i] = 0;
-    BFS.ColorList[i] = GraphEdge::white;
-  }
-};
-
-/** Free's accounting structure.
- * \param &BFS accounting structure
- */
-void FinalizeBFSAccounting(struct BFSAccounting &BFS)
-{
-  delete[](BFS.PredecessorList);
-  delete[](BFS.ShortestPathList);
-  delete[](BFS.ColorList);
-  delete (BFS.BFSStack);
-  delete (BFS.TouchedStack);
-  BFS.AtomCount = 0;
-};
-
-/** Clean the accounting structure.
- * \param &BFS accounting structure
- */
-void CleanBFSAccounting(struct BFSAccounting &BFS)
-{
-  atom *Walker = NULL;
-  while (!BFS.TouchedStack->empty()) {
-    Walker = BFS.TouchedStack->front();
-    BFS.TouchedStack->pop_front();
-    BFS.PredecessorList[Walker->getNr()] = NULL;
-    BFS.ShortestPathList[Walker->getNr()] = -1;
-    BFS.ColorList[Walker->getNr()] = GraphEdge::white;
-  }
-};
-
-/** Resets shortest path list and BFSStack.
- * \param *&Walker current node, pushed onto BFSAccounting::BFSStack and BFSAccounting::TouchedStack
- * \param &BFS accounting structure
- */
-void ResetBFSAccounting(atom *&Walker, struct BFSAccounting &BFS)
-{
-  BFS.ShortestPathList[Walker->getNr()] = 0;
-  BFS.BFSStack->clear(); // start with empty BFS stack
-  BFS.BFSStack->push_front(Walker);
-  BFS.TouchedStack->push_front(Walker);
-};
-
-/** Performs a BFS from \a *Root, trying to find the same node and hence a cycle.
- * \param *&BackEdge the edge from root that we don't want to move along
- * \param &BFS accounting structure
- */
-void CyclicStructureAnalysis_CyclicBFSFromRootToRoot(bond *&BackEdge, struct BFSAccounting &BFS)
-{
-  atom *Walker = NULL;
-  atom *OtherAtom = NULL;
-  do { // look for Root
-    ASSERT(!BFS.BFSStack->empty(), "CyclicStructureAnalysis_CyclicBFSFromRootToRoot() - BFS.BFSStack is empty!");
-    Walker = BFS.BFSStack->front();
-    BFS.BFSStack->pop_front();
-    DoLog(2) && (Log() << Verbose(2) << "Current Walker is " << *Walker << ", we look for SP to Root " << *BFS.Root << "." << endl);
-    const BondList& ListOfBonds = Walker->getListOfBonds();
-    for (BondList::const_iterator Runner = ListOfBonds.begin();
-        Runner != ListOfBonds.end();
-        ++Runner) {
-      if ((*Runner) != BackEdge) { // only walk along DFS spanning tree (otherwise we always find SP of one being backedge Binder)
-        OtherAtom = (*Runner)->GetOtherAtom(Walker);
-#ifdef ADDHYDROGEN
-        if (OtherAtom->getType()->getAtomicNumber() != 1) {
-#endif
-        DoLog(2) && (Log() << Verbose(2) << "Current OtherAtom is: " << OtherAtom->getName() << " for bond " << *(*Runner) << "." << endl);
-        if (BFS.ColorList[OtherAtom->getNr()] == GraphEdge::white) {
-          BFS.TouchedStack->push_front(OtherAtom);
-          BFS.ColorList[OtherAtom->getNr()] = GraphEdge::lightgray;
-          BFS.PredecessorList[OtherAtom->getNr()] = Walker; // Walker is the predecessor
-          BFS.ShortestPathList[OtherAtom->getNr()] = BFS.ShortestPathList[Walker->getNr()] + 1;
-          DoLog(2) && (Log() << Verbose(2) << "Coloring OtherAtom " << OtherAtom->getName() << " lightgray, its predecessor is " << Walker->getName() << " and its Shortest Path is " << BFS.ShortestPathList[OtherAtom->getNr()] << " egde(s) long." << endl);
-          //if (BFS.ShortestPathList[OtherAtom->getNr()] < MinimumRingSize[Walker->GetTrueFather()->nr]) { // Check for maximum distance
-          DoLog(3) && (Log() << Verbose(3) << "Putting OtherAtom into queue." << endl);
-          BFS.BFSStack->push_front(OtherAtom);
-          //}
-        } else {
-          DoLog(3) && (Log() << Verbose(3) << "Not Adding, has already been visited." << endl);
-        }
-        if (OtherAtom == BFS.Root)
-          break;
-#ifdef ADDHYDROGEN
-      } else {
-        DoLog(2) && (Log() << Verbose(2) << "Skipping hydrogen atom " << *OtherAtom << "." << endl);
-        BFS.ColorList[OtherAtom->getNr()] = GraphEdge::black;
-      }
-#endif
-      } else {
-        DoLog(2) && (Log() << Verbose(2) << "Bond " << *(*Runner) << " not Visiting, is the back edge." << endl);
-      }
-    }
-    BFS.ColorList[Walker->getNr()] = GraphEdge::black;
-    DoLog(1) && (Log() << Verbose(1) << "Coloring Walker " << Walker->getName() << " black." << endl);
-    if (OtherAtom == BFS.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 = BFS.PredecessorList[OtherAtom->getNr()];
-      }
-      if (OtherAtom == BackEdge->rightatom) { // if each atom in found cycle is cyclic, loop's been found before already
-        DoLog(3) && (Log() << Verbose(3) << "This cycle was already found before, skipping and removing seeker from search." << endl);
-        do {
-          ASSERT(!BFS.TouchedStack->empty(), "CyclicStructureAnalysis_CyclicBFSFromRootToRoot() - BFS.TouchedStack is empty!");
-          OtherAtom = BFS.TouchedStack->front();
-          BFS.TouchedStack->pop_front();
-          if (BFS.PredecessorList[OtherAtom->getNr()] == Walker) {
-            DoLog(4) && (Log() << Verbose(4) << "Removing " << *OtherAtom << " from lists and stacks." << endl);
-            BFS.PredecessorList[OtherAtom->getNr()] = NULL;
-            BFS.ShortestPathList[OtherAtom->getNr()] = -1;
-            BFS.ColorList[OtherAtom->getNr()] = GraphEdge::white;
-            // rats ... deque has no find()
-            std::deque<atom *>::iterator iter = find(
-                BFS.BFSStack->begin(),
-                BFS.BFSStack->end(),
-                OtherAtom);
-            ASSERT(iter != BFS.BFSStack->end(),
-                "CyclicStructureAnalysis_CyclicBFSFromRootToRoot() - can't find "+toString(*OtherAtom)+" on stack!");
-            BFS.BFSStack->erase(iter);
-          }
-        } while ((!BFS.TouchedStack->empty()) && (BFS.PredecessorList[OtherAtom->getNr()] == NULL));
-        BFS.TouchedStack->push_front(OtherAtom); // last was wrongly popped
-        OtherAtom = BackEdge->rightatom; // set to not Root
-      } else
-        OtherAtom = BFS.Root;
-    }
-  } while ((!BFS.BFSStack->empty()) && (OtherAtom != BFS.Root) && (OtherAtom != NULL)); // || (ShortestPathList[OtherAtom->getNr()] < MinimumRingSize[Walker->GetTrueFather()->getNr()])));
-};
-
-/** Climb back the BFSAccounting::PredecessorList and find cycle members.
- * \param *&OtherAtom
- * \param *&BackEdge denotes the edge we did not want to travel along when doing CyclicBFSFromRootToRoot()
- * \param &BFS accounting structure
- * \param *&MinimumRingSize minimum distance from this node possible without encountering oneself, set on return for each atom
- * \param &MinRingSize global minimum distance from one node without encountering oneself, set on return
- */
-void CyclicStructureAnalysis_RetrieveCycleMembers(atom *&OtherAtom, bond *&BackEdge, struct BFSAccounting &BFS, int *&MinimumRingSize, int &MinRingSize)
-{
-  atom *Walker = NULL;
-  int NumCycles = 0;
-  int RingSize = -1;
-
-  if (OtherAtom == BFS.Root) {
-    // now climb back the predecessor list and thus find the cycle members
-    NumCycles++;
-    RingSize = 1;
-    BFS.Root->GetTrueFather()->IsCyclic = true;
-    DoLog(1) && (Log() << Verbose(1) << "Found ring contains: ");
-    Walker = BFS.Root;
-    while (Walker != BackEdge->rightatom) {
-      DoLog(0) && (Log() << Verbose(0) << Walker->getName() << " <-> ");
-      Walker = BFS.PredecessorList[Walker->getNr()];
-      Walker->GetTrueFather()->IsCyclic = true;
-      RingSize++;
-    }
-    DoLog(0) && (Log() << Verbose(0) << Walker->getName() << "  with a length of " << RingSize << "." << endl << endl);
-    // walk through all and set MinimumRingSize
-    Walker = BFS.Root;
-    MinimumRingSize[Walker->GetTrueFather()->getNr()] = RingSize;
-    while (Walker != BackEdge->rightatom) {
-      Walker = BFS.PredecessorList[Walker->getNr()];
-      if (RingSize < MinimumRingSize[Walker->GetTrueFather()->getNr()])
-        MinimumRingSize[Walker->GetTrueFather()->getNr()] = RingSize;
-    }
-    if ((RingSize < MinRingSize) || (MinRingSize == -1))
-      MinRingSize = RingSize;
-  } else {
-    DoLog(1) && (Log() << Verbose(1) << "No ring containing " << *BFS.Root << " with length equal to or smaller than " << MinimumRingSize[BFS.Root->GetTrueFather()->getNr()] << " found." << endl);
-  }
-};
-
-/** From a given node performs a BFS to touch the next cycle, for whose nodes \a *&MinimumRingSize is set and set it accordingly.
- * \param *&Root node to look for closest cycle from, i.e. \a *&MinimumRingSize is set for this node
- * \param *&MinimumRingSize minimum distance from this node possible without encountering oneself, set on return for each atom
- * \param AtomCount number of nodes in graph
- */
-void CyclicStructureAnalysis_BFSToNextCycle(atom *&Root, atom *&Walker, int *&MinimumRingSize, int AtomCount)
-{
-  struct BFSAccounting BFS;
-  atom *OtherAtom = Walker;
-
-  InitializeBFSAccounting(BFS, AtomCount);
-
-  ResetBFSAccounting(Walker, BFS);
-  while (OtherAtom != NULL) { // look for Root
-    ASSERT(!BFS.BFSStack->empty(), "CyclicStructureAnalysis_BFSToNextCycle() - BFS.BFSStack is empty!");
-    Walker = BFS.BFSStack->front();
-    BFS.BFSStack->pop_front();
-    //Log() << Verbose(2) << "Current Walker is " << *Walker << ", we look for SP to Root " << *Root << "." << endl;
-    const BondList& ListOfBonds = Walker->getListOfBonds();
-    for (BondList::const_iterator Runner = ListOfBonds.begin();
-        Runner != ListOfBonds.end();
-        ++Runner) {
-      // "removed (*Runner) != BackEdge) || " from next if, is u
-      if ((ListOfBonds.size() == 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 = (*Runner)->GetOtherAtom(Walker);
-        //Log() << Verbose(2) << "Current OtherAtom is: " << OtherAtom->Name << " for bond " << *Binder << "." << endl;
-        if (BFS.ColorList[OtherAtom->getNr()] == GraphEdge::white) {
-          BFS.TouchedStack->push_front(OtherAtom);
-          BFS.ColorList[OtherAtom->getNr()] = GraphEdge::lightgray;
-          BFS.PredecessorList[OtherAtom->getNr()] = Walker; // Walker is the predecessor
-          BFS.ShortestPathList[OtherAtom->getNr()] = BFS.ShortestPathList[Walker->getNr()] + 1;
-          //Log() << Verbose(2) << "Coloring OtherAtom " << OtherAtom->Name << " lightgray, its predecessor is " << Walker->Name << " and its Shortest Path is " << ShortestPathList[OtherAtom->getNr()] << " egde(s) long." << endl;
-          if (OtherAtom->GetTrueFather()->IsCyclic) { // if the other atom is connected to a ring
-            MinimumRingSize[Root->GetTrueFather()->getNr()] = BFS.ShortestPathList[OtherAtom->getNr()] + MinimumRingSize[OtherAtom->GetTrueFather()->getNr()];
-            OtherAtom = NULL; //break;
-            break;
-          } else
-            BFS.BFSStack->push_front(OtherAtom);
-        } else {
-          //Log() << Verbose(3) << "Not Adding, has already been visited." << endl;
-        }
-      } else {
-        //Log() << Verbose(3) << "Not Visiting, is a back edge." << endl;
-      }
-    }
-    BFS.ColorList[Walker->getNr()] = GraphEdge::black;
-    //Log() << Verbose(1) << "Coloring Walker " << Walker->Name << " black." << endl;
-  }
-  //CleanAccountingLists(TouchedStack, PredecessorList, ShortestPathList, ColorList);
-
-  FinalizeBFSAccounting(BFS);
-}
-;
-
-/** All nodes that are not in cycles get assigned a \a *&MinimumRingSizeby BFS to next cycle.
- * \param *&MinimumRingSize array with minimum distance without encountering onself for each atom
- * \param &MinRingSize global minium distance
- * \param &NumCyles number of cycles in graph
- * \param *mol molecule with atoms
- */
-void CyclicStructureAnalysis_AssignRingSizetoNonCycleMembers(int *&MinimumRingSize, int &MinRingSize, int &NumCycles, const molecule * const mol)
-{
-  atom *Root = NULL;
-  atom *Walker = NULL;
-  if (MinRingSize != -1) { // if rings are present
-    // go over all atoms
-    for (molecule::const_iterator iter = mol->begin(); iter != mol->end(); ++iter) {
-      Root = *iter;
-
-      if (MinimumRingSize[Root->GetTrueFather()->getNr()] == mol->getAtomCount()) { // check whether MinimumRingSize is set, if not BFS to next where it is
-        Walker = Root;
-
-        //Log() << Verbose(1) << "---------------------------------------------------------------------------------------------------------" << endl;
-        CyclicStructureAnalysis_BFSToNextCycle(Root, Walker, MinimumRingSize, mol->getAtomCount());
-
-      }
-      DoLog(1) && (Log() << Verbose(1) << "Minimum ring size of " << *Root << " is " << MinimumRingSize[Root->GetTrueFather()->getNr()] << "." << endl);
-    }
-    DoLog(1) && (Log() << Verbose(1) << "Minimum ring size is " << MinRingSize << ", over " << NumCycles << " cycles total." << endl);
-  } else
-    DoLog(1) && (Log() << Verbose(1) << "No rings were detected in the molecular structure." << endl);
-}
-;
-
-/** 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 *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(
-    std::deque<bond *> * BackEdgeStack,
-    int *&MinimumRingSize
-    ) const
-{
-  struct BFSAccounting BFS;
-  atom *Walker = NULL;
-  atom *OtherAtom = NULL;
-  bond *BackEdge = NULL;
-  int NumCycles = 0;
-  int MinRingSize = -1;
-
-  InitializeBFSAccounting(BFS, getAtomCount());
-
-  //Log() << Verbose(1) << "Back edge list - ";
-  //BackEdgeStack->Output(out);
-
-  DoLog(1) && (Log() << Verbose(1) << "Analysing cycles ... " << endl);
-  NumCycles = 0;
-  while (!BackEdgeStack->empty()) {
-    BackEdge = BackEdgeStack->front();
-    BackEdgeStack->pop_front();
-    // this is the target
-    BFS.Root = BackEdge->leftatom;
-    // this is the source point
-    Walker = BackEdge->rightatom;
-
-    ResetBFSAccounting(Walker, BFS);
-
-    DoLog(1) && (Log() << Verbose(1) << "---------------------------------------------------------------------------------------------------------" << endl);
-    OtherAtom = NULL;
-    CyclicStructureAnalysis_CyclicBFSFromRootToRoot(BackEdge, BFS);
-
-    CyclicStructureAnalysis_RetrieveCycleMembers(OtherAtom, BackEdge, BFS, MinimumRingSize, MinRingSize);
-
-    CleanBFSAccounting(BFS);
-  }
-  FinalizeBFSAccounting(BFS);
-
-  CyclicStructureAnalysis_AssignRingSizetoNonCycleMembers(MinimumRingSize, MinRingSize, NumCycles, this);
-};
 
 /** Sets the next component number.
