Changeset ef9aae


Ignore:
Timestamp:
Oct 18, 2009, 4:01:57 PM (15 years ago)
Author:
Frederik Heber <heber@…>
Branches:
Action_Thermostats, Add_AtomRandomPerturbation, Add_FitFragmentPartialChargesAction, Add_RotateAroundBondAction, Add_SelectAtomByNameAction, Added_ParseSaveFragmentResults, AddingActions_SaveParseParticleParameters, Adding_Graph_to_ChangeBondActions, Adding_MD_integration_tests, Adding_ParticleName_to_Atom, Adding_StructOpt_integration_tests, AtomFragments, Automaking_mpqc_open, AutomationFragmentation_failures, Candidate_v1.5.4, Candidate_v1.6.0, Candidate_v1.6.1, ChangeBugEmailaddress, ChangingTestPorts, ChemicalSpaceEvaluator, CombiningParticlePotentialParsing, Combining_Subpackages, Debian_Package_split, Debian_package_split_molecuildergui_only, Disabling_MemDebug, Docu_Python_wait, EmpiricalPotential_contain_HomologyGraph, EmpiricalPotential_contain_HomologyGraph_documentation, Enable_parallel_make_install, Enhance_userguide, Enhanced_StructuralOptimization, Enhanced_StructuralOptimization_continued, Example_ManyWaysToTranslateAtom, Exclude_Hydrogens_annealWithBondGraph, FitPartialCharges_GlobalError, Fix_BoundInBox_CenterInBox_MoleculeActions, Fix_ChargeSampling_PBC, Fix_ChronosMutex, Fix_FitPartialCharges, Fix_FitPotential_needs_atomicnumbers, Fix_ForceAnnealing, Fix_IndependentFragmentGrids, Fix_ParseParticles, Fix_ParseParticles_split_forward_backward_Actions, Fix_PopActions, Fix_QtFragmentList_sorted_selection, Fix_Restrictedkeyset_FragmentMolecule, Fix_StatusMsg, Fix_StepWorldTime_single_argument, Fix_Verbose_Codepatterns, Fix_fitting_potentials, Fixes, ForceAnnealing_goodresults, ForceAnnealing_oldresults, ForceAnnealing_tocheck, ForceAnnealing_with_BondGraph, ForceAnnealing_with_BondGraph_continued, ForceAnnealing_with_BondGraph_continued_betteresults, ForceAnnealing_with_BondGraph_contraction-expansion, FragmentAction_writes_AtomFragments, FragmentMolecule_checks_bonddegrees, GeometryObjects, Gui_Fixes, Gui_displays_atomic_force_velocity, ImplicitCharges, IndependentFragmentGrids, IndependentFragmentGrids_IndividualZeroInstances, IndependentFragmentGrids_IntegrationTest, IndependentFragmentGrids_Sole_NN_Calculation, JobMarket_RobustOnKillsSegFaults, JobMarket_StableWorkerPool, JobMarket_unresolvable_hostname_fix, MoreRobust_FragmentAutomation, ODR_violation_mpqc_open, PartialCharges_OrthogonalSummation, PdbParser_setsAtomName, PythonUI_with_named_parameters, QtGui_reactivate_TimeChanged_changes, Recreated_GuiChecks, Rewrite_FitPartialCharges, RotateToPrincipalAxisSystem_UndoRedo, SaturateAtoms_findBestMatching, SaturateAtoms_singleDegree, StoppableMakroAction, Subpackage_CodePatterns, Subpackage_JobMarket, Subpackage_LinearAlgebra, Subpackage_levmar, Subpackage_mpqc_open, Subpackage_vmg, Switchable_LogView, ThirdParty_MPQC_rebuilt_buildsystem, TrajectoryDependenant_MaxOrder, TremoloParser_IncreasedPrecision, TremoloParser_MultipleTimesteps, TremoloParser_setsAtomName, Ubuntu_1604_changes, stable
Children:
2cc75c3
Parents:
174e0e
git-author:
Frederik Heber <heber@…> (10/18/09 15:59:52)
git-committer:
Frederik Heber <heber@…> (10/18/09 16:01:57)
Message:

