source: src/Graph/CyclicStructureAnalysis.hpp@ 50e6b7

ForceAnnealing_goodresults ForceAnnealing_tocheck
Last change on this file since 50e6b7 was 83cc3e, checked in by Frederik Heber <heber@…>, 11 years ago

FIX: CyclicStructureAnalysis did not robustly detect all cycles.

  • it depended on the sequence of the back edges. In Coronene most back edges lead to two cycles but at least one back edge is attached to only one cycle.
  • The change is that we now continue after having found a cycle - regardless of whether it is already present or not. This ensures that we find all cycles present.
  • finding a cycle sets however the size of the BFS horizon (we just look for the minimal cycles). This prevents the BFS from stepping through the whole graph.
  • rename CycleBFStoRoot() -> findAllCyclesforBackEdge(), calls RetrieveCycleMembers() on each found cycle (not in operator() anymore).
  • Modified RetrieveCycleMembers() to check whether cycle is present, using IsCyclic checking as a faster mean.
  • operator() dropped NumCycles, is redundantly contained in allcycles.size().
  • Property mode set to 100644
File size: 2.1 KB
Line 
1/*
2 * CyclicStructureAnalysis.hpp
3 *
4 * Created on: Feb 16, 2011
5 * Author: heber
6 */
7
8#ifndef CYCLICSTRUCTUREANALYSIS_HPP_
9#define CYCLICSTRUCTUREANALYSIS_HPP_
10
11// include config.h
12#ifdef HAVE_CONFIG_H
13#include <config.h>
14#endif
15
16#include <deque>
17#include <map>
18#include <vector>
19
20#include "Bond/bond.hpp"
21#include "Bond/GraphEdge.hpp"
22#include "Fragmentation/KeySet.hpp"
23#include "Fragmentation/HydrogenSaturation_enum.hpp"
24#include "Helpers/defs.hpp"
25#include "types.hpp"
26
27class atom;
28class molecule;
29
30class CyclicStructureAnalysis
31{
32public:
33 //!> typedef for specifying a cycle
34 typedef KeySet cycle_t;
35 //!> typedef for specifying many cycles
36 typedef std::vector< cycle_t > cycles_t;
37
38 explicit CyclicStructureAnalysis(const enum HydrogenTreatment _treatment);
39 ~CyclicStructureAnalysis();
40
41 void Reset();
42 void operator()(std::deque<bond::ptr > * BackEdgeStack);
43
44 const std::map<atomId_t, int >& getMinimumRingSize() const;
45
46 /** Getter for all found cycles.
47 *
48 */
49 cycles_t getAllCycles() const {
50 return allcycles;
51 }
52
53private:
54
55 // init or reset
56 void InitNode(atomId_t atom_id);
57 void CleanAllTouched();
58 void InitializeToRoot(atom *&Walker);
59 // performing tasks
60 void findAllCyclesforBackEdge(atom *&OtherAtom, bond::ptr &BackEdge, int &MinRingSize);
61 int RetrieveCycleMembers(atom *&OtherAtom, bond::ptr &BackEdge, int &MinRingSize);
62 cycle_t extractCurrentCycle(bond::ptr &BackEdge);
63 void BFSToNextCycle(atom *Walker);
64 void AssignRingSizetoNonCycleMembers(const int MinRingSize);
65 // output
66 void OutputAlreadyVisited(int *list);
67
68 std::map<atomId_t, atom *> PredecessorList;
69 std::map<atomId_t, int > ShortestPathList;
70 std::map<atomId_t, enum GraphEdge::Shading> ColorList;
71 std::map<atomId_t, int > MinimumRingSize;
72 std::deque<atom *> BFSStack;
73 std::deque<atom *> TouchedStack;
74 int BondOrder;
75 atom *Root;
76
77 //!> container for all found cycles, note that these are global ids
78 cycles_t allcycles;
79
80 //!> whether to treat hydrogen special or not
81 const enum HydrogenTreatment treatment;
82
83 bool BackStepping;
84 int CurrentGraphNr;
85 int ComponentNr;
86};
87
88#endif /* CYCLICSTRUCTUREANALYSIS_HPP_ */
Note: See TracBrowser for help on using the repository browser.