Changeset f67817f

Timestamp:

Oct 25, 2011, 12:08:03 PM (13 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:

d0b375b

Parents:

23fb72

git-author:

Frederik Heber <heber@…> (10/18/11 12:26:01)

git-committer:

Frederik Heber <heber@…> (10/25/11 12:08:03)

Message:

Extracted power set generation into own class PowerSetGenerator.

Location:

src

Files:

• Fragmentation/Makefile.am (modified) (2 diffs)
• Fragmentation/PowerSetGenerator.cpp (added)
• Fragmentation/PowerSetGenerator.hpp (added)
• Fragmentation/fragmentation_helpers.cpp (modified) (1 diff)
• Fragmentation/fragmentation_helpers.hpp (modified) (1 diff)
• molecule.hpp (modified) (1 diff)
• molecule_fragmentation.cpp (modified) (4 diffs)

src/Fragmentation/Makefile.am

@@ -10 +10 @@
         Fragmentation/KeySetsContainer.cpp \
         Fragmentation/MatrixContainer.cpp \
+        Fragmentation/PowerSetGenerator.cpp \
         Fragmentation/UniqueFragments.cpp
 
@@ -15 +16 @@
         Fragmentation/defs.hpp \
         Fragmentation/EnergyMatrix.hpp \
+        Fragmentation/ForceMatrix.hpp \
         Fragmentation/fragmentation_helpers.hpp \
-        Fragmentation/ForceMatrix.hpp \
         Fragmentation/helpers.hpp \
         Fragmentation/HessianMatrix.hpp \
         Fragmentation/KeySetsContainer.hpp \
         Fragmentation/MatrixContainer.hpp \
+        Fragmentation/PowerSetGenerator.hpp \
         Fragmentation/UniqueFragments.hpp
 

src/Fragmentation/fragmentation_helpers.cpp

@@ -426 +426 @@
 
 
-/** Clears the touched list
- * \param *out output stream for debugging
- * \param verbosity verbosity level
- * \param *&TouchedList touched list
- * \param SubOrder current suborder
- * \param TouchedIndex currently touched
- */
-void SPFragmentGenerator_ClearingTouched(int verbosity, int *&TouchedList, int SubOrder, int &TouchedIndex)
-{
-  Log() << Verbose(1+verbosity) << "Clearing touched list." << endl;
-  for (TouchedIndex=SubOrder+1;TouchedIndex--;)  // empty touched list
-    TouchedList[TouchedIndex] = -1;
-  TouchedIndex = 0;
-
-}
-
-/** Adds the current combination of the power set to the snake stack.
- * \param *out output stream for debugging
- * \param verbosity verbosity level
- * \param CurrentCombination
- * \param SetDimension maximum number of bits in power set
- * \param *FragmentSet snake stack to remove from
- * \param &BondsSet set of bonds
- * \param *&TouchedList touched list
- * \param TouchedIndex currently touched
- * \return number of set bits
- */
-int AddPowersetToSnakeStack(int verbosity, int CurrentCombination, int SetDimension, KeySet *FragmentSet, std::vector<bond *> &BondsSet, int *&TouchedList, int &TouchedIndex)
-{
-  atom *OtherWalker = NULL;
-  bool bit = false;
-  KeySetTestPair TestKeySetInsert;
-
-  int Added = 0;
-  for (int j=0;j<SetDimension;j++) {  // pull out every bit by shifting
-    bit = ((CurrentCombination & (1 << j)) != 0);  // mask the bit for the j-th bond
-    if (bit) {  // if bit is set, we add this bond partner
-      OtherWalker = BondsSet[j]->rightatom;  // rightatom is always the one more distant, i.e. the one to add
-      //Log() << Verbose(1+verbosity) << "Current Bond is " << BondsSet[j] << ", checking on " << *OtherWalker << "." << endl;
-      Log() << Verbose(2+verbosity) << "Adding " << *OtherWalker << " with nr " << OtherWalker->getNr() << "." << endl;
-      TestKeySetInsert = FragmentSet->insert(OtherWalker->getNr());
-      if (TestKeySetInsert.second) {
-        TouchedList[TouchedIndex++] = OtherWalker->getNr();  // note as added
-        Added++;
-      } else {
-        Log() << Verbose(2+verbosity) << "This was item was already present in the keyset." << endl;
-      }
-    } else {
-      Log() << Verbose(2+verbosity) << "Not adding." << endl;
-    }
-  }
-  return Added;
-};
-
-/** Counts the number of elements in a power set.
- * \param SetFirst begin iterator first bond
- * \param SetLast end iterator
- * \param *&TouchedList touched list
- * \param TouchedIndex currently touched
- * \return number of elements
- */
-int CountSetMembers(std::list<bond *>::const_iterator SetFirst, std::list<bond *>::const_iterator SetLast, int *&TouchedList, int TouchedIndex)
-{
-  int SetDimension = 0;
-  for( std::list<bond *>::const_iterator Binder = SetFirst;
-      Binder != SetLast;
-      ++Binder) {
-    for (int k=TouchedIndex;k--;) {
-      if ((*Binder)->Contains(TouchedList[k]))   // if we added this very endpiece
-        SetDimension++;
-    }
-  }
-  return SetDimension;
-};
-
-/** Fills a list of bonds from another
- * \param *BondsList bonds array/vector to fill
- * \param SetFirst begin iterator first bond
- * \param SetLast end iterator
- * \param *&TouchedList touched list
- * \param TouchedIndex currently touched
- * \return number of elements
- */
-int FillBondsList(std::vector<bond *> &BondsList, std::list<bond *>::const_iterator SetFirst, std::list<bond *>::const_iterator SetLast, int *&TouchedList, int TouchedIndex)
-{
-  int SetDimension = 0;
-  for( std::list<bond *>::const_iterator Binder = SetFirst;
-      Binder != SetLast;
-      ++Binder) {
-    for (int k=0;k<TouchedIndex;k++) {
-      if ((*Binder)->leftatom->getNr() == TouchedList[k])   // leftatom is always the closer one
-        BondsList[SetDimension++] = (*Binder);
-    }
-  }
-  return SetDimension;
-};
-
-/** Remove all items that were added on this SP level.
- * \param *out output stream for debugging
- * \param verbosity verbosity level
- * \param *FragmentSet snake stack to remove from
- * \param *&TouchedList touched list
- * \param TouchedIndex currently touched
- */
-void RemoveAllTouchedFromSnakeStack(int verbosity, KeySet *FragmentSet, int *&TouchedList, int &TouchedIndex)
-{
-  int Removal = 0;
-  for(int j=0;j<TouchedIndex;j++) {
-    Removal = TouchedList[j];
-    Log() << Verbose(2+verbosity) << "Removing item nr. " << Removal << " from snake stack." << endl;
-    FragmentSet->erase(Removal);
-    TouchedList[j] = -1;
-  }
-  DoLog(2) && (Log() << Verbose(2) << "Remaining local nr.s on snake stack are: ");
-  for(KeySet::iterator runner = FragmentSet->begin(); runner != FragmentSet->end(); runner++)
-    DoLog(0) && (Log() << Verbose(0) << (*runner) << " ");
-  DoLog(0) && (Log() << Verbose(0) << endl);
-  TouchedIndex = 0; // set Index to 0 for list of atoms added on this level
-};
-
-
 bool KeyCompare::operator() (const KeySet SubgraphA, const KeySet SubgraphB) const
 {

src/Fragmentation/fragmentation_helpers.hpp

@@ -36 +36 @@
 bool MarkUpdateCandidates(bool *AtomMask, std::map<double, std::pair<int,int> > &FinalRootCandidates, int Order, molecule *mol);
 void PrintAtomMask(bool *AtomMask, int AtomCount);
-void SPFragmentGenerator_ClearingTouched(int verbosity, int *&TouchedList, int SubOrder, int &TouchedIndex);
-int AddPowersetToSnakeStack(int verbosity, int CurrentCombination, int SetDimension, KeySet *FragmentSet, std::vector<bond *> &BondsSet, int *&TouchedList, int &TouchedIndex);
-int CountSetMembers(std::list<bond *>::const_iterator SetFirst, std::list<bond *>::const_iterator SetLast, int *&TouchedList, int TouchedIndex);
-int FillBondsList(std::vector<bond *> &BondsList, std::list<bond *>::const_iterator SetFirst, std::list<bond *>::const_iterator SetLast, int *&TouchedList, int TouchedIndex);
-void RemoveAllTouchedFromSnakeStack(int verbosity, KeySet *FragmentSet, int *&TouchedList, int &TouchedIndex);
 
 int CombineAllOrderListIntoOne(Graph *&FragmentList, Graph ***FragmentLowerOrdersList, KeyStack &RootStack, molecule *mol);

src/molecule.hpp

@@ -224 +224 @@
   /// -# BOSSANOVA
   void FragmentBOSSANOVA(Graph *&FragmentList, KeyStack &RootStack);
-  int PowerSetGenerator(int Order, struct UniqueFragments &FragmentSearch, KeySet RestrictedKeySet);
   molecule * StoreFragmentFromKeySet(KeySet &Leaflet, bool IsAngstroem);
-  void SPFragmentGenerator(struct UniqueFragments *FragmentSearch, int RootDistance, std::vector<bond *> &BondsSet, int SetDimension, int SubOrder);
   int LookForRemovalCandidate(KeySet *&Leaf, int *&ShortestPathList);
   int GuesstimateFragmentCount(int order);

src/molecule_fragmentation.cpp

@@ -31 +31 @@
 #include "Element/periodentafel.hpp"
 #include "Fragmentation/fragmentation_helpers.hpp"
+#include "Fragmentation/PowerSetGenerator.hpp"
 #include "Fragmentation/UniqueFragments.hpp"
 #include "Graph/BondGraph.hpp"
@@ -658 +659 @@
 };
 
-/** From a given set of Bond sorted by Shortest Path distance, create all possible fragments of size \a SetDimension.
- * -# loops over every possible combination (2^dimension of edge set)
- *  -# inserts current set, if there's still space left
- *    -# yes: calls SPFragmentGenerator with structure, created new edge list and size respective to root dist
-ance+1
- *    -# no: stores fragment into keyset list by calling InsertFragmentIntoGraph
- *  -# removes all items added into the snake stack (in UniqueFragments structure) added during level (root
-distance) and current set
- * \param FragmentSearch UniqueFragments structure with all values needed
- * \param RootDistance current shortest path level, whose set of edges is represented by **BondsSet
- * \param BondsSet array of bonds to check
- * \param SetDimension Number of possible bonds on this level (i.e. size of the array BondsSet[])
- * \param SubOrder remaining number of allowed vertices to add
- */
-void molecule::SPFragmentGenerator(struct UniqueFragments *FragmentSearch, int RootDistance, std::vector<bond *> &BondsSet, int SetDimension, int SubOrder)
-{
-  int verbosity = 0; //FragmentSearch->ANOVAOrder-SubOrder;
-  int NumCombinations;
-  int bits, TouchedIndex, SubSetDimension, SP, Added;
-  int SpaceLeft;
-  int *TouchedList = new int[SubOrder + 1];
-  KeySetTestPair TestKeySetInsert;
-
-  NumCombinations = 1 << SetDimension;
-
-  // here for all bonds of Walker all combinations of end pieces (from the bonds)
-  // have to be added and for the remaining ANOVA order GraphCrawler be called
-  // recursively for the next level
-
-  Log() << Verbose(1+verbosity) << "Begin of SPFragmentGenerator." << endl;
-  Log() << Verbose(1+verbosity) << "We are " << RootDistance << " away from Root, which is " << *FragmentSearch->getRoot() << ", SubOrder is " << SubOrder << ", SetDimension is " << SetDimension << " and this means " <<  NumCombinations-1 << " combination(s)." << endl;
-
-  // initialised touched list (stores added atoms on this level)
-  SPFragmentGenerator_ClearingTouched(verbosity, TouchedList, SubOrder, TouchedIndex);
-
-  // create every possible combination of the endpieces
-  Log() << Verbose(1+verbosity) << "Going through all combinations of the power set." << endl;
-  for (int i=1;i<NumCombinations;i++) {  // sweep through all power set combinations (skip empty set!)
-    // count the set bit of i
-    bits = 0;
-    for (int j=SetDimension;j--;)
-      bits += (i & (1 << j)) >> j;
-
-    Log() << Verbose(1+verbosity) << "Current set is " << Binary(i | (1 << SetDimension)) << ", number of bits is " << bits << "." << endl;
-    if (bits <= SubOrder) { // if not greater than additional atoms allowed on stack, continue
-      // --1-- add this set of the power set of bond partners to the snake stack
-      Added = AddPowersetToSnakeStack(verbosity, i, SetDimension, FragmentSearch->FragmentSet, BondsSet, TouchedList, TouchedIndex);
-
-      SpaceLeft = SubOrder - Added ;// SubOrder - bits; // due to item's maybe being already present, this does not work anymore
-      if (SpaceLeft > 0) {
-        Log() << Verbose(1+verbosity) << "There's still some space left on stack: " << SpaceLeft << "." << endl;
-        if (SubOrder > 1) {    // Due to Added above we have to check extra whether we're not already reaching beyond the desired Order
-          // --2-- look at all added end pieces of this combination, construct bond subsets and sweep through a power set of these by recursion
-          SP = RootDistance+1;  // this is the next level
-
-          // first count the members in the subset
-          SubSetDimension = CountSetMembers(FragmentSearch->BondsPerSPList[SP].begin(), FragmentSearch->BondsPerSPList[SP].end(), TouchedList, TouchedIndex);
-
-          // then allocate and fill the list
-          std::vector<bond *> BondsList;
-          BondsList.resize(SubSetDimension);
-          SubSetDimension = FillBondsList(BondsList, FragmentSearch->BondsPerSPList[SP].begin(), FragmentSearch->BondsPerSPList[SP].end(), TouchedList, TouchedIndex);
-
-          // then iterate
-          Log() << Verbose(2+verbosity) << "Calling subset generator " << SP << " away from root " << *FragmentSearch->getRoot() << " with sub set dimension " << SubSetDimension << "." << endl;
-          SPFragmentGenerator(FragmentSearch, SP, BondsList, SubSetDimension, SubOrder-bits);
-        }
-      } else {
-        // --2-- otherwise store the complete fragment
-        Log() << Verbose(1+verbosity) << "Enough items on stack for a fragment!" << endl;
-        // store fragment as a KeySet
-        DoLog(2) && (Log() << Verbose(2) << "Found a new fragment[" << FragmentSearch->FragmentCounter << "], local nr.s are: ");
-        for(KeySet::iterator runner = FragmentSearch->FragmentSet->begin(); runner != FragmentSearch->FragmentSet->end(); runner++)
-          DoLog(0) && (Log() << Verbose(0) << (*runner) << " ");
-        DoLog(0) && (Log() << Verbose(0) << endl);
-        FragmentSearch->InsertFragmentIntoGraph();
-      }
-
-      // --3-- remove all added items in this level from snake stack
-      Log() << Verbose(1+verbosity) << "Removing all items that were added on this SP level " << RootDistance << "." << endl;
-      RemoveAllTouchedFromSnakeStack(verbosity, FragmentSearch->FragmentSet, TouchedList, TouchedIndex);
-    } else {
-      Log() << Verbose(2+verbosity) << "More atoms to add for this set (" << bits << ") than space left on stack " << SubOrder << ", skipping this set." << endl;
-    }
-  }
-  delete[](TouchedList);
-  Log() << Verbose(1+verbosity) << "End of SPFragmentGenerator, " << RootDistance << " away from Root " << *FragmentSearch->getRoot() << " and SubOrder is " << SubOrder << "." << endl;
-};
-
-
-/** Creates a list of all unique fragments of certain vertex size from a given graph \a Fragment for a given root vertex in the context of \a this molecule.
- * -# initialises UniqueFragments structure
- * -# fills edge list via BFS
- * -# creates the fragment by calling recursive function SPFragmentGenerator with UniqueFragments structure, 0 as
- root distance, the edge set, its dimension and the current suborder
- * -# Free'ing structure
- * Note that we may use the fact that the atoms are SP-ordered on the atomstack. I.e. when popping always the last, we first get all
- * with SP of 2, then those with SP of 3, then those with SP of 4 and so on.
- * \param *out output stream for debugging
- * \param Order bond order (limits BFS exploration and "number of digits" in power set generation
- * \param FragmentSearch UniqueFragments structure containing TEFactor, root atom and so on
- * \param RestrictedKeySet Restricted vertex set to use in context of molecule
- * \return number of inserted fragments
- * \note ShortestPathList in FragmentSearch structure is probably due to NumberOfAtomsSPLevel and SP not needed anymore
- */
-int molecule::PowerSetGenerator(int Order, struct UniqueFragments &FragmentSearch, KeySet RestrictedKeySet)
-{
-  int Counter = FragmentSearch.FragmentCounter; // mark current value of counter
-
-  DoLog(0) && (Log() << Verbose(0) << endl);
-  DoLog(0) && (Log() << Verbose(0) << "Begin of PowerSetGenerator with order " << Order << " at Root " << *FragmentSearch.getRoot() << "." << endl);
-
-  FragmentSearch.SetSPList(Order);
-
-  // do a BFS search to fill the SP lists and label the found vertices
-  FragmentSearch.FillSPListandLabelVertices(Order, RestrictedKeySet);
-
-  // outputting all list for debugging
-  FragmentSearch.OutputSPList(Order);
-
-  // creating fragments with the found edge sets  (may be done in reverse order, faster)
-  int SP = FragmentSearch.CountNumbersInBondsList(Order);
-  DoLog(0) && (Log() << Verbose(0) << "Total number of edges is " << SP << "." << endl);
-  if (SP >= (Order-1)) {
-    // start with root (push on fragment stack)
-    DoLog(0) && (Log() << Verbose(0) << "Starting fragment generation with " << *FragmentSearch.getRoot() << ", local nr is " << FragmentSearch.getRoot()->getNr() << "." << endl);
-    FragmentSearch.FragmentSet->clear();
-    DoLog(0) && (Log() << Verbose(0) << "Preparing subset for this root and calling generator." << endl);
-
-    // prepare the subset and call the generator
-    std::vector<bond*> BondsList;
-    BondsList.resize(FragmentSearch.BondsPerSPCount[0]);
-    ASSERT(FragmentSearch.BondsPerSPList[0].size() != 0,
-        "molecule::PowerSetGenerator() - FragmentSearch.BondsPerSPList[0] contains no root bond.");
-    BondsList[0] = (*FragmentSearch.BondsPerSPList[0].begin());  // on SP level 0 there's only the root bond
-
-    SPFragmentGenerator(&FragmentSearch, 0, BondsList, FragmentSearch.BondsPerSPCount[0], Order);
-  } else {
-    DoLog(0) && (Log() << Verbose(0) << "Not enough total number of edges to build " << Order << "-body fragments." << endl);
-  }
-
-  // as FragmentSearch structure is used only once, we don't have to clean it anymore
-  // remove root from stack
-  DoLog(0) && (Log() << Verbose(0) << "Removing root again from stack." << endl);
-  FragmentSearch.FragmentSet->erase(FragmentSearch.getRoot()->getNr());
-
-  // free'ing the bonds lists
-  FragmentSearch.ResetSPList(Order);
-
-  // return list
-  DoLog(0) && (Log() << Verbose(0) << "End of PowerSetGenerator." << endl);
-  return (FragmentSearch.FragmentCounter - Counter);
-};
-
-
-
-
 /** Performs BOSSANOVA decomposition at selected sites, increasing the cutoff by one at these sites.
  * -# constructs a complete keyset of the molecule
@@ -844 +688 @@
   int RootNr = 0;
   struct UniqueFragments FragmentSearch;
+  class PowerSetGenerator PSG;
 
   DoLog(0) && (Log() << Verbose(0) << "Begin of FragmentBOSSANOVA." << endl);
@@ -901 +746 @@
       FragmentSearch.Leaflet = FragmentLowerOrdersList[RootNr][0];      // set to insertion graph
       FragmentSearch.setRoot(Walker);
-      NumMoleculesOfOrder[RootNr] = PowerSetGenerator(Walker->AdaptiveOrder, FragmentSearch, CompleteMolecule);
+      NumMoleculesOfOrder[RootNr] = PSG(&FragmentSearch, Walker->AdaptiveOrder, CompleteMolecule);
 
       // output resulting number