Changeset ce7cc5 for src/molecule_graph.cpp

Timestamp:

Oct 18, 2009, 5:52:47 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:

43587e

Parents:

ba4170

Message:

Refactored molecule::BreadthFirstSearchAdd()

• new function: BreadthFirstSearchAdd_Init(), BreadthFirstSearchAdd_VisitedNode(), BreadthFirstSearchAdd_UnvisitedNode()
• new structure BFSAccounting contains all of the accounting data needed for Breadth First Search.

File:

• src/molecule_graph.cpp (modified) (2 diffs)

src/molecule_graph.cpp

@@ -983 +983 @@
 };
 
+struct BFSAccounting {
+  atom **PredecessorList;
+  int *ShortestPathList;
+  enum Shading *ColorList;
+  class StackClass<atom *> *AtomStack;
+  int AtomCount;
+  int BondOrder;
+  atom *Root;
+};
+
+void BreadthFirstSearchAdd_Init(struct BFSAccounting &BFS, atom *&Root, int AtomCount, int BondOrder, atom **AddedAtomList = NULL)
+{
+  BFS.AtomCount = AtomCount;
+  BFS.BondOrder = BondOrder;
+  BFS.PredecessorList = Malloc<atom*>(AtomCount, "molecule::BreadthFirstSearchAdd_Init: **PredecessorList");
+  BFS.ShortestPathList = Malloc<int>(AtomCount, "molecule::BreadthFirstSearchAdd_Init: *ShortestPathList");
+  BFS.ColorList = Malloc<enum Shading>(AtomCount, "molecule::BreadthFirstSearchAdd_Init: *ColorList");
+  BFS.AtomStack = new StackClass<atom *>(AtomCount);
+
+  BFS.Root = Root;
+  BFS.AtomStack->ClearStack();
+  BFS.AtomStack->Push(Root);
+
+  // initialise each vertex as white with no predecessor, empty queue, color Root lightgray
+  for (int i=AtomCount;i--;) {
+    BFS.PredecessorList[i] = NULL;
+    BFS.ShortestPathList[i] = -1;
+    if ((AddedAtomList != NULL) && (AddedAtomList[i] != NULL)) // mark already present atoms (i.e. Root and maybe others) as visited
+      BFS.ColorList[i] = lightgray;
+    else
+      BFS.ColorList[i] = white;
+  }
+  BFS.ShortestPathList[Root->nr] = 0;
+};
+
+void BreadthFirstSearchAdd_Free(struct BFSAccounting &BFS)
+{
+  Free(&BFS.PredecessorList);
+  Free(&BFS.ShortestPathList);
+  Free(&BFS.ColorList);
+  delete(BFS.AtomStack);
+  BFS.AtomCount = 0;
+};
+
+
+void BreadthFirstSearchAdd_UnvisitedNode(ofstream *out, molecule *Mol, struct BFSAccounting &BFS, atom *&Walker, atom *&OtherAtom, bond *&Binder, bond *&Bond, atom **&AddedAtomList, bond **&AddedBondList, bool IsAngstroem)
+{
+  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)
+    BFS.ColorList[OtherAtom->nr] = lightgray;
+  BFS.PredecessorList[OtherAtom->nr] = Walker;  // Walker is the predecessor
+  BFS.ShortestPathList[OtherAtom->nr] = BFS.ShortestPathList[Walker->nr]+1;
+  *out << Verbose(2) << "Coloring OtherAtom " << OtherAtom->Name << " " << ((BFS.ColorList[OtherAtom->nr] == white) ? "white" : "lightgray") << ", its predecessor is " << Walker->Name << " and its Shortest Path is " << BFS.ShortestPathList[OtherAtom->nr] << " egde(s) long." << endl;
+  if ((((BFS.ShortestPathList[OtherAtom->nr] < BFS.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->CopyBond(AddedAtomList[Walker->nr], AddedAtomList[OtherAtom->nr], Binder);
+      *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->CopyBond(AddedAtomList[Walker->nr], AddedAtomList[OtherAtom->nr], Binder);
+        *out << ", added Bond " << *(AddedBondList[Binder->nr]);
+      } else
+        *out << ", not added Bond ";
+    }
+    *out << ", putting OtherAtom into queue." << endl;
+    BFS.AtomStack->Push(OtherAtom);
+  } else { // out of bond order, then replace
+    if ((AddedAtomList[OtherAtom->nr] == NULL) && (Binder->Cyclic))
+      BFS.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 (BFS.ShortestPathList[OtherAtom->nr] >= BFS.BondOrder)
+      *out << Verbose(3) << "Not Queueing, is out of Bond Count of " << BFS.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->CopyBond(AddedAtomList[Walker->nr], AddedAtomList[OtherAtom->nr], Binder);
+      } else {
+  #ifdef ADDHYDROGEN
+        if (!Mol->AddHydrogenReplacementAtom(out, Binder, AddedAtomList[Walker->nr], Walker, OtherAtom, IsAngstroem))
+          exit(1);
+  #endif
+      }
+    }
+  }
+};
+
+void BreadthFirstSearchAdd_VisitedNode(ofstream *out, molecule *Mol, struct BFSAccounting &BFS, atom *&Walker, atom *&OtherAtom, bond *&Binder, bond *&Bond, atom **&AddedAtomList, bond **&AddedBondList, bool IsAngstroem)
+{
+  *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) && (((BFS.ShortestPathList[Walker->nr]+1) < BFS.BondOrder))) {
+      AddedBondList[Binder->nr] = Mol->CopyBond(AddedAtomList[Walker->nr], AddedAtomList[OtherAtom->nr], Binder);
+    } 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, IsAngstroem))
+        exit(1);
+  #endif
+    }
+  }
+};
 
 /** Adds atoms up to \a BondCount distance from \a *Root and notes them down in \a **AddedAtomList.
@@ -998 +1104 @@
 void molecule::BreadthFirstSearchAdd(ofstream *out, molecule *Mol, atom **&AddedAtomList, bond **&AddedBondList, atom *Root, bond *Bond, int BondOrder, bool IsAngstroem)
 {
-  atom **PredecessorList = Malloc<atom*>(AtomCount, "molecule::BreadthFirstSearchAdd: **PredecessorList");
-  int *ShortestPathList = Malloc<int>(AtomCount, "molecule::BreadthFirstSearchAdd: *ShortestPathList");
-  enum Shading *ColorList = Malloc<enum Shading>(AtomCount, "molecule::BreadthFirstSearchAdd: *ColorList");
-  class StackClass<atom *> *AtomStack = new StackClass<atom *>(AtomCount);
+  struct BFSAccounting BFS;
   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;
+
+  BreadthFirstSearchAdd_Init(BFS, Root, BondOrder, AtomCount, AddedAtomList);
 
   // and go on ... Queue always contains all lightgray vertices
-  while (!AtomStack->IsEmpty()) {
+  while (!BFS.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
+    Walker = BFS.AtomStack->PopFirst(); // pop oldest added
     *out << Verbose(1) << "Current Walker is: " << Walker->Name << ", and has " << Walker->ListOfBonds.size() << " bonds." << endl;
     for (BondList::const_iterator Runner = Walker->ListOfBonds.begin(); Runner != Walker->ListOfBonds.end(); (++Runner)) {
       if ((*Runner) != NULL) { // don't look at bond equal NULL
+        Binder = (*Runner);
         OtherAtom = (*Runner)->GetOtherAtom(Walker);
         *out << Verbose(2) << "Current OtherAtom is: " << OtherAtom->Name << " for bond " << *(*Runner) << "." << endl;
-        if (ColorList[OtherAtom->nr] == white) {
-          if ((*Runner) != 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) && ((*Runner) != 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[(*Runner)->nr] = Mol->CopyBond(AddedAtomList[Walker->nr], AddedAtomList[OtherAtom->nr], (*Runner));
-              *out << " and bond " << *(AddedBondList[(*Runner)->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[(*Runner)->nr] == NULL) {
-                AddedBondList[(*Runner)->nr] = Mol->CopyBond(AddedAtomList[Walker->nr], AddedAtomList[OtherAtom->nr], (*Runner));
-                *out << ", added Bond " << *(AddedBondList[(*Runner)->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) && ((*Runner)->Cyclic))
-              ColorList[OtherAtom->nr] = white; // unmark if it has not been queued/added, to make it available via its other bonds (cyclic)
-            if ((*Runner) == 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 (!(*Runner)->Cyclic)
-              *out << ", is not part of a cyclic bond, saturating bond with Hydrogen." << endl;
-            if (AddedBondList[(*Runner)->nr] == NULL) {
-              if ((AddedAtomList[OtherAtom->nr] != NULL)) { // .. whether we add or saturate
-                AddedBondList[(*Runner)->nr] = Mol->CopyBond(AddedAtomList[Walker->nr], AddedAtomList[OtherAtom->nr], (*Runner));
-              } else {
-#ifdef ADDHYDROGEN
-                if (!Mol->AddHydrogenReplacementAtom(out, (*Runner), AddedAtomList[Walker->nr], Walker, OtherAtom, IsAngstroem))
-                  exit(1);
-#endif
-              }
-            }
-          }
+        if (BFS.ColorList[OtherAtom->nr] == white) {
+          BreadthFirstSearchAdd_UnvisitedNode(out, Mol, BFS, Walker, OtherAtom, Binder, Bond, AddedAtomList, AddedBondList, IsAngstroem);
         } 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[(*Runner)->nr] == NULL) {
-            if (((*Runner) != Bond) && ((*Runner)->Cyclic) && (((ShortestPathList[Walker->nr]+1) < BondOrder))) {
-              AddedBondList[(*Runner)->nr] = Mol->CopyBond(AddedAtomList[Walker->nr], AddedAtomList[OtherAtom->nr], (*Runner));
-            } else { // if it's root bond it has to broken (otherwise we would not create the fragments)
-#ifdef ADDHYDROGEN
-              if(!Mol->AddHydrogenReplacementAtom(out, (*Runner), AddedAtomList[Walker->nr], Walker, OtherAtom, IsAngstroem))
-                exit(1);
-#endif
-            }
-          }
+          BreadthFirstSearchAdd_VisitedNode(out, Mol, BFS, Walker, OtherAtom, Binder, Bond, AddedAtomList, AddedBondList, IsAngstroem);
         }
       }
     }
-    ColorList[Walker->nr] = black;
+    BFS.ColorList[Walker->nr] = black;
     *out << Verbose(1) << "Coloring Walker " << Walker->Name << " black." << endl;
   }
-  Free(&PredecessorList);
-  Free(&ShortestPathList);
-  Free(&ColorList);
-  delete(AtomStack);
+  BreadthFirstSearchAdd_Free(BFS);
 };