Changeset ec7511


Ignore:
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.
Files:
28 added
4 edited

Legend:

Unmodified
Added
Removed

  • src/Graph/CyclicStructureAnalysis.cpp

    r4b10fd rec7511  
    3636
    3737#include "CyclicStructureAnalysis.hpp"
     38
     39#include <algorithm>
    3840
    3941#include "Atom/atom.hpp"
    … …  
    110112  do { // look for Root
    111113    ASSERT(!BFSStack.empty(), "CyclicStructureAnalysis_CyclicBFSFromRootToRoot() - BFSStack is empty!");
    112     Walker = BFSStack.front();
    113     BFSStack.pop_front();
     114    Walker = BFSStack.back();
     115    BFSStack.pop_back();
    114116    LOG(2, "INFO: Current Walker is " << *Walker << ", we look for SP to Root " << *Root << ".");
    115117    const BondList& ListOfBonds = Walker->getListOfBonds();
    … …  
    159161      // if each atom in found cycle is cyclic, loop's been found before already
    160162      if (OtherAtom == BackEdge->rightatom) { // loop got round completely
    161         LOG(3, "INFO: This cycle was already found before, skipping and removing seeker from search.");
    162         do {
    163           ASSERT(!TouchedStack.empty(), "CyclicStructureAnalysis_CyclicBFSFromRootToRoot() - TouchedStack is empty!");
    164           OtherAtom = TouchedStack.front();
    165           TouchedStack.pop_front();
    166           if (PredecessorList[OtherAtom->getNr()] == Walker) {
    167             LOG(4, "INFO: Removing " << *OtherAtom << " from lists and stacks.");
    168             PredecessorList[OtherAtom->getNr()] = NULL;
    169             ShortestPathList[OtherAtom->getNr()] = -1;
    170             ColorList[OtherAtom->getNr()] = GraphEdge::white;
    171             // rats ... deque has no find()
    172             std::deque<atom *>::iterator iter = find(
    173                 BFSStack.begin(),
    174                 BFSStack.end(),
    175                 OtherAtom);
    176             ASSERT(iter != BFSStack.end(),
    177                 "CyclicStructureAnalysis_CyclicBFSFromRootToRoot() - can't find "+toString(*OtherAtom)+" on stack!");
    178             BFSStack.erase(iter);
    179           }
    180         } while ((!TouchedStack.empty()) && (PredecessorList[OtherAtom->getNr()] == NULL));
    181         TouchedStack.push_front(OtherAtom); // last was wrongly popped
    182         OtherAtom = BackEdge->rightatom; // set to not Root
     163        LOG(3, "INFO: All bonds are marked cyclic already, checking allcycles whether cycle is already present.");
     164        const cycle_t currentcycle = extractCurrentCycle(BackEdge);
     165        const cycles_t::const_iterator iter =
     166            std::find(allcycles.begin(), allcycles.end(), currentcycle);
     167        if (iter == allcycles.end()) { // not found
     168          OtherAtom = Root;
     169          LOG(2, "INFO: Cycle is not present.");
     170          LOG(2, "INFO: We have reached Root " << *OtherAtom << " and may extract the cycle.");
     171        } else {
     172          LOG(2, "INFO: Cycle is already present.");
     173          do {
     174            ASSERT(!TouchedStack.empty(), "CyclicStructureAnalysis_CyclicBFSFromRootToRoot() - TouchedStack is empty!");
     175            OtherAtom = TouchedStack.front();
     176            TouchedStack.pop_front();
     177            if (PredecessorList[OtherAtom->getNr()] == Walker) {
     178              LOG(4, "INFO: Removing " << *OtherAtom << " from lists and stacks.");
     179              PredecessorList[OtherAtom->getNr()] = NULL;
     180              ShortestPathList[OtherAtom->getNr()] = -1;
     181              ColorList[OtherAtom->getNr()] = GraphEdge::white;
     182              // rats ... deque has no find()
     183              std::deque<atom *>::iterator iter = find(
     184                  BFSStack.begin(),
     185                  BFSStack.end(),
     186                  OtherAtom);
     187              ASSERT(iter != BFSStack.end(),
     188                  "CyclicStructureAnalysis_CyclicBFSFromRootToRoot() - can't find "+toString(*OtherAtom)+" on stack!");
     189              BFSStack.erase(iter);
     190            }
     191          } while ((!TouchedStack.empty()) && (PredecessorList[OtherAtom->getNr()] == NULL));
     192          TouchedStack.push_front(OtherAtom); // last was wrongly popped
     193          OtherAtom = BackEdge->rightatom; // set to not Root
     194        }
    183195      } else {
    184196        OtherAtom = Root;
    … …  
    187199    }
    188200  } while ((!BFSStack.empty()) && (OtherAtom != Root) && (OtherAtom != NULL)); // || (ShortestPathList[OtherAtom->getNr()] < MinimumRingSize[Walker->GetTrueFather()->getNr()])));
     201}
     202
     203/** Extracts cycle from BFSAccounting::PredecessorList with given \a BackEdge and current \a Root.
     204 *
     205 * \param BackEdge back edge of this cycle
     206 */
     207CyclicStructureAnalysis::cycle_t CyclicStructureAnalysis::extractCurrentCycle(
     208    bond::ptr &BackEdge)
     209{
     210  CyclicStructureAnalysis::cycle_t currentcycle;
     211  atom *Walker = Root;
     212  currentcycle.insert(Walker->GetTrueFather()->getId());
     213  std::stringstream output;
     214  while (Walker != BackEdge->rightatom) { // leftatom is root
     215    Walker = PredecessorList[Walker->getNr()];
     216    Walker->GetTrueFather()->IsCyclic = true;
     217    output << Walker->getName() << " <-> ";
     218#ifndef NDEBUG
     219    std::pair< cycle_t::iterator, bool > inserter =
     220#endif
     221        currentcycle.insert(Walker->GetTrueFather()->getId());
     222    ASSERT( inserter.second,
     223        "CyclicStructureAnalysis::RetrieveCycleMembers() - we already inserted "
     224        +toString(Walker->GetTrueFather()->getId())+" into currentcycle.");
     225  }
     226  LOG(3, "INFO: " << output.str() << Root->getName());
     227  return currentcycle;
    189228}
    190229
    … …  
    208247    // now climb back the predecessor list and thus find the cycle members
    209248    NumCycles++;
    210     RingSize = 1;
    211249    Root->GetTrueFather()->IsCyclic = true;
    212250
     251    // exctract cycle
    213252    {
    214       CyclicStructureAnalysis::cycle_t currentcycle;
    215       std::stringstream output;
    216       output << "Found ring contains: ";
    217       Walker = Root;
    218       currentcycle.insert(Walker->GetTrueFather()->getId());
    219       while (Walker != BackEdge->rightatom) { // leftatom is root
    220         output << Walker->getName() << " <-> ";
    221         Walker = PredecessorList[Walker->getNr()];
    222         Walker->GetTrueFather()->IsCyclic = true;
    223 #ifndef NDEBUG
    224         std::pair< cycle_t::iterator, bool > inserter =
    225 #endif
    226             currentcycle.insert(Walker->GetTrueFather()->getId());
    227         ASSERT( inserter.second,
    228             "CyclicStructureAnalysis::RetrieveCycleMembers() - we already inserted "
    229             +toString(Walker->GetTrueFather()->getId())+" into currentcycle.");
    230         RingSize++;
    231       }
    232       output << Walker->getName() << "  with a length of " << RingSize << ".";
    233       LOG(0, "INFO: " << output.str());
    234       allcycles.push_back(currentcycle);
     253      allcycles.push_back(extractCurrentCycle(BackEdge));
     254      CyclicStructureAnalysis::cycle_t &lastcycle = allcycles.back();
     255      RingSize = lastcycle.size();
     256      LOG(0, "INFO: " << "Found ring contains: " << lastcycle << "  with a length of " << RingSize);
    235257    }
    236258

  • src/Graph/CyclicStructureAnalysis.hpp

    r4b10fd rec7511  
    6060  void CyclicBFSFromRootToRoot(atom *&OtherAtom, bond::ptr &BackEdge);
    6161  void RetrieveCycleMembers(atom *&OtherAtom, bond::ptr &BackEdge, int &MinRingSize, int &NumCycles);
     62  cycle_t extractCurrentCycle(bond::ptr &BackEdge);
    6263  void BFSToNextCycle(atom *Walker);
    6364  void AssignRingSizetoNonCycleMembers(const int MinRingSize, const int NumCycles);

  • tests/Fragmentations/Makefile.am

    r4b10fd rec7511  
    1313        $(srcdir)/Fragmenting/1_2-dimethylbenzene \
    1414        $(srcdir)/Fragmenting/2-methylcyclohexanone \
     15        $(srcdir)/Fragmenting/anthracene \
    1516        $(srcdir)/Fragmenting/benzene \
    1617        $(srcdir)/Fragmenting/cholesterol \
     18        $(srcdir)/Fragmenting/coronene \
    1719        $(srcdir)/Fragmenting/cycloheptane \
    1820        $(srcdir)/Fragmenting/dimethyl_bromomalonate \
    … …  
    2022        $(srcdir)/Fragmenting/heptan \
    2123        $(srcdir)/Fragmenting/isoleucine \
     24        $(srcdir)/Fragmenting/naphthalene \
    2225        $(srcdir)/Fragmenting/neohexane \
    2326        $(srcdir)/Fragmenting/N_N-dimethylacetamide \
     27        $(srcdir)/Fragmenting/phenanthrene \
    2428        $(srcdir)/Fragmenting/proline \
    2529        $(srcdir)/Fragmenting/putrescine \
    … …  
    4448        Fragmenting/2-methylcyclohexanone/testsuite-fragmenting-2-methylcyclohexanone-order3.at \
    4549        Fragmenting/2-methylcyclohexanone/testsuite-fragmenting-2-methylcyclohexanone-order4.at \
     50        Fragmenting/anthracene/testsuite-fragmenting-anthracene-order1.at \
     51        Fragmenting/anthracene/testsuite-fragmenting-anthracene-order2.at \
     52        Fragmenting/anthracene/testsuite-fragmenting-anthracene-order3.at \
     53        Fragmenting/anthracene/testsuite-fragmenting-anthracene-order4.at \
     54        Fragmenting/anthracene/testsuite-fragmenting-anthracene-order5.at \
     55        Fragmenting/anthracene/testsuite-fragmenting-anthracene-order6.at \
    4656        Fragmenting/benzene/testsuite-fragmenting-benzene-order1.at \
    4757        Fragmenting/benzene/testsuite-fragmenting-benzene-order2.at \
    … …  
    5464        Fragmenting/cholesterol/testsuite-fragmenting-cholesterol-order3.at \
    5565        Fragmenting/cholesterol/testsuite-fragmenting-cholesterol-order4.at \
     66        Fragmenting/coronene/testsuite-fragmenting-coronene-order1.at \
     67        Fragmenting/coronene/testsuite-fragmenting-coronene-order2.at \
     68        Fragmenting/coronene/testsuite-fragmenting-coronene-order3.at \
     69        Fragmenting/coronene/testsuite-fragmenting-coronene-order4.at \
     70        Fragmenting/coronene/testsuite-fragmenting-coronene-order5.at \
     71        Fragmenting/coronene/testsuite-fragmenting-coronene-order6.at \
    5672        Fragmenting/cycloheptane/testsuite-fragmenting-cycloheptane-order1.at \
    5773        Fragmenting/cycloheptane/testsuite-fragmenting-cycloheptane-order2.at \
    … …  
    8298        Fragmenting/isoleucine/testsuite-fragmenting-isoleucine-order5.at \
    8399        Fragmenting/isoleucine/testsuite-fragmenting-isoleucine-order6.at \
     100        Fragmenting/naphthalene/testsuite-fragmenting-naphthalene-order1.at \
     101        Fragmenting/naphthalene/testsuite-fragmenting-naphthalene-order2.at \
     102        Fragmenting/naphthalene/testsuite-fragmenting-naphthalene-order3.at \
     103        Fragmenting/naphthalene/testsuite-fragmenting-naphthalene-order4.at \
     104        Fragmenting/naphthalene/testsuite-fragmenting-naphthalene-order5.at \
     105        Fragmenting/naphthalene/testsuite-fragmenting-naphthalene-order6.at \
    84106        Fragmenting/neohexane/testsuite-fragmenting-neohexane-order1.at \
    85107        Fragmenting/neohexane/testsuite-fragmenting-neohexane-order2.at \
    … …  
    94116        Fragmenting/N_N-dimethylacetamide/testsuite-fragmenting-N_N-dimethylacetamide-order5.at \
    95117        Fragmenting/N_N-dimethylacetamide/testsuite-fragmenting-N_N-dimethylacetamide-order6.at \
     118        Fragmenting/phenanthrene/testsuite-fragmenting-phenanthrene-order1.at \
     119        Fragmenting/phenanthrene/testsuite-fragmenting-phenanthrene-order2.at \
     120        Fragmenting/phenanthrene/testsuite-fragmenting-phenanthrene-order3.at \
     121        Fragmenting/phenanthrene/testsuite-fragmenting-phenanthrene-order4.at \
     122        Fragmenting/phenanthrene/testsuite-fragmenting-phenanthrene-order5.at \
     123        Fragmenting/phenanthrene/testsuite-fragmenting-phenanthrene-order6.at \
    96124        Fragmenting/proline/testsuite-fragmenting-proline-order1.at \
    97125        Fragmenting/proline/testsuite-fragmenting-proline-order2.at \

  • tests/Fragmentations/testsuite.at

    r4b10fd rec7511  
    6262m4_include(Fragmenting/2-methylcyclohexanone/testsuite-fragmenting-2-methylcyclohexanone-order4.at)
    6363
     64# fragmentation of anthracene
     65m4_include(Fragmenting/anthracene/testsuite-fragmenting-anthracene-order1.at)
     66m4_include(Fragmenting/anthracene/testsuite-fragmenting-anthracene-order2.at)
     67m4_include(Fragmenting/anthracene/testsuite-fragmenting-anthracene-order3.at)
     68m4_include(Fragmenting/anthracene/testsuite-fragmenting-anthracene-order4.at)
     69m4_include(Fragmenting/anthracene/testsuite-fragmenting-anthracene-order5.at)
     70m4_include(Fragmenting/anthracene/testsuite-fragmenting-anthracene-order6.at)
     71
    6472# fragmentation of benzene
    6573m4_include(Fragmenting/benzene/testsuite-fragmenting-benzene-order1.at)
    … …  
    7583m4_include(Fragmenting/cholesterol/testsuite-fragmenting-cholesterol-order3.at)
    7684m4_include(Fragmenting/cholesterol/testsuite-fragmenting-cholesterol-order4.at)
     85
     86# fragmentation of coronene
     87m4_include(Fragmenting/coronene/testsuite-fragmenting-coronene-order1.at)
     88m4_include(Fragmenting/coronene/testsuite-fragmenting-coronene-order2.at)
     89m4_include(Fragmenting/coronene/testsuite-fragmenting-coronene-order3.at)
     90m4_include(Fragmenting/coronene/testsuite-fragmenting-coronene-order4.at)
     91m4_include(Fragmenting/coronene/testsuite-fragmenting-coronene-order5.at)
     92m4_include(Fragmenting/coronene/testsuite-fragmenting-coronene-order6.at)
    7793
    7894# fragmentation of cycloheptane
    … …  
    114130m4_include(Fragmenting/isoleucine/testsuite-fragmenting-isoleucine-order6.at)
    115131
     132# fragmentation of naphthalene
     133m4_include(Fragmenting/naphthalene/testsuite-fragmenting-naphthalene-order1.at)
     134m4_include(Fragmenting/naphthalene/testsuite-fragmenting-naphthalene-order2.at)
     135m4_include(Fragmenting/naphthalene/testsuite-fragmenting-naphthalene-order3.at)
     136m4_include(Fragmenting/naphthalene/testsuite-fragmenting-naphthalene-order4.at)
     137m4_include(Fragmenting/naphthalene/testsuite-fragmenting-naphthalene-order5.at)
     138m4_include(Fragmenting/naphthalene/testsuite-fragmenting-naphthalene-order6.at)
     139
    116140# fragmentation of neohexane
    117141m4_include(Fragmenting/neohexane/testsuite-fragmenting-neohexane-order1.at)
    … …  
    129153m4_include(Fragmenting/N_N-dimethylacetamide/testsuite-fragmenting-N_N-dimethylacetamide-order5.at)
    130154m4_include(Fragmenting/N_N-dimethylacetamide/testsuite-fragmenting-N_N-dimethylacetamide-order6.at)
     155
     156# fragmentation of phenanthrene
     157m4_include(Fragmenting/phenanthrene/testsuite-fragmenting-phenanthrene-order1.at)
     158m4_include(Fragmenting/phenanthrene/testsuite-fragmenting-phenanthrene-order2.at)
     159m4_include(Fragmenting/phenanthrene/testsuite-fragmenting-phenanthrene-order3.at)
     160m4_include(Fragmenting/phenanthrene/testsuite-fragmenting-phenanthrene-order4.at)
     161m4_include(Fragmenting/phenanthrene/testsuite-fragmenting-phenanthrene-order5.at)
     162m4_include(Fragmenting/phenanthrene/testsuite-fragmenting-phenanthrene-order6.at)
    131163
    132164# fragmentation of proline
Note: See TracChangeset for help on using the changeset viewer.