Changeset 174e0e


Ignore:
Timestamp:
Oct 18, 2009, 3:13:46 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:
ef9aae
Parents:
266237
Message:

Refactored molecule::DepthFirstSearchAnalysis()

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/molecule_graph.cpp

    r266237 r174e0e  
    252252};
    253253
     254void SetWalkersGraphNr(ofstream *out, bool &BackStepping, atom *&Walker, int &CurrentGraphNr, class StackClass<atom *> *&AtomStack)
     255{
     256  if (!BackStepping) { // if we don't just return from (8)
     257    Walker->GraphNr = CurrentGraphNr;
     258    Walker->LowpointNr = CurrentGraphNr;
     259    *out << Verbose(1) << "Setting Walker[" << Walker->Name << "]'s number to " << Walker->GraphNr << " with Lowpoint " << Walker->LowpointNr << "." << endl;
     260    AtomStack->Push(Walker);
     261    CurrentGraphNr++;
     262  }
     263};
     264
     265void ProbeAlongUnusedBond(ofstream *out, molecule *mol, bond *&Binder, bool &BackStepping, atom *&Walker, class StackClass<bond *> *&BackEdgeStack)
     266{
     267  atom *OtherAtom = NULL;
     268
     269  do { // (3) if Walker has no unused egdes, go to (5)
     270    BackStepping = false; // reset backstepping flag for (8)
     271    if (Binder == NULL) // if we don't just return from (11), Binder is already set to next unused
     272      Binder = mol->FindNextUnused(Walker);
     273    if (Binder == NULL)
     274      break;
     275    *out << Verbose(2) << "Current Unused Bond is " << *Binder << "." << endl;
     276    // (4) Mark Binder used, ...
     277    Binder->MarkUsed(black);
     278    OtherAtom = Binder->GetOtherAtom(Walker);
     279    *out << Verbose(2) << "(4) OtherAtom is " << OtherAtom->Name << "." << endl;
     280    if (OtherAtom->GraphNr != -1) {
     281      // (4a) ... if "other" atom has been visited (GraphNr != 0), set lowpoint to minimum of both, go to (3)
     282      Binder->Type = BackEdge;
     283      BackEdgeStack->Push(Binder);
     284      Walker->LowpointNr = ( Walker->LowpointNr < OtherAtom->GraphNr ) ? Walker->LowpointNr : OtherAtom->GraphNr;
     285      *out << Verbose(3) << "(4a) Visited: Setting Lowpoint of Walker[" << Walker->Name << "] to " << Walker->LowpointNr << "." << endl;
     286    } else {
     287      // (4b) ... otherwise set OtherAtom as Ancestor of Walker and Walker as OtherAtom, go to (2)
     288      Binder->Type = TreeEdge;
     289      OtherAtom->Ancestor = Walker;
     290      Walker = OtherAtom;
     291      *out << Verbose(3) << "(4b) Not Visited: OtherAtom[" << OtherAtom->Name << "]'s Ancestor is now " << OtherAtom->Ancestor->Name << ", Walker is OtherAtom " << OtherAtom->Name << "." << endl;
     292      break;
     293    }
     294    Binder = NULL;
     295  } while (1);  // (3)
     296};
     297
     298void CheckForaNewComponent(ofstream *out, molecule *mol, bool &BackStepping, atom *&Walker, atom *&Root, int &ComponentNumber, class StackClass<atom *> *&AtomStack, MoleculeLeafClass *&LeafWalker )
     299{
     300  atom *OtherAtom = NULL;
     301
     302  // (5) if Ancestor of Walker is ...
     303  *out << Verbose(1) << "(5) Number of Walker[" << Walker->Name << "]'s Ancestor[" << Walker->Ancestor->Name << "] is " << Walker->Ancestor->GraphNr << "." << endl;
     304
     305  if (Walker->Ancestor->GraphNr != Root->GraphNr) {
     306    // (6)  (Ancestor of Walker is not Root)
     307    if (Walker->LowpointNr < Walker->Ancestor->GraphNr) {
     308      // (6a) set Ancestor's Lowpoint number to minimum of of its Ancestor and itself, go to Step(8)
     309      Walker->Ancestor->LowpointNr = (Walker->Ancestor->LowpointNr < Walker->LowpointNr) ? Walker->Ancestor->LowpointNr : Walker->LowpointNr;
     310      *out << Verbose(2) << "(6) Setting Walker[" << Walker->Name << "]'s Ancestor[" << Walker->Ancestor->Name << "]'s Lowpoint to " << Walker->Ancestor->LowpointNr << "." << endl;
     311    } else {
     312      // (7) (Ancestor of Walker is a separating vertex, remove all from stack till Walker (including), these and Ancestor form a component
     313      Walker->Ancestor->SeparationVertex = true;
     314      *out << Verbose(2) << "(7) Walker[" << Walker->Name << "]'s Ancestor[" << Walker->Ancestor->Name << "]'s is a separating vertex, creating component." << endl;
     315      mol->SetNextComponentNumber(Walker->Ancestor, ComponentNumber);
     316      *out << Verbose(3) << "(7) Walker[" << Walker->Name << "]'s Ancestor's Compont is " << ComponentNumber << "." << endl;
     317      mol->SetNextComponentNumber(Walker, ComponentNumber);
     318      *out << Verbose(3) << "(7) Walker[" << Walker->Name << "]'s Compont is " << ComponentNumber << "." << endl;
     319      do {
     320        OtherAtom = AtomStack->PopLast();
     321        LeafWalker->Leaf->AddCopyAtom(OtherAtom);
     322        mol->SetNextComponentNumber(OtherAtom, ComponentNumber);
     323        *out << Verbose(3) << "(7) Other[" << OtherAtom->Name << "]'s Compont is " << ComponentNumber << "." << endl;
     324      } while (OtherAtom != Walker);
     325      ComponentNumber++;
     326    }
     327    // (8) Walker becomes its Ancestor, go to (3)
     328    *out << Verbose(2) << "(8) Walker[" << Walker->Name << "] is now its Ancestor " << Walker->Ancestor->Name << ", backstepping. " << endl;
     329    Walker = Walker->Ancestor;
     330    BackStepping = true;
     331  }
     332};
     333
     334void CleanRootStackDownTillWalker(ofstream *out, molecule *mol, bool &BackStepping, atom *&Root, atom *&Walker, bond *&Binder, int &ComponentNumber, class StackClass<atom *> *&AtomStack, MoleculeLeafClass *&LeafWalker)
     335{
     336  atom *OtherAtom = NULL;
     337
     338  if (!BackStepping) {  // coming from (8) want to go to (3)
     339    // (9) remove all from stack till Walker (including), these and Root form a component
     340    AtomStack->Output(out);
     341    mol->SetNextComponentNumber(Root, ComponentNumber);
     342    *out << Verbose(3) << "(9) Root[" << Root->Name << "]'s Component is " << ComponentNumber << "." << endl;
     343    mol->SetNextComponentNumber(Walker, ComponentNumber);
     344    *out << Verbose(3) << "(9) Walker[" << Walker->Name << "]'s Component is " << ComponentNumber << "." << endl;
     345    do {
     346      OtherAtom = AtomStack->PopLast();
     347      LeafWalker->Leaf->AddCopyAtom(OtherAtom);
     348      mol->SetNextComponentNumber(OtherAtom, ComponentNumber);
     349      *out << Verbose(3) << "(7) Other[" << OtherAtom->Name << "]'s Compont is " << ComponentNumber << "." << endl;
     350    } while (OtherAtom != Walker);
     351    ComponentNumber++;
     352
     353    // (11) Root is separation vertex,  set Walker to Root and go to (4)
     354    Walker = Root;
     355    Binder = mol->FindNextUnused(Walker);
     356    *out << Verbose(1) << "(10) Walker is Root[" << Root->Name << "], next Unused Bond is " << Binder << "." << endl;
     357    if (Binder != NULL) { // Root is separation vertex
     358      *out << Verbose(1) << "(11) Root is a separation vertex." << endl;
     359      Walker->SeparationVertex = true;
     360    }
     361  }
     362};
     363
     364
    254365/** Performs a Depth-First search on this molecule.
    255366 * Marks bonds in molecule as cyclic, bridge, ... and atoms as
    … …  
    268379  int CurrentGraphNr = 0, OldGraphNr;
    269380  int ComponentNumber = 0;
    270   atom *Walker = NULL, *OtherAtom = NULL, *Root = start->next;
     381  atom *Walker = NULL;
     382  atom *Root = start->next;
    271383  bond *Binder = NULL;
    272384  bool BackStepping = false;
    … …  
    291403    do { // (10)
    292404      do { // (2) set number and Lowpoint of Atom to i, increase i, push current atom
    293         if (!BackStepping) { // if we don't just return from (8)
    294           Walker->GraphNr = CurrentGraphNr;
    295           Walker->LowpointNr = CurrentGraphNr;
    296           *out << Verbose(1) << "Setting Walker[" << Walker->Name << "]'s number to " << Walker->GraphNr << " with Lowpoint " << Walker->LowpointNr << "." << endl;
    297           AtomStack->Push(Walker);
    298           CurrentGraphNr++;
    299         }
    300         do { // (3) if Walker has no unused egdes, go to (5)
    301           BackStepping = false; // reset backstepping flag for (8)
    302           if (Binder == NULL) // if we don't just return from (11), Binder is already set to next unused
    303             Binder = FindNextUnused(Walker);
    304           if (Binder == NULL)
    305             break;
    306           *out << Verbose(2) << "Current Unused Bond is " << *Binder << "." << endl;
    307           // (4) Mark Binder used, ...
    308           Binder->MarkUsed(black);
    309           OtherAtom = Binder->GetOtherAtom(Walker);
    310           *out << Verbose(2) << "(4) OtherAtom is " << OtherAtom->Name << "." << endl;
    311           if (OtherAtom->GraphNr != -1) {
    312             // (4a) ... if "other" atom has been visited (GraphNr != 0), set lowpoint to minimum of both, go to (3)
    313             Binder->Type = BackEdge;
    314             BackEdgeStack->Push(Binder);
    315             Walker->LowpointNr = ( Walker->LowpointNr < OtherAtom->GraphNr ) ? Walker->LowpointNr : OtherAtom->GraphNr;
    316             *out << Verbose(3) << "(4a) Visited: Setting Lowpoint of Walker[" << Walker->Name << "] to " << Walker->LowpointNr << "." << endl;
    317           } else {
    318             // (4b) ... otherwise set OtherAtom as Ancestor of Walker and Walker as OtherAtom, go to (2)
    319             Binder->Type = TreeEdge;
    320             OtherAtom->Ancestor = Walker;
    321             Walker = OtherAtom;
    322             *out << Verbose(3) << "(4b) Not Visited: OtherAtom[" << OtherAtom->Name << "]'s Ancestor is now " << OtherAtom->Ancestor->Name << ", Walker is OtherAtom " << OtherAtom->Name << "." << endl;
    323             break;
    324           }
    325           Binder = NULL;
    326         } while (1);  // (3)
     405        SetWalkersGraphNr(out, BackStepping, Walker, CurrentGraphNr, AtomStack);
     406
     407        ProbeAlongUnusedBond(out, this, Binder, BackStepping, Walker, BackEdgeStack);
     408
    327409        if (Binder == NULL) {
    328410          *out << Verbose(2) << "No more Unused Bonds." << endl;
    … …  
    336418        break;
    337419
    338       // (5) if Ancestor of Walker is ...
    339       *out << Verbose(1) << "(5) Number of Walker[" << Walker->Name << "]'s Ancestor[" << Walker->Ancestor->Name << "] is " << Walker->Ancestor->GraphNr << "." << endl;
    340       if (Walker->Ancestor->GraphNr != Root->GraphNr) {
    341         // (6)  (Ancestor of Walker is not Root)
    342         if (Walker->LowpointNr < Walker->Ancestor->GraphNr) {
    343           // (6a) set Ancestor's Lowpoint number to minimum of of its Ancestor and itself, go to Step(8)
    344           Walker->Ancestor->LowpointNr = (Walker->Ancestor->LowpointNr < Walker->LowpointNr) ? Walker->Ancestor->LowpointNr : Walker->LowpointNr;
    345           *out << Verbose(2) << "(6) Setting Walker[" << Walker->Name << "]'s Ancestor[" << Walker->Ancestor->Name << "]'s Lowpoint to " << Walker->Ancestor->LowpointNr << "." << endl;
    346         } else {
    347           // (7) (Ancestor of Walker is a separating vertex, remove all from stack till Walker (including), these and Ancestor form a component
    348           Walker->Ancestor->SeparationVertex = true;
    349           *out << Verbose(2) << "(7) Walker[" << Walker->Name << "]'s Ancestor[" << Walker->Ancestor->Name << "]'s is a separating vertex, creating component." << endl;
    350           SetNextComponentNumber(Walker->Ancestor, ComponentNumber);
    351           *out << Verbose(3) << "(7) Walker[" << Walker->Name << "]'s Ancestor's Compont is " << ComponentNumber << "." << endl;
    352           SetNextComponentNumber(Walker, ComponentNumber);
    353           *out << Verbose(3) << "(7) Walker[" << Walker->Name << "]'s Compont is " << ComponentNumber << "." << endl;
    354           do {
    355             OtherAtom = AtomStack->PopLast();
    356             LeafWalker->Leaf->AddCopyAtom(OtherAtom);
    357             SetNextComponentNumber(OtherAtom, ComponentNumber);
    358             *out << Verbose(3) << "(7) Other[" << OtherAtom->Name << "]'s Compont is " << ComponentNumber << "." << endl;
    359           } while (OtherAtom != Walker);
    360           ComponentNumber++;
    361         }
    362         // (8) Walker becomes its Ancestor, go to (3)
    363         *out << Verbose(2) << "(8) Walker[" << Walker->Name << "] is now its Ancestor " << Walker->Ancestor->Name << ", backstepping. " << endl;
    364         Walker = Walker->Ancestor;
    365         BackStepping = true;
    366       }
    367       if (!BackStepping) {  // coming from (8) want to go to (3)
    368         // (9) remove all from stack till Walker (including), these and Root form a component
    369         AtomStack->Output(out);
    370         SetNextComponentNumber(Root, ComponentNumber);
    371         *out << Verbose(3) << "(9) Root[" << Root->Name << "]'s Component is " << ComponentNumber << "." << endl;
    372         SetNextComponentNumber(Walker, ComponentNumber);
    373         *out << Verbose(3) << "(9) Walker[" << Walker->Name << "]'s Component is " << ComponentNumber << "." << endl;
    374         do {
    375           OtherAtom = AtomStack->PopLast();
    376           LeafWalker->Leaf->AddCopyAtom(OtherAtom);
    377           SetNextComponentNumber(OtherAtom, ComponentNumber);
    378           *out << Verbose(3) << "(7) Other[" << OtherAtom->Name << "]'s Compont is " << ComponentNumber << "." << endl;
    379         } while (OtherAtom != Walker);
    380         ComponentNumber++;
    381 
    382         // (11) Root is separation vertex,  set Walker to Root and go to (4)
    383         Walker = Root;
    384         Binder = FindNextUnused(Walker);
    385         *out << Verbose(1) << "(10) Walker is Root[" << Root->Name << "], next Unused Bond is " << Binder << "." << endl;
    386         if (Binder != NULL) { // Root is separation vertex
    387           *out << Verbose(1) << "(11) Root is a separation vertex." << endl;
    388           Walker->SeparationVertex = true;
    389         }
    390       }
     420      CheckForaNewComponent(out, this, BackStepping, Walker, Root,ComponentNumber, AtomStack, LeafWalker );
     421
     422      CleanRootStackDownTillWalker(out, this, BackStepping, Root, Walker, Binder, ComponentNumber, AtomStack, LeafWalker);
     423
    391424    } while ((BackStepping) || (Binder != NULL)); // (10) halt only if Root has no unused edges
    392425
Note: See TracChangeset for help on using the changeset viewer.