Changeset ef9aae
- Timestamp:
- Oct 18, 2009, 4:01:57 PM (15 years ago)
- 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:
- 2cc75c3
- Parents:
- 174e0e
- git-author:
- Frederik Heber <heber@…> (10/18/09 15:59:52)
- git-committer:
- Frederik Heber <heber@…> (10/18/09 16:01:57)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/molecule_graph.cpp
r174e0e ref9aae 494 494 }; 495 495 496 /** initialise each vertex as white with no predecessor, empty queue, color Root lightgray. 497 * 498 */ 499 void InitializeAccounting(atom **&PredecessorList, int *&ShortestPathList, enum Shading *&ColorList, int AtomCount) 500 { 501 for (int i=AtomCount;i--;) { 502 PredecessorList[i] = NULL; 503 ShortestPathList[i] = -1; 504 ColorList[i] = white; 505 } 506 }; 507 508 void ResetAccounting(atom *&Walker, class StackClass<atom *> *&TouchedStack, int *&ShortestPathList, class StackClass<atom *> *&BFSStack) 509 { 510 ShortestPathList[Walker->nr] = 0; 511 BFSStack->ClearStack(); // start with empty BFS stack 512 BFSStack->Push(Walker); 513 TouchedStack->Push(Walker); 514 }; 515 516 void CyclicBFSFromRootToRoot(ofstream *out, atom *&Root, bond *&BackEdge, class StackClass<atom *> *&TouchedStack, int *&ShortestPathList, atom **&PredecessorList, class StackClass<atom *> *&BFSStack, enum Shading *&ColorList) 517 { 518 atom *Walker = NULL; 519 atom *OtherAtom = NULL; 520 do { // look for Root 521 Walker = BFSStack->PopFirst(); 522 *out << Verbose(2) << "Current Walker is " << *Walker << ", we look for SP to Root " << *Root << "." << endl; 523 for (BondList::const_iterator Runner = Walker->ListOfBonds.begin(); Runner != Walker->ListOfBonds.end(); (++Runner)) { 524 if ((*Runner) != BackEdge) { // only walk along DFS spanning tree (otherwise we always find SP of one being backedge Binder) 525 OtherAtom = (*Runner)->GetOtherAtom(Walker); 526 #ifdef ADDHYDROGEN 527 if (OtherAtom->type->Z != 1) { 528 #endif 529 *out << Verbose(2) << "Current OtherAtom is: " << OtherAtom->Name << " for bond " << *(*Runner) << "." << endl; 530 if (ColorList[OtherAtom->nr] == white) { 531 TouchedStack->Push(OtherAtom); 532 ColorList[OtherAtom->nr] = lightgray; 533 PredecessorList[OtherAtom->nr] = Walker; // Walker is the predecessor 534 ShortestPathList[OtherAtom->nr] = ShortestPathList[Walker->nr]+1; 535 *out << Verbose(2) << "Coloring OtherAtom " << OtherAtom->Name << " lightgray, its predecessor is " << Walker->Name << " and its Shortest Path is " << ShortestPathList[OtherAtom->nr] << " egde(s) long." << endl; 536 //if (ShortestPathList[OtherAtom->nr] < MinimumRingSize[Walker->GetTrueFather()->nr]) { // Check for maximum distance 537 *out << Verbose(3) << "Putting OtherAtom into queue." << endl; 538 BFSStack->Push(OtherAtom); 539 //} 540 } else { 541 *out << Verbose(3) << "Not Adding, has already been visited." << endl; 542 } 543 if (OtherAtom == Root) 544 break; 545 #ifdef ADDHYDROGEN 546 } else { 547 *out << Verbose(2) << "Skipping hydrogen atom " << *OtherAtom << "." << endl; 548 ColorList[OtherAtom->nr] = black; 549 } 550 #endif 551 } else { 552 *out << Verbose(2) << "Bond " << *(*Runner) << " not Visiting, is the back edge." << endl; 553 } 554 } 555 ColorList[Walker->nr] = black; 556 *out << Verbose(1) << "Coloring Walker " << Walker->Name << " black." << endl; 557 if (OtherAtom == Root) { // if we have found the root, check whether this cycle wasn't already found beforehand 558 // step through predecessor list 559 while (OtherAtom != BackEdge->rightatom) { 560 if (!OtherAtom->GetTrueFather()->IsCyclic) // if one bond in the loop is not marked as cyclic, we haven't found this cycle yet 561 break; 562 else 563 OtherAtom = PredecessorList[OtherAtom->nr]; 564 } 565 if (OtherAtom == BackEdge->rightatom) { // if each atom in found cycle is cyclic, loop's been found before already 566 *out << Verbose(3) << "This cycle was already found before, skipping and removing seeker from search." << endl;\ 567 do { 568 OtherAtom = TouchedStack->PopLast(); 569 if (PredecessorList[OtherAtom->nr] == Walker) { 570 *out << Verbose(4) << "Removing " << *OtherAtom << " from lists and stacks." << endl; 571 PredecessorList[OtherAtom->nr] = NULL; 572 ShortestPathList[OtherAtom->nr] = -1; 573 ColorList[OtherAtom->nr] = white; 574 BFSStack->RemoveItem(OtherAtom); 575 } 576 } while ((!TouchedStack->IsEmpty()) && (PredecessorList[OtherAtom->nr] == NULL)); 577 TouchedStack->Push(OtherAtom); // last was wrongly popped 578 OtherAtom = BackEdge->rightatom; // set to not Root 579 } else 580 OtherAtom = Root; 581 } 582 } while ((!BFSStack->IsEmpty()) && (OtherAtom != Root) && (OtherAtom != NULL)); // || (ShortestPathList[OtherAtom->nr] < MinimumRingSize[Walker->GetTrueFather()->nr]))); 583 }; 584 585 void RetrieveCycleMembers(ofstream *out, atom *&Root, atom *&OtherAtom, bond *&BackEdge, atom **&PredecessorList, int *&MinimumRingSize, int &MinRingSize) 586 { 587 atom *Walker = NULL; 588 int NumCycles = 0; 589 int RingSize = -1; 590 591 if (OtherAtom == Root) { 592 // now climb back the predecessor list and thus find the cycle members 593 NumCycles++; 594 RingSize = 1; 595 Root->GetTrueFather()->IsCyclic = true; 596 *out << Verbose(1) << "Found ring contains: "; 597 Walker = Root; 598 while (Walker != BackEdge->rightatom) { 599 *out << Walker->Name << " <-> "; 600 Walker = PredecessorList[Walker->nr]; 601 Walker->GetTrueFather()->IsCyclic = true; 602 RingSize++; 603 } 604 *out << Walker->Name << " with a length of " << RingSize << "." << endl << endl; 605 // walk through all and set MinimumRingSize 606 Walker = Root; 607 MinimumRingSize[Walker->GetTrueFather()->nr] = RingSize; 608 while (Walker != BackEdge->rightatom) { 609 Walker = PredecessorList[Walker->nr]; 610 if (RingSize < MinimumRingSize[Walker->GetTrueFather()->nr]) 611 MinimumRingSize[Walker->GetTrueFather()->nr] = RingSize; 612 } 613 if ((RingSize < MinRingSize) || (MinRingSize == -1)) 614 MinRingSize = RingSize; 615 } else { 616 *out << Verbose(1) << "No ring containing " << *Root << " with length equal to or smaller than " << MinimumRingSize[Walker->GetTrueFather()->nr] << " found." << endl; 617 } 618 }; 619 620 void CleanAccounting(class StackClass<atom *> *&TouchedStack, atom **&PredecessorList, int *&ShortestPathList, enum Shading *&ColorList) 621 { 622 atom *Walker = NULL; 623 while (!TouchedStack->IsEmpty()){ 624 Walker = TouchedStack->PopFirst(); 625 PredecessorList[Walker->nr] = NULL; 626 ShortestPathList[Walker->nr] = -1; 627 ColorList[Walker->nr] = white; 628 } 629 }; 630 631 632 void BFSToNextCycle(ofstream *out, atom *&Root, atom *&Walker, bond *&BackEdge, int *&MinimumRingSize, int AtomCount) 633 { 634 atom **PredecessorList = Malloc<atom*>(AtomCount, "molecule::CyclicStructureAnalysis: **PredecessorList"); 635 int *ShortestPathList = Malloc<int>(AtomCount, "molecule::CyclicStructureAnalysis: *ShortestPathList"); 636 enum Shading *ColorList = Malloc<enum Shading>(AtomCount, "molecule::CyclicStructureAnalysis: *ColorList"); 637 class StackClass<atom *> *BFSStack = new StackClass<atom *> (AtomCount); // will hold the current ring 638 class StackClass<atom *> *TouchedStack = new StackClass<atom *> (AtomCount); // contains all "touched" atoms (that need to be reset after BFS loop) 639 atom *OtherAtom = Walker; 640 641 InitializeAccounting(PredecessorList, ShortestPathList, ColorList, AtomCount); 642 643 ResetAccounting(Walker, TouchedStack, ShortestPathList, BFSStack); 644 while (OtherAtom != NULL) { // look for Root 645 Walker = BFSStack->PopFirst(); 646 //*out << Verbose(2) << "Current Walker is " << *Walker << ", we look for SP to Root " << *Root << "." << endl; 647 for (BondList::const_iterator Runner = Walker->ListOfBonds.begin(); Runner != Walker->ListOfBonds.end(); (++Runner)) { 648 if (((*Runner) != BackEdge) || (Walker->ListOfBonds.size() == 1)) { // only walk along DFS spanning tree (otherwise we always find SP of 1 being backedge Binder), but terminal hydrogens may be connected via backedge, hence extra check 649 OtherAtom = (*Runner)->GetOtherAtom(Walker); 650 //*out << Verbose(2) << "Current OtherAtom is: " << OtherAtom->Name << " for bond " << *Binder << "." << endl; 651 if (ColorList[OtherAtom->nr] == white) { 652 TouchedStack->Push(OtherAtom); 653 ColorList[OtherAtom->nr] = lightgray; 654 PredecessorList[OtherAtom->nr] = Walker; // Walker is the predecessor 655 ShortestPathList[OtherAtom->nr] = ShortestPathList[Walker->nr]+1; 656 //*out << Verbose(2) << "Coloring OtherAtom " << OtherAtom->Name << " lightgray, its predecessor is " << Walker->Name << " and its Shortest Path is " << ShortestPathList[OtherAtom->nr] << " egde(s) long." << endl; 657 if (OtherAtom->GetTrueFather()->IsCyclic) { // if the other atom is connected to a ring 658 MinimumRingSize[Root->GetTrueFather()->nr] = ShortestPathList[OtherAtom->nr]+MinimumRingSize[OtherAtom->GetTrueFather()->nr]; 659 OtherAtom = NULL; //break; 660 break; 661 } else 662 BFSStack->Push(OtherAtom); 663 } else { 664 //*out << Verbose(3) << "Not Adding, has already been visited." << endl; 665 } 666 } else { 667 //*out << Verbose(3) << "Not Visiting, is a back edge." << endl; 668 } 669 } 670 ColorList[Walker->nr] = black; 671 //*out << Verbose(1) << "Coloring Walker " << Walker->Name << " black." << endl; 672 } 673 //CleanAccountingLists(TouchedStack, PredecessorList, ShortestPathList, ColorList); 674 675 Free(&PredecessorList); 676 Free(&ShortestPathList); 677 Free(&ColorList); 678 delete(BFSStack); 679 }; 680 681 void AssignRingSizetoNonCycleMembers(ofstream *out, int *&MinimumRingSize, int &MinRingSize, int &NumCycles, molecule *mol, bond *&BackEdge) 682 { 683 atom *Root= NULL; 684 atom *Walker = NULL; 685 if (MinRingSize != -1) { // if rings are present 686 // go over all atoms 687 Root = mol->start; 688 while(Root->next != mol->end) { 689 Root = Root->next; 690 691 if (MinimumRingSize[Root->GetTrueFather()->nr] == mol->AtomCount) { // check whether MinimumRingSize is set, if not BFS to next where it is 692 Walker = Root; 693 694 //*out << Verbose(1) << "---------------------------------------------------------------------------------------------------------" << endl; 695 BFSToNextCycle(out, Root, Walker, BackEdge, MinimumRingSize, mol->AtomCount); 696 697 } 698 *out << Verbose(1) << "Minimum ring size of " << *Root << " is " << MinimumRingSize[Root->GetTrueFather()->nr] << "." << endl; 699 } 700 *out << Verbose(1) << "Minimum ring size is " << MinRingSize << ", over " << NumCycles << " cycles total." << endl; 701 } else 702 *out << Verbose(1) << "No rings were detected in the molecular structure." << endl; 703 }; 704 496 705 /** Analyses the cycles found and returns minimum of all cycle lengths. 497 706 * We begin with a list of Back edges found during DepthFirstSearchAnalysis(). We go through this list - one end is the Root, … … 511 720 class StackClass<atom *> *BFSStack = new StackClass<atom *> (AtomCount); // will hold the current ring 512 721 class StackClass<atom *> *TouchedStack = new StackClass<atom *> (AtomCount); // contains all "touched" atoms (that need to be reset after BFS loop) 513 atom *Walker = NULL, *OtherAtom = NULL, *Root = NULL; 514 bond *Binder = NULL, *BackEdge = NULL; 515 int RingSize, NumCycles, MinRingSize = -1; 516 517 // initialise each vertex as white with no predecessor, empty queue, color Root lightgray 518 for (int i=AtomCount;i--;) { 519 PredecessorList[i] = NULL; 520 ShortestPathList[i] = -1; 521 ColorList[i] = white; 522 } 722 atom *Walker = NULL; 723 atom *OtherAtom = NULL; 724 atom *Root = NULL; 725 bond *BackEdge = NULL; 726 int NumCycles = 0; 727 int MinRingSize = -1; 728 729 InitializeAccounting(PredecessorList, ShortestPathList, ColorList, AtomCount); 523 730 524 731 *out << Verbose(1) << "Back edge list - "; … … 533 740 // this is the source point 534 741 Walker = BackEdge->rightatom; 535 ShortestPathList[Walker->nr] = 0; 536 BFSStack->ClearStack(); // start with empty BFS stack 537 BFSStack->Push(Walker); 538 TouchedStack->Push(Walker); 742 743 ResetAccounting(Walker, TouchedStack, ShortestPathList, BFSStack); 744 539 745 *out << Verbose(1) << "---------------------------------------------------------------------------------------------------------" << endl; 540 746 OtherAtom = NULL; 541 do { // look for Root 542 Walker = BFSStack->PopFirst(); 543 *out << Verbose(2) << "Current Walker is " << *Walker << ", we look for SP to Root " << *Root << "." << endl; 544 for (BondList::const_iterator Runner = Walker->ListOfBonds.begin(); Runner != Walker->ListOfBonds.end(); (++Runner)) { 545 if ((*Runner) != BackEdge) { // only walk along DFS spanning tree (otherwise we always find SP of one being backedge Binder) 546 OtherAtom = (*Runner)->GetOtherAtom(Walker); 547 #ifdef ADDHYDROGEN 548 if (OtherAtom->type->Z != 1) { 549 #endif 550 *out << Verbose(2) << "Current OtherAtom is: " << OtherAtom->Name << " for bond " << *Binder << "." << endl; 551 if (ColorList[OtherAtom->nr] == white) { 552 TouchedStack->Push(OtherAtom); 553 ColorList[OtherAtom->nr] = lightgray; 554 PredecessorList[OtherAtom->nr] = Walker; // Walker is the predecessor 555 ShortestPathList[OtherAtom->nr] = ShortestPathList[Walker->nr]+1; 556 *out << Verbose(2) << "Coloring OtherAtom " << OtherAtom->Name << " lightgray, its predecessor is " << Walker->Name << " and its Shortest Path is " << ShortestPathList[OtherAtom->nr] << " egde(s) long." << endl; 557 //if (ShortestPathList[OtherAtom->nr] < MinimumRingSize[Walker->GetTrueFather()->nr]) { // Check for maximum distance 558 *out << Verbose(3) << "Putting OtherAtom into queue." << endl; 559 BFSStack->Push(OtherAtom); 560 //} 561 } else { 562 *out << Verbose(3) << "Not Adding, has already been visited." << endl; 563 } 564 if (OtherAtom == Root) 565 break; 566 #ifdef ADDHYDROGEN 567 } else { 568 *out << Verbose(2) << "Skipping hydrogen atom " << *OtherAtom << "." << endl; 569 ColorList[OtherAtom->nr] = black; 570 } 571 #endif 572 } else { 573 *out << Verbose(2) << "Bond " << *Binder << " not Visiting, is the back edge." << endl; 574 } 575 } 576 ColorList[Walker->nr] = black; 577 *out << Verbose(1) << "Coloring Walker " << Walker->Name << " black." << endl; 578 if (OtherAtom == Root) { // if we have found the root, check whether this cycle wasn't already found beforehand 579 // step through predecessor list 580 while (OtherAtom != BackEdge->rightatom) { 581 if (!OtherAtom->GetTrueFather()->IsCyclic) // if one bond in the loop is not marked as cyclic, we haven't found this cycle yet 582 break; 583 else 584 OtherAtom = PredecessorList[OtherAtom->nr]; 585 } 586 if (OtherAtom == BackEdge->rightatom) { // if each atom in found cycle is cyclic, loop's been found before already 587 *out << Verbose(3) << "This cycle was already found before, skipping and removing seeker from search." << endl;\ 588 do { 589 OtherAtom = TouchedStack->PopLast(); 590 if (PredecessorList[OtherAtom->nr] == Walker) { 591 *out << Verbose(4) << "Removing " << *OtherAtom << " from lists and stacks." << endl; 592 PredecessorList[OtherAtom->nr] = NULL; 593 ShortestPathList[OtherAtom->nr] = -1; 594 ColorList[OtherAtom->nr] = white; 595 BFSStack->RemoveItem(OtherAtom); 596 } 597 } while ((!TouchedStack->IsEmpty()) && (PredecessorList[OtherAtom->nr] == NULL)); 598 TouchedStack->Push(OtherAtom); // last was wrongly popped 599 OtherAtom = BackEdge->rightatom; // set to not Root 600 } else 601 OtherAtom = Root; 602 } 603 } while ((!BFSStack->IsEmpty()) && (OtherAtom != Root) && (OtherAtom != NULL)); // || (ShortestPathList[OtherAtom->nr] < MinimumRingSize[Walker->GetTrueFather()->nr]))); 604 605 if (OtherAtom == Root) { 606 // now climb back the predecessor list and thus find the cycle members 607 NumCycles++; 608 RingSize = 1; 609 Root->GetTrueFather()->IsCyclic = true; 610 *out << Verbose(1) << "Found ring contains: "; 611 Walker = Root; 612 while (Walker != BackEdge->rightatom) { 613 *out << Walker->Name << " <-> "; 614 Walker = PredecessorList[Walker->nr]; 615 Walker->GetTrueFather()->IsCyclic = true; 616 RingSize++; 617 } 618 *out << Walker->Name << " with a length of " << RingSize << "." << endl << endl; 619 // walk through all and set MinimumRingSize 620 Walker = Root; 621 MinimumRingSize[Walker->GetTrueFather()->nr] = RingSize; 622 while (Walker != BackEdge->rightatom) { 623 Walker = PredecessorList[Walker->nr]; 624 if (RingSize < MinimumRingSize[Walker->GetTrueFather()->nr]) 625 MinimumRingSize[Walker->GetTrueFather()->nr] = RingSize; 626 } 627 if ((RingSize < MinRingSize) || (MinRingSize == -1)) 628 MinRingSize = RingSize; 629 } else { 630 *out << Verbose(1) << "No ring containing " << *Root << " with length equal to or smaller than " << MinimumRingSize[Walker->GetTrueFather()->nr] << " found." << endl; 631 } 632 633 // now clean the lists 634 while (!TouchedStack->IsEmpty()){ 635 Walker = TouchedStack->PopFirst(); 636 PredecessorList[Walker->nr] = NULL; 637 ShortestPathList[Walker->nr] = -1; 638 ColorList[Walker->nr] = white; 639 } 640 } 641 if (MinRingSize != -1) { 642 // go over all atoms 643 Root = start; 644 while(Root->next != end) { 645 Root = Root->next; 646 647 if (MinimumRingSize[Root->GetTrueFather()->nr] == AtomCount) { // check whether MinimumRingSize is set, if not BFS to next where it is 648 Walker = Root; 649 ShortestPathList[Walker->nr] = 0; 650 BFSStack->ClearStack(); // start with empty BFS stack 651 BFSStack->Push(Walker); 652 TouchedStack->Push(Walker); 653 //*out << Verbose(1) << "---------------------------------------------------------------------------------------------------------" << endl; 654 OtherAtom = Walker; 655 while (OtherAtom != NULL) { // look for Root 656 Walker = BFSStack->PopFirst(); 657 //*out << Verbose(2) << "Current Walker is " << *Walker << ", we look for SP to Root " << *Root << "." << endl; 658 for (BondList::const_iterator Runner = Walker->ListOfBonds.begin(); Runner != Walker->ListOfBonds.end(); (++Runner)) { 659 if (((*Runner) != BackEdge) || (Walker->ListOfBonds.size() == 1)) { // only walk along DFS spanning tree (otherwise we always find SP of 1 being backedge Binder), but terminal hydrogens may be connected via backedge, hence extra check 660 OtherAtom = (*Runner)->GetOtherAtom(Walker); 661 //*out << Verbose(2) << "Current OtherAtom is: " << OtherAtom->Name << " for bond " << *Binder << "." << endl; 662 if (ColorList[OtherAtom->nr] == white) { 663 TouchedStack->Push(OtherAtom); 664 ColorList[OtherAtom->nr] = lightgray; 665 PredecessorList[OtherAtom->nr] = Walker; // Walker is the predecessor 666 ShortestPathList[OtherAtom->nr] = ShortestPathList[Walker->nr]+1; 667 //*out << Verbose(2) << "Coloring OtherAtom " << OtherAtom->Name << " lightgray, its predecessor is " << Walker->Name << " and its Shortest Path is " << ShortestPathList[OtherAtom->nr] << " egde(s) long." << endl; 668 if (OtherAtom->GetTrueFather()->IsCyclic) { // if the other atom is connected to a ring 669 MinimumRingSize[Root->GetTrueFather()->nr] = ShortestPathList[OtherAtom->nr]+MinimumRingSize[OtherAtom->GetTrueFather()->nr]; 670 OtherAtom = NULL; //break; 671 break; 672 } else 673 BFSStack->Push(OtherAtom); 674 } else { 675 //*out << Verbose(3) << "Not Adding, has already been visited." << endl; 676 } 677 } else { 678 //*out << Verbose(3) << "Not Visiting, is a back edge." << endl; 679 } 680 } 681 ColorList[Walker->nr] = black; 682 //*out << Verbose(1) << "Coloring Walker " << Walker->Name << " black." << endl; 683 } 684 685 // now clean the lists 686 while (!TouchedStack->IsEmpty()){ 687 Walker = TouchedStack->PopFirst(); 688 PredecessorList[Walker->nr] = NULL; 689 ShortestPathList[Walker->nr] = -1; 690 ColorList[Walker->nr] = white; 691 } 692 } 693 *out << Verbose(1) << "Minimum ring size of " << *Root << " is " << MinimumRingSize[Root->GetTrueFather()->nr] << "." << endl; 694 } 695 *out << Verbose(1) << "Minimum ring size is " << MinRingSize << ", over " << NumCycles << " cycles total." << endl; 696 } else 697 *out << Verbose(1) << "No rings were detected in the molecular structure." << endl; 698 747 CyclicBFSFromRootToRoot(out, Root, BackEdge, TouchedStack, ShortestPathList, PredecessorList, BFSStack, ColorList); 748 749 RetrieveCycleMembers(out, Root, OtherAtom, BackEdge, PredecessorList, MinimumRingSize, MinRingSize); 750 751 CleanAccounting(TouchedStack, PredecessorList, ShortestPathList, ColorList); 752 } 699 753 Free(&PredecessorList); 700 754 Free(&ShortestPathList); 701 755 Free(&ColorList); 702 756 delete(BFSStack); 757 758 AssignRingSizetoNonCycleMembers(out, MinimumRingSize, MinRingSize, NumCycles, this, BackEdge); 759 703 760 }; 704 761
Note:
See TracChangeset
for help on using the changeset viewer.