Changeset ec7511 for src

Timestamp:

Apr 29, 2014, 12:42:43 PM (11 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:

237f93

Parents:

4b10fd

git-author:

Frederik Heber <heber@…> (11/11/13 09:49:19)

git-committer:

Frederik Heber <heber@…> (04/29/14 12:42:43)

Message:

FIX: CyclicStructureAnalysis falsely used DFS, skipped some cycles.

• FIX: CyclicStructureAnalysis did use DFS instead of BFS for finding cycles. Note that CyclicStructureAnalysis with coronene would find supercycles and not the smaller interconnected ones.
• FIX: Cycles were skipped when all bonds marked cyclic, not enough. In interconnected aromatic rings, bonds may very well be marked as cyclic from earlier extraction of cycles and yet the specific cycle might not have been found yet (e.g. coronene). In this case we now check whether this particular cycle has already been extracted and only skip if so.
• TESTFIX: added new fragmentation regression tests on some metallic systems.
• this is mainly for regression on bond graph detection and cycle analysis.

Location:

src/Graph

Files:

• CyclicStructureAnalysis.cpp (modified) (5 diffs)
• CyclicStructureAnalysis.hpp (modified) (1 diff)

src/Graph/CyclicStructureAnalysis.cpp

@@ -36 +36 @@
 
 #include "CyclicStructureAnalysis.hpp"
+
+#include <algorithm>
 
 #include "Atom/atom.hpp"
@@ -110 +112 @@
   do { // look for Root
     ASSERT(!BFSStack.empty(), "CyclicStructureAnalysis_CyclicBFSFromRootToRoot() - BFSStack is empty!");
-    Walker = BFSStack.front();
-    BFSStack.pop_front();
+    Walker = BFSStack.back();
+    BFSStack.pop_back();
     LOG(2, "INFO: Current Walker is " << *Walker << ", we look for SP to Root " << *Root << ".");
     const BondList& ListOfBonds = Walker->getListOfBonds();
@@ -159 +161 @@
       // if each atom in found cycle is cyclic, loop's been found before already
       if (OtherAtom == BackEdge->rightatom) { // loop got round completely
-        LOG(3, "INFO: This cycle was already found before, skipping and removing seeker from search.");
-        do {
-          ASSERT(!TouchedStack.empty(), "CyclicStructureAnalysis_CyclicBFSFromRootToRoot() - TouchedStack is empty!");
-          OtherAtom = TouchedStack.front();
-          TouchedStack.pop_front();
-          if (PredecessorList[OtherAtom->getNr()] == Walker) {
-            LOG(4, "INFO: Removing " << *OtherAtom << " from lists and stacks.");
-            PredecessorList[OtherAtom->getNr()] = NULL;
-            ShortestPathList[OtherAtom->getNr()] = -1;
-            ColorList[OtherAtom->getNr()] = GraphEdge::white;
-            // rats ... deque has no find()
-            std::deque<atom *>::iterator iter = find(
-                BFSStack.begin(),
-                BFSStack.end(),
-                OtherAtom);
-            ASSERT(iter != BFSStack.end(),
-                "CyclicStructureAnalysis_CyclicBFSFromRootToRoot() - can't find "+toString(*OtherAtom)+" on stack!");
-            BFSStack.erase(iter);
-          }
-        } while ((!TouchedStack.empty()) && (PredecessorList[OtherAtom->getNr()] == NULL));
-        TouchedStack.push_front(OtherAtom); // last was wrongly popped
-        OtherAtom = BackEdge->rightatom; // set to not Root
+        LOG(3, "INFO: All bonds are marked cyclic already, checking allcycles whether cycle is already present.");
+        const cycle_t currentcycle = extractCurrentCycle(BackEdge);
+        const cycles_t::const_iterator iter =
+            std::find(allcycles.begin(), allcycles.end(), currentcycle);
+        if (iter == allcycles.end()) { // not found
+          OtherAtom = Root;
+          LOG(2, "INFO: Cycle is not present.");
+          LOG(2, "INFO: We have reached Root " << *OtherAtom << " and may extract the cycle.");
+        } else {
+          LOG(2, "INFO: Cycle is already present.");
+          do {
+            ASSERT(!TouchedStack.empty(), "CyclicStructureAnalysis_CyclicBFSFromRootToRoot() - TouchedStack is empty!");
+            OtherAtom = TouchedStack.front();
+            TouchedStack.pop_front();
+            if (PredecessorList[OtherAtom->getNr()] == Walker) {
+              LOG(4, "INFO: Removing " << *OtherAtom << " from lists and stacks.");
+              PredecessorList[OtherAtom->getNr()] = NULL;
+              ShortestPathList[OtherAtom->getNr()] = -1;
+              ColorList[OtherAtom->getNr()] = GraphEdge::white;
+              // rats ... deque has no find()
+              std::deque<atom *>::iterator iter = find(
+                  BFSStack.begin(),
+                  BFSStack.end(),
+                  OtherAtom);
+              ASSERT(iter != BFSStack.end(),
+                  "CyclicStructureAnalysis_CyclicBFSFromRootToRoot() - can't find "+toString(*OtherAtom)+" on stack!");
+              BFSStack.erase(iter);
+            }
+          } while ((!TouchedStack.empty()) && (PredecessorList[OtherAtom->getNr()] == NULL));
+          TouchedStack.push_front(OtherAtom); // last was wrongly popped
+          OtherAtom = BackEdge->rightatom; // set to not Root
+        }
       } else {
         OtherAtom = Root;
@@ -187 +199 @@
     }
   } while ((!BFSStack.empty()) && (OtherAtom != Root) && (OtherAtom != NULL)); // || (ShortestPathList[OtherAtom->getNr()] < MinimumRingSize[Walker->GetTrueFather()->getNr()])));
+}
+
+/** Extracts cycle from BFSAccounting::PredecessorList with given \a BackEdge and current \a Root.
+ *
+ * \param BackEdge back edge of this cycle
+ */
+CyclicStructureAnalysis::cycle_t CyclicStructureAnalysis::extractCurrentCycle(
+    bond::ptr &BackEdge)
+{
+  CyclicStructureAnalysis::cycle_t currentcycle;
+  atom *Walker = Root;
+  currentcycle.insert(Walker->GetTrueFather()->getId());
+  std::stringstream output;
+  while (Walker != BackEdge->rightatom) { // leftatom is root
+    Walker = PredecessorList[Walker->getNr()];
+    Walker->GetTrueFather()->IsCyclic = true;
+    output << Walker->getName() << " <-> ";
+#ifndef NDEBUG
+    std::pair< cycle_t::iterator, bool > inserter =
+#endif
+        currentcycle.insert(Walker->GetTrueFather()->getId());
+    ASSERT( inserter.second,
+        "CyclicStructureAnalysis::RetrieveCycleMembers() - we already inserted "
+        +toString(Walker->GetTrueFather()->getId())+" into currentcycle.");
+  }
+  LOG(3, "INFO: " << output.str() << Root->getName());
+  return currentcycle;
 }
 
