Ignore:
Timestamp:
Mar 2, 2011, 9:53:08 PM (14 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:
2fa1dc
Parents:
1a4d4fe
git-author:
Frederik Heber <heber@…> (02/25/11 22:15:31)
git-committer:
Frederik Heber <heber@…> (03/02/11 21:53:08)
Message:

Moved DepthFirstSearchAnalysis into functor in Graph/.

Smaller fixes:

TESTFIXES:

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/molecule_graph.cpp

    r1a4d4fe r49c059  
    3030#include "CodePatterns/Verbose.hpp"
    3131#include "config.hpp"
     32#include "Graph/DepthFirstSearchAnalysis.hpp"
    3233#include "element.hpp"
    3334#include "Graph/BondGraph.hpp"
    … …  
    4445#define MAXBONDS 8
    4546
    46 
    47 /** Accounting data for Depth First Search.
    48  */
    49 struct DFSAccounting
    50 {
    51   std::deque<atom *> *AtomStack;
    52   std::deque<bond *> *BackEdgeStack;
    53   int CurrentGraphNr;
    54   int ComponentNumber;
    55   atom *Root;
    56   bool BackStepping;
    57 };
    58 
    59 /************************************* Functions for class molecule *********************************/
    6047
    6148/** Fills the bond structure of this chain list subgraphs that are derived from a complete \a *reference molecule.
    … …  
    146133;
    147134
    148 
    149 /** Counts all cyclic bonds and returns their number.
    150  * \note Hydrogen bonds can never by cyclic, thus no check for that
    151  * \return number of cyclic bonds
    152  */
    153 int molecule::CountCyclicBonds()
    154 {
    155   NoCyclicBonds = 0;
    156   int *MinimumRingSize = NULL;
    157   MoleculeLeafClass *Subgraphs = NULL;
    158   std::deque<bond *> *BackEdgeStack = NULL;
    159   for(molecule::iterator AtomRunner = begin(); AtomRunner != end(); ++AtomRunner) {
    160     const BondList& ListOfBonds = (*AtomRunner)->getListOfBonds();
    161     if ((!ListOfBonds.empty()) && ((*ListOfBonds.begin())->Type == GraphEdge::Undetermined)) {
    162       DoLog(0) && (Log() << Verbose(0) << "No Depth-First-Search analysis performed so far, calling ..." << endl);
    163       Subgraphs = DepthFirstSearchAnalysis(BackEdgeStack);
    164       while (Subgraphs->next != NULL) {
    165         Subgraphs = Subgraphs->next;
    166         delete (Subgraphs->previous);
    167       }
    168       delete (Subgraphs);
    169       delete[] (MinimumRingSize);
    170       break;
    171     }
    172   }
    173   for(molecule::iterator AtomRunner = begin(); AtomRunner != end(); ++AtomRunner) {
    174     const BondList& ListOfBonds = (*AtomRunner)->getListOfBonds();
    175     for(BondList::const_iterator BondRunner = ListOfBonds.begin();
    176         BondRunner != ListOfBonds.end();
    177         ++BondRunner)
    178       if ((*BondRunner)->leftatom == *AtomRunner)
    179         if ((*BondRunner)->Cyclic)
    180           NoCyclicBonds++;
    181   }
    182   delete (BackEdgeStack);
    183   return NoCyclicBonds;
    184 }
    185 ;
    186 
    187 
    188 /** Sets atom::GraphNr and atom::LowpointNr to DFSAccounting::CurrentGraphNr.
    189  * \param *Walker current node
    190  * \param &BFS structure with accounting data for BFS
    191  */
    192 void DepthFirstSearchAnalysis_SetWalkersGraphNr(atom *&Walker, struct DFSAccounting &DFS)
    193 {
    194   if (!DFS.BackStepping) { // if we don't just return from (8)
    195     Walker->GraphNr = DFS.CurrentGraphNr;
    196     Walker->LowpointNr = DFS.CurrentGraphNr;
    197     DoLog(1) && (Log() << Verbose(1) << "Setting Walker[" << Walker->getName() << "]'s number to " << Walker->GraphNr << " with Lowpoint " << Walker->LowpointNr << "." << endl);
    198     DFS.AtomStack->push_front(Walker);
    199     DFS.CurrentGraphNr++;
    200   }
    201 }
    202 ;
    203 
    204 /** During DFS goes along unvisited bond and touches other atom.
    205  * Sets bond::type, if
    206  *  -# BackEdge: set atom::LowpointNr and push on \a BackEdgeStack
    207  *  -# TreeEgde: set atom::Ancestor and continue with Walker along this edge
    208  * Continue until molecule::FindNextUnused() finds no more unused bonds.
    209  * \param *mol molecule with atoms and finding unused bonds
    210  * \param *&Binder current edge
    211  * \param &DFS DFS accounting data
    212  */
    213 void DepthFirstSearchAnalysis_ProbeAlongUnusedBond(const molecule * const mol, atom *&Walker, bond *&Binder, struct DFSAccounting &DFS)
    214 {
    215   atom *OtherAtom = NULL;
    216 
    217   do { // (3) if Walker has no unused egdes, go to (5)
    218     DFS.BackStepping = false; // reset backstepping flag for (8)
    219     if (Binder == NULL) // if we don't just return from (11), Binder is already set to next unused
    220       Binder = mol->FindNextUnused(Walker);
    221     if (Binder == NULL)
    222       break;
    223     DoLog(2) && (Log() << Verbose(2) << "Current Unused Bond is " << *Binder << "." << endl);
    224     // (4) Mark Binder used, ...
    225     Binder->MarkUsed(GraphEdge::black);
    226     OtherAtom = Binder->GetOtherAtom(Walker);
    227     DoLog(2) && (Log() << Verbose(2) << "(4) OtherAtom is " << OtherAtom->getName() << "." << endl);
    228     if (OtherAtom->GraphNr != -1) {
    229       // (4a) ... if "other" atom has been visited (GraphNr != 0), set lowpoint to minimum of both, go to (3)
    230       Binder->Type = GraphEdge::BackEdge;
    231       DFS.BackEdgeStack->push_front(Binder);
    232       Walker->LowpointNr = (Walker->LowpointNr < OtherAtom->GraphNr) ? Walker->LowpointNr : OtherAtom->GraphNr;
    233       DoLog(3) && (Log() << Verbose(3) << "(4a) Visited: Setting Lowpoint of Walker[" << Walker->getName() << "] to " << Walker->LowpointNr << "." << endl);
    234     } else {
    235       // (4b) ... otherwise set OtherAtom as Ancestor of Walker and Walker as OtherAtom, go to (2)
    236       Binder->Type = GraphEdge::TreeEdge;
    237       OtherAtom->Ancestor = Walker;
    238       Walker = OtherAtom;
    239       DoLog(3) && (Log() << Verbose(3) << "(4b) Not Visited: OtherAtom[" << OtherAtom->getName() << "]'s Ancestor is now " << OtherAtom->Ancestor->getName() << ", Walker is OtherAtom " << OtherAtom->getName() << "." << endl);
    240       break;
    241     }
    242     Binder = NULL;
    243   } while (1); // (3)
    244 }
    245 ;
    246 
    247 /** Checks whether we have a new component.
    248  * if atom::LowpointNr of \a *&Walker is greater than atom::GraphNr of its atom::Ancestor, we have a new component.
    249  * Meaning that if we touch upon a node who suddenly has a smaller atom::LowpointNr than its ancestor, then we
    250  * have a found a new branch in the graph tree.
    251  * \param *mol molecule with atoms and finding unused bonds
    252  * \param *&Walker current node
    253  * \param &DFS DFS accounting data
    254  */
    255 void DepthFirstSearchAnalysis_CheckForaNewComponent(const molecule * const mol, atom *&Walker, struct DFSAccounting &DFS, MoleculeLeafClass *&LeafWalker)
    256 {
    257   atom *OtherAtom = NULL;
    258 
    259   // (5) if Ancestor of Walker is ...
    260   DoLog(1) && (Log() << Verbose(1) << "(5) Number of Walker[" << Walker->getName() << "]'s Ancestor[" << Walker->Ancestor->getName() << "] is " << Walker->Ancestor->GraphNr << "." << endl);
    261 
    262   if (Walker->Ancestor->GraphNr != DFS.Root->GraphNr) {
    263     // (6)  (Ancestor of Walker is not Root)
    264     if (Walker->LowpointNr < Walker->Ancestor->GraphNr) {
    265       // (6a) set Ancestor's Lowpoint number to minimum of of its Ancestor and itself, go to Step(8)
    266       Walker->Ancestor->LowpointNr = (Walker->Ancestor->LowpointNr < Walker->LowpointNr) ? Walker->Ancestor->LowpointNr : Walker->LowpointNr;
    267       DoLog(2) && (Log() << Verbose(2) << "(6) Setting Walker[" << Walker->getName() << "]'s Ancestor[" << Walker->Ancestor->getName() << "]'s Lowpoint to " << Walker->Ancestor->LowpointNr << "." << endl);
    268     } else {
    269       // (7) (Ancestor of Walker is a separating vertex, remove all from stack till Walker (including), these and Ancestor form a component
    270       Walker->Ancestor->SeparationVertex = true;
    271       DoLog(2) && (Log() << Verbose(2) << "(7) Walker[" << Walker->getName() << "]'s Ancestor[" << Walker->Ancestor->getName() << "]'s is a separating vertex, creating component." << endl);
    272       mol->SetNextComponentNumber(Walker->Ancestor, DFS.ComponentNumber);
    273       DoLog(3) && (Log() << Verbose(3) << "(7) Walker[" << Walker->getName() << "]'s Ancestor's Compont is " << DFS.ComponentNumber << "." << endl);
    274       mol->SetNextComponentNumber(Walker, DFS.ComponentNumber);
    275       DoLog(3) && (Log() << Verbose(3) << "(7) Walker[" << Walker->getName() << "]'s Compont is " << DFS.ComponentNumber << "." << endl);
    276       do {
    277         ASSERT(!DFS.AtomStack->empty(), "DepthFirstSearchAnalysis_CheckForaNewComponent() - DFS.AtomStack is empty!");
    278         OtherAtom = DFS.AtomStack->front();
    279         DFS.AtomStack->pop_front();
    280         LeafWalker->Leaf->AddCopyAtom(OtherAtom);
    281         mol->SetNextComponentNumber(OtherAtom, DFS.ComponentNumber);
    282         DoLog(3) && (Log() << Verbose(3) << "(7) Other[" << OtherAtom->getName() << "]'s Compont is " << DFS.ComponentNumber << "." << endl);
    283       } while (OtherAtom != Walker);
    284       DFS.ComponentNumber++;
    285     }
    286     // (8) Walker becomes its Ancestor, go to (3)
    287     DoLog(2) && (Log() << Verbose(2) << "(8) Walker[" << Walker->getName() << "] is now its Ancestor " << Walker->Ancestor->getName() << ", backstepping. " << endl);
    288     Walker = Walker->Ancestor;
    289     DFS.BackStepping = true;
    290   }
    291 }
    292 ;
    293 
    294 /** Cleans the root stack when we have found a component.
    295  * If we are not DFSAccounting::BackStepping, then we clear the root stack by putting everything into a
    296  * component down till we meet DFSAccounting::Root.
    297  * \param *mol molecule with atoms and finding unused bonds
    298  * \param *&Walker current node
    299  * \param *&Binder current edge
    300  * \param &DFS DFS accounting data
    301  */
    302 void DepthFirstSearchAnalysis_CleanRootStackDownTillWalker(const molecule * const mol, atom *&Walker, bond *&Binder, struct DFSAccounting &DFS, MoleculeLeafClass *&LeafWalker)
    303 {
    304   atom *OtherAtom = NULL;
    305 
    306   if (!DFS.BackStepping) { // coming from (8) want to go to (3)
    307     // (9) remove all from stack till Walker (including), these and Root form a component
    308     //DFS.AtomStack->Output(out);
    309     mol->SetNextComponentNumber(DFS.Root, DFS.ComponentNumber);
    310     DoLog(3) && (Log() << Verbose(3) << "(9) Root[" << DFS.Root->getName() << "]'s Component is " << DFS.ComponentNumber << "." << endl);
    311     mol->SetNextComponentNumber(Walker, DFS.ComponentNumber);
    312     DoLog(3) && (Log() << Verbose(3) << "(9) Walker[" << Walker->getName() << "]'s Component is " << DFS.ComponentNumber << "." << endl);
    313     do {
    314       ASSERT(!DFS.AtomStack->empty(), "DepthFirstSearchAnalysis_CleanRootStackDownTillWalker() - DFS.AtomStack is empty!");
    315       OtherAtom = DFS.AtomStack->front();
    316       DFS.AtomStack->pop_front();
    317       LeafWalker->Leaf->AddCopyAtom(OtherAtom);
    318       mol->SetNextComponentNumber(OtherAtom, DFS.ComponentNumber);
    319       DoLog(3) && (Log() << Verbose(3) << "(7) Other[" << OtherAtom->getName() << "]'s Component is " << DFS.ComponentNumber << "." << endl);
    320     } while (OtherAtom != Walker);
    321     DFS.ComponentNumber++;
    322 
    323     // (11) Root is separation vertex,  set Walker to Root and go to (4)
    324     Walker = DFS.Root;
    325     Binder = mol->FindNextUnused(Walker);
    326     DoLog(1) && (Log() << Verbose(1) << "(10) Walker is Root[" << DFS.Root->getName() << "], next Unused Bond is " << Binder << "." << endl);
    327     if (Binder != NULL) { // Root is separation vertex
    328       DoLog(1) && (Log() << Verbose(1) << "(11) Root is a separation vertex." << endl);
    329       Walker->SeparationVertex = true;
    330     }
    331   }
    332 }
    333 ;
    334 
    335 /** Initializes DFSAccounting structure.
    336  * \param &DFS accounting structure to allocate
    337  * \param *mol molecule with AtomCount, BondCount and all atoms
    338  */
    339 void DepthFirstSearchAnalysis_Init(struct DFSAccounting &DFS, const molecule * const mol)
    340 {
    341   DFS.AtomStack = new std::deque<atom *> (mol->getAtomCount());
    342   DFS.CurrentGraphNr = 0;
    343   DFS.ComponentNumber = 0;
    344   DFS.BackStepping = false;
    345   mol->ResetAllBondsToUnused();
    346   DFS.BackEdgeStack->clear();
    347 }
    348 ;
    349 
    350 /** Free's DFSAccounting structure.
    351  * \param &DFS accounting structure to free
    352  */
    353 void DepthFirstSearchAnalysis_Finalize(struct DFSAccounting &DFS)
    354 {
    355   delete (DFS.AtomStack);
    356   // delete (DFS.BackEdgeStack); // DON'T free, see DepthFirstSearchAnalysis(), is returned as allocated
    357 }
    358 ;
    359 
    360 void molecule::init_DFS(struct DFSAccounting &DFS) const{
    361   DepthFirstSearchAnalysis_Init(DFS, this);
    362   for_each(atoms.begin(),atoms.end(),mem_fun(&atom::resetGraphNr));
    363   for_each(atoms.begin(),atoms.end(),mem_fun(&atom::InitComponentNr));
    364 }
    365 
    366 /** Performs a Depth-First search on this molecule.
    367  * Marks bonds in molecule as cyclic, bridge, ... and atoms as
    368  * articulations points, ...
    369  * We use the algorithm from [Even, Graph Algorithms, p.62].
    370  * \param *&BackEdgeStack NULL pointer to std::deque<bond *> with all the found back edges, allocated and filled on return
    371  * \return list of each disconnected subgraph as an individual molecule class structure
    372  */
    373 MoleculeLeafClass * molecule::DepthFirstSearchAnalysis(std::deque<bond *> *&BackEdgeStack) const
    374 {
    375   struct DFSAccounting DFS;
    376   BackEdgeStack = new std::deque<bond *> (getBondCount());
    377   DFS.BackEdgeStack = BackEdgeStack;
    378   MoleculeLeafClass *SubGraphs = new MoleculeLeafClass(NULL);
    379   MoleculeLeafClass *LeafWalker = SubGraphs;
    380   int OldGraphNr = 0;
    381   atom *Walker = NULL;
    382   bond *Binder = NULL;
    383 
    384   if (getAtomCount() == 0)
    385     return SubGraphs;
    386   DoLog(0) && (Log() << Verbose(0) << "Begin of DepthFirstSearchAnalysis" << endl);
    387   init_DFS(DFS);
    388 
    389   for (molecule::const_iterator iter = begin(); iter != end();) {
    390     DFS.Root = *iter;
    391     // (1) mark all edges unused, empty stack, set atom->GraphNr = -1 for all
    392     DFS.AtomStack->clear();
    393 
    394     // put into new subgraph molecule and add this to list of subgraphs
    395     LeafWalker = new MoleculeLeafClass(LeafWalker);
    396     LeafWalker->Leaf = World::getInstance().createMolecule();
    397     LeafWalker->Leaf->AddCopyAtom(DFS.Root);
    398 
    399     OldGraphNr = DFS.CurrentGraphNr;
    400     Walker = DFS.Root;
    401     do { // (10)
    402       do { // (2) set number and Lowpoint of Atom to i, increase i, push current atom
    403         DepthFirstSearchAnalysis_SetWalkersGraphNr(Walker, DFS);
    404 
    405         DepthFirstSearchAnalysis_ProbeAlongUnusedBond(this, Walker, Binder, DFS);
    406 
    407         if (Binder == NULL) {
    408           DoLog(2) && (Log() << Verbose(2) << "No more Unused Bonds." << endl);
    409           break;
    410         } else
    411           Binder = NULL;
    412       } while (1); // (2)
    413 
    414       // if we came from backstepping, yet there were no more unused bonds, we end up here with no Ancestor, because Walker is Root! Then we are finished!
    415       if ((Walker == DFS.Root) && (Binder == NULL))
    416         break;
    417 
    418       DepthFirstSearchAnalysis_CheckForaNewComponent(this, Walker, DFS, LeafWalker);
    419 
    420       DepthFirstSearchAnalysis_CleanRootStackDownTillWalker(this, Walker, Binder, DFS, LeafWalker);
    421 
    422     } while ((DFS.BackStepping) || (Binder != NULL)); // (10) halt only if Root has no unused edges
    423 
    424     // From OldGraphNr to CurrentGraphNr ranges an disconnected subgraph
    425     DoLog(0) && (Log() << Verbose(0) << "Disconnected subgraph ranges from " << OldGraphNr << " to " << DFS.CurrentGraphNr << "." << endl);
    426     LeafWalker->Leaf->Output((ofstream *)&(Log() << Verbose(0)));
    427     DoLog(0) && (Log() << Verbose(0) << endl);
    428 
    429     // step on to next root
    430     while ((iter != end()) && ((*iter)->GraphNr != -1)) {
    431       //Log() << Verbose(1) << "Current next subgraph root candidate is " << (*iter)->Name << "." << endl;
    432       if ((*iter)->GraphNr != -1) // if already discovered, step on
    433         iter++;
    434     }
    435   }
    436   // set cyclic bond criterium on "same LP" basis
    437   CyclicBondAnalysis();
    438 
    439   OutputGraphInfoPerAtom();
    440 
    441   OutputGraphInfoPerBond();
    442 
    443   // free all and exit
    444   DepthFirstSearchAnalysis_Finalize(DFS);
    445   DoLog(0) && (Log() << Verbose(0) << "End of DepthFirstSearchAnalysis" << endl);
    446   return SubGraphs;
    447 }
    448 ;
    449 
    450 /** Scans through all bonds and set bond::Cyclic to true where atom::LowpointNr of both ends is equal: LP criterion.
    451  */
    452 void molecule::CyclicBondAnalysis() const
    453 {
    454   NoCyclicBonds = 0;
    455   for(molecule::const_iterator AtomRunner = begin(); AtomRunner != end(); ++AtomRunner) {
    456     const BondList& ListOfBonds = (*AtomRunner)->getListOfBonds();
    457     for(BondList::const_iterator BondRunner = ListOfBonds.begin();
    458         BondRunner != ListOfBonds.end();
    459         ++BondRunner)
    460       if ((*BondRunner)->leftatom == *AtomRunner)
    461         if ((*BondRunner)->rightatom->LowpointNr == (*BondRunner)->leftatom->LowpointNr) { // cyclic ??
    462           (*BondRunner)->Cyclic = true;
    463           NoCyclicBonds++;
    464         }
    465   }
    466 }
    467 ;
    468 
    469 /** Output graph information per atom.
    470  */
    471 void molecule::OutputGraphInfoPerAtom() const
    472 {
    473   DoLog(1) && (Log() << Verbose(1) << "Final graph info for each atom is:" << endl);
    474   for_each(atoms.begin(),atoms.end(),mem_fun(&atom::OutputGraphInfo));
    475 }
    476 ;
    477 
    478 /** Output graph information per bond.
    479  */
    480 void molecule::OutputGraphInfoPerBond() const
    481 {
    482   DoLog(1) && (Log() << Verbose(1) << "Final graph info for each bond is:" << endl);
    483   for(molecule::const_iterator AtomRunner = begin(); AtomRunner != end(); ++AtomRunner) {
    484     const BondList& ListOfBonds = (*AtomRunner)->getListOfBonds();
    485     for(BondList::const_iterator BondRunner = ListOfBonds.begin();
    486         BondRunner != ListOfBonds.end();
    487         ++BondRunner)
    488       if ((*BondRunner)->leftatom == *AtomRunner) {
    489         const bond *Binder = *BondRunner;
    490         if (DoLog(2)) {
    491           ostream &out = (Log() << Verbose(2));
    492           out << ((Binder->Type == GraphEdge::TreeEdge) ? "TreeEdge " : "BackEdge ") << *Binder << ": <";
    493           out << ((Binder->leftatom->SeparationVertex) ? "SP," : "") << "L" << Binder->leftatom->LowpointNr << " G" << Binder->leftatom->GraphNr << " Comp.";
    494           Binder->leftatom->OutputComponentNumber(&out);
    495           out << " ===  ";
    496           out << ((Binder->rightatom->SeparationVertex) ? "SP," : "") << "L" << Binder->rightatom->LowpointNr << " G" << Binder->rightatom->GraphNr << " Comp.";
    497           Binder->rightatom->OutputComponentNumber(&out);
    498           out << ">." << endl;
    499         }
    500         if (Binder->Cyclic) // cyclic ??
    501           DoLog(3) && (Log() << Verbose(3) << "Lowpoint at each side are equal: CYCLIC!" << endl);
    502       }
    503   }
    504 }
    505 ;
    506 
    507 /** Sets the next component number.
    508  * This is O(N) as the number of bonds per atom is bound.
    509  * \param *vertex atom whose next atom::*ComponentNr is to be set
    510  * \param Nr number to use
    511  */
    512 void molecule::SetNextComponentNumber(atom *vertex, int nr) const
    513 {
    514   size_t i = 0;
    515   if (vertex != NULL) {
    516     const BondList& ListOfBonds = vertex->getListOfBonds();
    517     for (; i < ListOfBonds.size(); i++) {
    518       if (vertex->ComponentNr[i] == -1) { // check if not yet used
    519         vertex->ComponentNr[i] = nr;
    520         break;
    521       } else if (vertex->ComponentNr[i] == nr) // if number is already present, don't add another time
    522         break; // breaking here will not cause error!
    523     }
    524     if (i == ListOfBonds.size()) {
    525       DoeLog(0) && (eLog()<< Verbose(0) << "Error: All Component entries are already occupied!" << endl);
    526       performCriticalExit();
    527     }
    528   } else {
    529     DoeLog(0) && (eLog()<< Verbose(0) << "Error: Given vertex is NULL!" << endl);
    530     performCriticalExit();
    531   }
    532 }
    533 ;
    534 
    535 /** Returns next unused bond for this atom \a *vertex or NULL of none exists.
    536  * \param *vertex atom to regard
    537  * \return bond class or NULL
    538  */
    539 bond * molecule::FindNextUnused(atom *vertex) const
    540 {
    541   const BondList& ListOfBonds = vertex->getListOfBonds();
    542   for (BondList::const_iterator Runner = ListOfBonds.begin();
    543       Runner != ListOfBonds.end();
    544       ++Runner)
    545     if ((*Runner)->IsUsed() == GraphEdge::white)
    546       return ((*Runner));
    547   return NULL;
    548 }
    549 ;
    550 
    551 /** Resets bond::Used flag of all bonds in this molecule.
    552  * \return true - success, false - -failure
    553  */
    554 void molecule::ResetAllBondsToUnused() const
    555 {
    556   for(molecule::const_iterator AtomRunner = begin(); AtomRunner != end(); ++AtomRunner) {
    557     const BondList& ListOfBonds = (*AtomRunner)->getListOfBonds();
    558     for(BondList::const_iterator BondRunner = ListOfBonds.begin();
    559         BondRunner != ListOfBonds.end();
    560         ++BondRunner)
    561       if ((*BondRunner)->leftatom == *AtomRunner)
    562         (*BondRunner)->ResetUsed();
    563   }
    564 }
    565 ;
    566 
    567 /** Output a list of flags, stating whether the bond was visited or not.
    568  * \param *list list to print
    569  */
    570 void OutputAlreadyVisited(int *list)
    571 {
    572   DoLog(4) && (Log() << Verbose(4) << "Already Visited Bonds:\t");
    573   for (int i = 1; i <= list[0]; i++)
    574     DoLog(0) && (Log() << Verbose(0) << list[i] << "  ");
    575   DoLog(0) && (Log() << Verbose(0) << endl);
    576 }
    577 ;
    578135
    579136/** Storing the bond structure of a molecule to file.
    … …  
    755312;
    756313
    757 /** Picks from a global stack with all back edges the ones in the fragment.
    758  * \param **ListOfLocalAtoms array of father atom::Nr to local atom::Nr (reverse of atom::father)
    759  * \param *ReferenceStack stack with all the back egdes
    760  * \param *LocalStack stack to be filled
    761  * \return true - everything ok, false - ReferenceStack was empty
    762  */
    763 bool molecule::PickLocalBackEdges(atom **ListOfLocalAtoms, std::deque<bond *> *&ReferenceStack, std::deque<bond *> *&LocalStack) const
    764 {
    765   bool status = true;
    766   if (ReferenceStack->empty()) {
    767     DoLog(1) && (Log() << Verbose(1) << "ReferenceStack is empty!" << endl);
    768     return false;
    769   }
    770   bond *Binder = ReferenceStack->front();
    771   ReferenceStack->pop_front();
    772   bond *FirstBond = Binder; // mark the first bond, so that we don't loop through the stack indefinitely
    773   atom *Walker = NULL, *OtherAtom = NULL;
    774   ReferenceStack->push_front(Binder);
    775 
    776   do { // go through all bonds and push local ones
    777     Walker = ListOfLocalAtoms[Binder->leftatom->getNr()]; // get one atom in the reference molecule
    778     if (Walker != NULL) { // if this Walker exists in the subgraph ...
    779       const BondList& ListOfBonds = Walker->getListOfBonds();
    780       for (BondList::const_iterator Runner = ListOfBonds.begin();
    781           Runner != ListOfBonds.end();
    782           ++Runner) {
    783         OtherAtom = (*Runner)->GetOtherAtom(Walker);
    784         if (OtherAtom == ListOfLocalAtoms[(*Runner)->rightatom->getNr()]) { // found the bond
    785           LocalStack->push_front((*Runner));
    786           DoLog(3) && (Log() << Verbose(3) << "Found local edge " << *(*Runner) << "." << endl);
    787           break;
    788         }
    789       }
    790     }
    791     ASSERT(!ReferenceStack->empty(), "molecule::PickLocalBackEdges() - ReferenceStack is empty!");
    792     Binder = ReferenceStack->front(); // loop the stack for next item
    793     ReferenceStack->pop_front();
    794     DoLog(3) && (Log() << Verbose(3) << "Current candidate edge " << Binder << "." << endl);
    795     ReferenceStack->push_front(Binder);
    796   } while (FirstBond != Binder);
    797 
    798   return status;
    799 }
    800 ;
    801 
    802314/** Adds a bond as a copy to a given one
    803315 * \param *left leftatom of new bond
    … …  
    891403;
    892404
    893 /** For a given keyset \a *Fragment, checks whether it is connected in the current molecule.
    894  * \param *Fragment Keyset of fragment's vertices
    895  * \return true - connected, false - disconnected
    896  * \note this is O(n^2) for it's just a bug checker not meant for permanent use!
    897  */
    898 bool molecule::CheckForConnectedSubgraph(KeySet *Fragment)
    899 {
    900   atom *Walker = NULL, *Walker2 = NULL;
    901   bool BondStatus = false;
    902   int size;
    903 
    904   DoLog(1) && (Log() << Verbose(1) << "Begin of CheckForConnectedSubgraph" << endl);
    905   DoLog(2) && (Log() << Verbose(2) << "Disconnected atom: ");
    906 
    907   // count number of atoms in graph
    908   size = 0;
    909   for (KeySet::iterator runner = Fragment->begin(); runner != Fragment->end(); runner++)
    910     size++;
    911   if (size > 1)
    912     for (KeySet::iterator runner = Fragment->begin(); runner != Fragment->end(); runner++) {
    913       Walker = FindAtom(*runner);
    914       BondStatus = false;
    915       for (KeySet::iterator runners = Fragment->begin(); runners != Fragment->end(); runners++) {
    916         Walker2 = FindAtom(*runners);
    917         const BondList& ListOfBonds = Walker->getListOfBonds();
    918         for (BondList::const_iterator Runner = ListOfBonds.begin();
    919             Runner != ListOfBonds.end();
    920             ++Runner) {
    921           if ((*Runner)->GetOtherAtom(Walker) == Walker2) {
    922             BondStatus = true;
    923             break;
    924           }
    925           if (BondStatus)
    926             break;
    927         }
    928       }
    929       if (!BondStatus) {
    930         DoLog(0) && (Log() << Verbose(0) << (*Walker) << endl);
    931         return false;
    932       }
    933     }
    934   else {
    935     DoLog(0) && (Log() << Verbose(0) << "none." << endl);
    936     return true;
    937   }
    938   DoLog(0) && (Log() << Verbose(0) << "none." << endl);
    939 
    940   DoLog(1) && (Log() << Verbose(1) << "End of CheckForConnectedSubgraph" << endl);
    941 
    942   return true;
    943 }
    944 
    945 /** Fills a lookup list of father's Atom::Nr -> atom for each subgraph.
    946  * \param *out output stream from debugging
     405/** Fills a lookup list of father's Atom::nr -> atom for each subgraph.
    947406 * \param **&ListOfLocalAtoms Lookup table for each subgraph and index of each atom in global molecule, may be NULL on start, then it is filled
    948407 * \param GlobalAtomCount number of atoms in the complete molecule
Note: See TracChangeset for help on using the changeset viewer.