Refactored molecule::CyclicStructureAnalysis()

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/molecule_graph.cpp

    r174e0e ref9aae  
    494494};
    495495
     496/**  initialise each vertex as white with no predecessor, empty queue, color Root lightgray.
     497 *
     498 */
     499void InitializeAccounting(atom **&PredecessorList, int *&ShortestPathList, enum Shading *&ColorList, int AtomCount)
     500{
     501  for (int i=AtomCount;i--;) {
     502    PredecessorList[i] = NULL;
     503    ShortestPathList[i] = -1;
     504    ColorList[i] = white;
     505  }
     506};
     507
     508void ResetAccounting(atom *&Walker, class StackClass<atom *> *&TouchedStack, int *&ShortestPathList, class StackClass<atom *> *&BFSStack)
     509{
     510  ShortestPathList[Walker->nr] = 0;
     511  BFSStack->ClearStack();  // start with empty BFS stack
     512  BFSStack->Push(Walker);
     513  TouchedStack->Push(Walker);
     514};
     515
     516void CyclicBFSFromRootToRoot(ofstream *out, atom *&Root, bond *&BackEdge, class StackClass<atom *> *&TouchedStack, int *&ShortestPathList, atom **&PredecessorList, class StackClass<atom *> *&BFSStack, enum Shading *&ColorList)
     517{
     518  atom *Walker = NULL;
     519  atom *OtherAtom = NULL;
     520  do {  // look for Root
     521    Walker = BFSStack->PopFirst();
     522    *out << Verbose(2) << "Current Walker is " << *Walker << ", we look for SP to Root " << *Root << "." << endl;
     523    for (BondList::const_iterator Runner = Walker->ListOfBonds.begin(); Runner != Walker->ListOfBonds.end(); (++Runner)) {
     524      if ((*Runner) != BackEdge) { // only walk along DFS spanning tree (otherwise we always find SP of one being backedge Binder)
     525        OtherAtom = (*Runner)->GetOtherAtom(Walker);
     526  #ifdef ADDHYDROGEN
     527        if (OtherAtom->type->Z != 1) {
     528  #endif
     529          *out << Verbose(2) << "Current OtherAtom is: " << OtherAtom->Name << " for bond " << *(*Runner) << "." << endl;
     530          if (ColorList[OtherAtom->nr] == white) {
     531            TouchedStack->Push(OtherAtom);
     532            ColorList[OtherAtom->nr] = lightgray;
     533            PredecessorList[OtherAtom->nr] = Walker;  // Walker is the predecessor
     534            ShortestPathList[OtherAtom->nr] = ShortestPathList[Walker->nr]+1;
     535            *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;
     536            //if (ShortestPathList[OtherAtom->nr] < MinimumRingSize[Walker->GetTrueFather()->nr]) { // Check for maximum distance
     537              *out << Verbose(3) << "Putting OtherAtom into queue." << endl;
     538              BFSStack->Push(OtherAtom);
     539            //}
     540          } else {
     541            *out << Verbose(3) << "Not Adding, has already been visited." << endl;
     542          }
     543          if (OtherAtom == Root)
     544            break;
     545  #ifdef ADDHYDROGEN
     546        } else {
     547          *out << Verbose(2) << "Skipping hydrogen atom " << *OtherAtom << "." << endl;
     548          ColorList[OtherAtom->nr] = black;
     549        }
     550  #endif
     551      } else {
     552        *out << Verbose(2) << "Bond " << *(*Runner) << " not Visiting, is the back edge." << endl;
     553      }
     554    }
     555    ColorList[Walker->nr] = black;
     556    *out << Verbose(1) << "Coloring Walker " << Walker->Name << " black." << endl;
     557    if (OtherAtom == Root) { // if we have found the root, check whether this cycle wasn't already found beforehand
     558      // step through predecessor list
     559      while (OtherAtom != BackEdge->rightatom) {
     560        if (!OtherAtom->GetTrueFather()->IsCyclic)  // if one bond in the loop is not marked as cyclic, we haven't found this cycle yet
     561          break;
     562        else
     563          OtherAtom = PredecessorList[OtherAtom->nr];
     564      }
     565      if (OtherAtom == BackEdge->rightatom) { // if each atom in found cycle is cyclic, loop's been found before already
     566        *out << Verbose(3) << "This cycle was already found before, skipping and removing seeker from search." << endl;\
     567        do {
     568          OtherAtom = TouchedStack->PopLast();
     569          if (PredecessorList[OtherAtom->nr] == Walker) {
     570            *out << Verbose(4) << "Removing " << *OtherAtom << " from lists and stacks." << endl;
     571            PredecessorList[OtherAtom->nr] = NULL;
     572            ShortestPathList[OtherAtom->nr] = -1;
     573            ColorList[OtherAtom->nr] = white;
     574            BFSStack->RemoveItem(OtherAtom);
     575          }
     576        } while ((!TouchedStack->IsEmpty()) && (PredecessorList[OtherAtom->nr] == NULL));
     577        TouchedStack->Push(OtherAtom);  // last was wrongly popped
     578        OtherAtom = BackEdge->rightatom; // set to not Root
     579      } else
     580        OtherAtom = Root;
     581    }
     582  } while ((!BFSStack->IsEmpty()) && (OtherAtom != Root) && (OtherAtom != NULL)); // || (ShortestPathList[OtherAtom->nr] < MinimumRingSize[Walker->GetTrueFather()->nr])));
     583};
     584
     585void RetrieveCycleMembers(ofstream *out, atom *&Root, atom *&OtherAtom, bond *&BackEdge, atom **&PredecessorList, int *&MinimumRingSize, int &MinRingSize)
     586{
     587  atom *Walker = NULL;
     588  int NumCycles = 0;
     589  int RingSize = -1;
     590
     591  if (OtherAtom == Root) {
     592    // now climb back the predecessor list and thus find the cycle members
     593    NumCycles++;
     594    RingSize = 1;
     595    Root->GetTrueFather()->IsCyclic = true;
     596    *out << Verbose(1) << "Found ring contains: ";
     597    Walker = Root;
     598    while (Walker != BackEdge->rightatom) {
     599      *out << Walker->Name << " <-> ";
     600      Walker = PredecessorList[Walker->nr];
     601      Walker->GetTrueFather()->IsCyclic = true;
     602      RingSize++;
     603    }
     604    *out << Walker->Name << "  with a length of " << RingSize << "." << endl << endl;
     605    // walk through all and set MinimumRingSize
     606    Walker = Root;
     607    MinimumRingSize[Walker->GetTrueFather()->nr] = RingSize;
     608    while (Walker != BackEdge->rightatom) {
     609      Walker = PredecessorList[Walker->nr];
     610      if (RingSize < MinimumRingSize[Walker->GetTrueFather()->nr])
     611        MinimumRingSize[Walker->GetTrueFather()->nr] = RingSize;
     612    }
     613    if ((RingSize < MinRingSize) || (MinRingSize == -1))
     614      MinRingSize = RingSize;
     615  } else {
     616    *out << Verbose(1) << "No ring containing " << *Root << " with length equal to or smaller than " << MinimumRingSize[Walker->GetTrueFather()->nr] << " found." << endl;
     617  }
     618};
     619
     620void CleanAccounting(class StackClass<atom *> *&TouchedStack, atom **&PredecessorList, int *&ShortestPathList, enum Shading *&ColorList)
     621{
     622  atom *Walker = NULL;
     623  while (!TouchedStack->IsEmpty()){
     624    Walker = TouchedStack->PopFirst();
     625    PredecessorList[Walker->nr] = NULL;
     626    ShortestPathList[Walker->nr] = -1;
     627    ColorList[Walker->nr] = white;
     628  }
     629};
     630
     631
     632void BFSToNextCycle(ofstream *out, atom *&Root, atom *&Walker, bond *&BackEdge, int *&MinimumRingSize, int AtomCount)
     633{
     634  atom **PredecessorList = Malloc<atom*>(AtomCount, "molecule::CyclicStructureAnalysis: **PredecessorList");
     635  int *ShortestPathList = Malloc<int>(AtomCount, "molecule::CyclicStructureAnalysis: *ShortestPathList");
     636  enum Shading *ColorList = Malloc<enum Shading>(AtomCount, "molecule::CyclicStructureAnalysis: *ColorList");
     637  class StackClass<atom *> *BFSStack = new StackClass<atom *> (AtomCount);   // will hold the current ring
     638  class StackClass<atom *> *TouchedStack = new StackClass<atom *> (AtomCount);   // contains all "touched" atoms (that need to be reset after BFS loop)
     639  atom *OtherAtom = Walker;
     640
     641  InitializeAccounting(PredecessorList, ShortestPathList, ColorList, AtomCount);
     642
     643  ResetAccounting(Walker, TouchedStack, ShortestPathList, BFSStack);
     644  while (OtherAtom != NULL) {  // look for Root
     645    Walker = BFSStack->PopFirst();
     646    //*out << Verbose(2) << "Current Walker is " << *Walker << ", we look for SP to Root " << *Root << "." << endl;
     647    for (BondList::const_iterator Runner = Walker->ListOfBonds.begin(); Runner != Walker->ListOfBonds.end(); (++Runner)) {
     648      if (((*Runner) != BackEdge) || (Walker->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
     649        OtherAtom = (*Runner)->GetOtherAtom(Walker);
     650        //*out << Verbose(2) << "Current OtherAtom is: " << OtherAtom->Name << " for bond " << *Binder << "." << endl;
     651        if (ColorList[OtherAtom->nr] == white) {
     652          TouchedStack->Push(OtherAtom);
     653          ColorList[OtherAtom->nr] = lightgray;
     654          PredecessorList[OtherAtom->nr] = Walker;  // Walker is the predecessor
     655          ShortestPathList[OtherAtom->nr] = ShortestPathList[Walker->nr]+1;
     656          //*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;
     657          if (OtherAtom->GetTrueFather()->IsCyclic) { // if the other atom is connected to a ring
     658            MinimumRingSize[Root->GetTrueFather()->nr] = ShortestPathList[OtherAtom->nr]+MinimumRingSize[OtherAtom->GetTrueFather()->nr];
     659            OtherAtom = NULL; //break;
     660            break;
     661          } else
     662            BFSStack->Push(OtherAtom);
     663        } else {
     664          //*out << Verbose(3) << "Not Adding, has already been visited." << endl;
     665        }
     666      } else {
     667        //*out << Verbose(3) << "Not Visiting, is a back edge." << endl;
     668      }
     669    }
     670    ColorList[Walker->nr] = black;
     671    //*out << Verbose(1) << "Coloring Walker " << Walker->Name << " black." << endl;
     672  }
     673  //CleanAccountingLists(TouchedStack, PredecessorList, ShortestPathList, ColorList);
     674
     675  Free(&PredecessorList);
     676  Free(&ShortestPathList);
     677  Free(&ColorList);
     678  delete(BFSStack);
     679};
     680
     681void AssignRingSizetoNonCycleMembers(ofstream *out, int *&MinimumRingSize, int &MinRingSize, int &NumCycles, molecule *mol, bond *&BackEdge)
     682{
     683  atom *Root= NULL;
     684  atom *Walker = NULL;
     685  if (MinRingSize != -1) { // if rings are present
     686    // go over all atoms
     687    Root = mol->start;
     688    while(Root->next != mol->end) {
     689      Root = Root->next;
     690
     691      if (MinimumRingSize[Root->GetTrueFather()->nr] == mol->AtomCount) { // check whether MinimumRingSize is set, if not BFS to next where it is
     692        Walker = Root;
     693
     694        //*out << Verbose(1) << "---------------------------------------------------------------------------------------------------------" << endl;
     695        BFSToNextCycle(out, Root, Walker, BackEdge, MinimumRingSize, mol->AtomCount);
     696
     697      }
     698      *out << Verbose(1) << "Minimum ring size of " << *Root << " is " << MinimumRingSize[Root->GetTrueFather()->nr] << "." << endl;
     699    }
     700    *out << Verbose(1) << "Minimum ring size is " << MinRingSize << ", over " << NumCycles << " cycles total." << endl;
     701  } else
     702    *out << Verbose(1) << "No rings were detected in the molecular structure." << endl;
     703};
     704
    496705/** Analyses the cycles found and returns minimum of all cycle lengths.
    497706 * We begin with a list of Back edges found during DepthFirstSearchAnalysis(). We go through this list - one end is the Root,
     
    511720  class StackClass<atom *> *BFSStack = new StackClass<atom *> (AtomCount);   // will hold the current ring
    512721  class StackClass<atom *> *TouchedStack = new StackClass<atom *> (AtomCount);   // contains all "touched" atoms (that need to be reset after BFS loop)
    513   atom *Walker = NULL, *OtherAtom = NULL, *Root = NULL;
    514   bond *Binder = NULL, *BackEdge = NULL;
    515   int RingSize, NumCycles, MinRingSize = -1;
    516 
    517   // initialise each vertex as white with no predecessor, empty queue, color Root lightgray
    518   for (int i=AtomCount;i--;) {
    519     PredecessorList[i] = NULL;
    520     ShortestPathList[i] = -1;
    521     ColorList[i] = white;
    522   }
     722  atom *Walker = NULL;
     723  atom *OtherAtom = NULL;
     724  atom *Root = NULL;
     725  bond *BackEdge = NULL;
     726  int NumCycles = 0;
     727  int MinRingSize = -1;
     728
     729  InitializeAccounting(PredecessorList, ShortestPathList, ColorList, AtomCount);
    523730
    524731  *out << Verbose(1) << "Back edge list - ";
     
    533740    // this is the source point
    534741    Walker = BackEdge->rightatom;
    535     ShortestPathList[Walker->nr] = 0;
    536     BFSStack->ClearStack();  // start with empty BFS stack
    537     BFSStack->Push(Walker);
    538     TouchedStack->Push(Walker);
     742
     743    ResetAccounting(Walker, TouchedStack, ShortestPathList, BFSStack);
     744
    539745    *out << Verbose(1) << "---------------------------------------------------------------------------------------------------------" << endl;
    540746    OtherAtom = NULL;
    541     do {  // look for Root
    542       Walker = BFSStack->PopFirst();
    543       *out << Verbose(2) << "Current Walker is " << *Walker << ", we look for SP to Root " << *Root << "." << endl;
    544       for (BondList::const_iterator Runner = Walker->ListOfBonds.begin(); Runner != Walker->ListOfBonds.end(); (++Runner)) {
    545         if ((*Runner) != BackEdge) { // only walk along DFS spanning tree (otherwise we always find SP of one being backedge Binder)
    546           OtherAtom = (*Runner)->GetOtherAtom(Walker);
    547 #ifdef ADDHYDROGEN
    548           if (OtherAtom->type->Z != 1) {
    549 #endif
    550             *out << Verbose(2) << "Current OtherAtom is: " << OtherAtom->Name << " for bond " << *Binder << "." << endl;
    551             if (ColorList[OtherAtom->nr] == white) {
    552               TouchedStack->Push(OtherAtom);
    553               ColorList[OtherAtom->nr] = lightgray;
    554               PredecessorList[OtherAtom->nr] = Walker;  // Walker is the predecessor
    555               ShortestPathList[OtherAtom->nr] = ShortestPathList[Walker->nr]+1;
    556               *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;
    557               //if (ShortestPathList[OtherAtom->nr] < MinimumRingSize[Walker->GetTrueFather()->nr]) { // Check for maximum distance
    558                 *out << Verbose(3) << "Putting OtherAtom into queue." << endl;
    559                 BFSStack->Push(OtherAtom);
    560               //}
    561             } else {
    562               *out << Verbose(3) << "Not Adding, has already been visited." << endl;
    563             }
    564             if (OtherAtom == Root)
    565               break;
    566 #ifdef ADDHYDROGEN
    567           } else {
    568             *out << Verbose(2) << "Skipping hydrogen atom " << *OtherAtom << "." << endl;
    569             ColorList[OtherAtom->nr] = black;
    570           }
    571 #endif
    572         } else {
    573           *out << Verbose(2) << "Bond " << *Binder << " not Visiting, is the back edge." << endl;
    574         }
    575       }
    576       ColorList[Walker->nr] = black;
    577       *out << Verbose(1) << "Coloring Walker " << Walker->Name << " black." << endl;
    578       if (OtherAtom == Root) { // if we have found the root, check whether this cycle wasn't already found beforehand
    579         // step through predecessor list
    580         while (OtherAtom != BackEdge->rightatom) {
    581           if (!OtherAtom->GetTrueFather()->IsCyclic)  // if one bond in the loop is not marked as cyclic, we haven't found this cycle yet
    582             break;
    583           else
    584             OtherAtom = PredecessorList[OtherAtom->nr];
    585         }
    586         if (OtherAtom == BackEdge->rightatom) { // if each atom in found cycle is cyclic, loop's been found before already
    587           *out << Verbose(3) << "This cycle was already found before, skipping and removing seeker from search." << endl;\
    588           do {
    589             OtherAtom = TouchedStack->PopLast();
    590             if (PredecessorList[OtherAtom->nr] == Walker) {
    591               *out << Verbose(4) << "Removing " << *OtherAtom << " from lists and stacks." << endl;
    592               PredecessorList[OtherAtom->nr] = NULL;
    593               ShortestPathList[OtherAtom->nr] = -1;
    594               ColorList[OtherAtom->nr] = white;
    595               BFSStack->RemoveItem(OtherAtom);
    596             }
    597           } while ((!TouchedStack->IsEmpty()) && (PredecessorList[OtherAtom->nr] == NULL));
    598           TouchedStack->Push(OtherAtom);  // last was wrongly popped
    599           OtherAtom = BackEdge->rightatom; // set to not Root
    600         } else
    601           OtherAtom = Root;
    602       }
    603     } while ((!BFSStack->IsEmpty()) && (OtherAtom != Root) && (OtherAtom != NULL)); // || (ShortestPathList[OtherAtom->nr] < MinimumRingSize[Walker->GetTrueFather()->nr])));
    604 
    605     if (OtherAtom == Root) {
    606       // now climb back the predecessor list and thus find the cycle members
    607       NumCycles++;
    608       RingSize = 1;
    609       Root->GetTrueFather()->IsCyclic = true;
    610       *out << Verbose(1) << "Found ring contains: ";
    611       Walker = Root;
    612       while (Walker != BackEdge->rightatom) {
    613         *out << Walker->Name << " <-> ";
    614         Walker = PredecessorList[Walker->nr];
    615         Walker->GetTrueFather()->IsCyclic = true;
    616         RingSize++;
    617       }
    618       *out << Walker->Name << "  with a length of " << RingSize << "." << endl << endl;
    619       // walk through all and set MinimumRingSize
    620       Walker = Root;
    621       MinimumRingSize[Walker->GetTrueFather()->nr] = RingSize;
    622       while (Walker != BackEdge->rightatom) {
    623         Walker = PredecessorList[Walker->nr];
    624         if (RingSize < MinimumRingSize[Walker->GetTrueFather()->nr])
    625           MinimumRingSize[Walker->GetTrueFather()->nr] = RingSize;
    626       }
    627       if ((RingSize < MinRingSize) || (MinRingSize == -1))
    628         MinRingSize = RingSize;
    629     } else {
    630       *out << Verbose(1) << "No ring containing " << *Root << " with length equal to or smaller than " << MinimumRingSize[Walker->GetTrueFather()->nr] << " found." << endl;
    631     }
    632 
    633     // now clean the lists
    634     while (!TouchedStack->IsEmpty()){
    635       Walker = TouchedStack->PopFirst();
    636       PredecessorList[Walker->nr] = NULL;
    637       ShortestPathList[Walker->nr] = -1;
    638       ColorList[Walker->nr] = white;
    639     }
    640   }
    641   if (MinRingSize != -1) {
    642     // go over all atoms
    643     Root = start;
    644     while(Root->next != end) {
    645       Root = Root->next;
    646 
    647       if (MinimumRingSize[Root->GetTrueFather()->nr] == AtomCount) { // check whether MinimumRingSize is set, if not BFS to next where it is
    648         Walker = Root;
    649         ShortestPathList[Walker->nr] = 0;
    650         BFSStack->ClearStack();  // start with empty BFS stack
    651         BFSStack->Push(Walker);
    652         TouchedStack->Push(Walker);
    653         //*out << Verbose(1) << "---------------------------------------------------------------------------------------------------------" << endl;
    654         OtherAtom = Walker;
    655         while (OtherAtom != NULL) {  // look for Root
    656           Walker = BFSStack->PopFirst();
    657           //*out << Verbose(2) << "Current Walker is " << *Walker << ", we look for SP to Root " << *Root << "." << endl;
    658           for (BondList::const_iterator Runner = Walker->ListOfBonds.begin(); Runner != Walker->ListOfBonds.end(); (++Runner)) {
    659             if (((*Runner) != BackEdge) || (Walker->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
    660               OtherAtom = (*Runner)->GetOtherAtom(Walker);
    661               //*out << Verbose(2) << "Current OtherAtom is: " << OtherAtom->Name << " for bond " << *Binder << "." << endl;
    662               if (ColorList[OtherAtom->nr] == white) {
    663                 TouchedStack->Push(OtherAtom);
    664                 ColorList[OtherAtom->nr] = lightgray;
    665                 PredecessorList[OtherAtom->nr] = Walker;  // Walker is the predecessor
    666                 ShortestPathList[OtherAtom->nr] = ShortestPathList[Walker->nr]+1;
    667                 //*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;
    668                 if (OtherAtom->GetTrueFather()->IsCyclic) { // if the other atom is connected to a ring
    669                   MinimumRingSize[Root->GetTrueFather()->nr] = ShortestPathList[OtherAtom->nr]+MinimumRingSize[OtherAtom->GetTrueFather()->nr];
    670                   OtherAtom = NULL; //break;
    671                   break;
    672                 } else
    673                   BFSStack->Push(OtherAtom);
    674               } else {
    675                 //*out << Verbose(3) << "Not Adding, has already been visited." << endl;
    676               }
    677             } else {
    678               //*out << Verbose(3) << "Not Visiting, is a back edge." << endl;
    679             }
    680           }
    681           ColorList[Walker->nr] = black;
    682           //*out << Verbose(1) << "Coloring Walker " << Walker->Name << " black." << endl;
    683         }
    684 
    685         // now clean the lists
    686         while (!TouchedStack->IsEmpty()){
    687           Walker = TouchedStack->PopFirst();
    688           PredecessorList[Walker->nr] = NULL;
    689           ShortestPathList[Walker->nr] = -1;
    690           ColorList[Walker->nr] = white;
    691         }
    692       }
    693       *out << Verbose(1) << "Minimum ring size of " << *Root << " is " << MinimumRingSize[Root->GetTrueFather()->nr] << "." << endl;
    694     }
    695     *out << Verbose(1) << "Minimum ring size is " << MinRingSize << ", over " << NumCycles << " cycles total." << endl;
    696   } else
    697     *out << Verbose(1) << "No rings were detected in the molecular structure." << endl;
    698 
     747    CyclicBFSFromRootToRoot(out, Root, BackEdge, TouchedStack, ShortestPathList, PredecessorList, BFSStack, ColorList);
     748
     749    RetrieveCycleMembers(out, Root, OtherAtom, BackEdge, PredecessorList, MinimumRingSize, MinRingSize);
     750
     751    CleanAccounting(TouchedStack, PredecessorList, ShortestPathList, ColorList);
     752  }
    699753  Free(&PredecessorList);
    700754  Free(&ShortestPathList);
    701755  Free(&ColorList);
    702756  delete(BFSStack);
     757
     758  AssignRingSizetoNonCycleMembers(out, MinimumRingSize, MinRingSize, NumCycles, this, BackEdge);
     759
    703760};
    704761
Note: See TracChangeset for help on using the changeset viewer.