@@ -208 +247 @@
     // now climb back the predecessor list and thus find the cycle members
     NumCycles++;
-    RingSize = 1;
     Root->GetTrueFather()->IsCyclic = true;
 
+    // exctract cycle
     {
-      CyclicStructureAnalysis::cycle_t currentcycle;
-      std::stringstream output;
-      output << "Found ring contains: ";
-      Walker = Root;
-      currentcycle.insert(Walker->GetTrueFather()->getId());
-      while (Walker != BackEdge->rightatom) { // leftatom is root
-        output << Walker->getName() << " <-> ";
-        Walker = PredecessorList[Walker->getNr()];
-        Walker->GetTrueFather()->IsCyclic = true;
-#ifndef NDEBUG
-        std::pair< cycle_t::iterator, bool > inserter =
-#endif
-            currentcycle.insert(Walker->GetTrueFather()->getId());
-        ASSERT( inserter.second,
-            "CyclicStructureAnalysis::RetrieveCycleMembers() - we already inserted "
-            +toString(Walker->GetTrueFather()->getId())+" into currentcycle.");
-        RingSize++;
-      }
-      output << Walker->getName() << "  with a length of " << RingSize << ".";
-      LOG(0, "INFO: " << output.str());
-      allcycles.push_back(currentcycle);
+      allcycles.push_back(extractCurrentCycle(BackEdge));
+      CyclicStructureAnalysis::cycle_t &lastcycle = allcycles.back();
+      RingSize = lastcycle.size();
+      LOG(0, "INFO: " << "Found ring contains: " << lastcycle << "  with a length of " << RingSize);
     }
 

src/Graph/CyclicStructureAnalysis.hpp

@@ -60 +60 @@
   void CyclicBFSFromRootToRoot(atom *&OtherAtom, bond::ptr &BackEdge);
   void RetrieveCycleMembers(atom *&OtherAtom, bond::ptr &BackEdge, int &MinRingSize, int &NumCycles);
+  cycle_t extractCurrentCycle(bond::ptr &BackEdge);
   void BFSToNextCycle(atom *Walker);
   void AssignRingSizetoNonCycleMembers(const int MinRingSize, const int NumCycles);