ARB
SyncRoot.hxx
Go to the documentation of this file.
1 // ========================================================= //
2 // //
3 // File : SyncRoot.hxx //
4 // Purpose : Sync roots of trees //
5 // //
6 // Coded by Ralf Westram (coder@reallysoft.de) in May 20 //
7 // http://www.arb-home.de/ //
8 // //
9 // ========================================================= //
10 
11 #ifndef SYNCROOT_HXX
12 #define SYNCROOT_HXX
13 
14 #ifndef CT_COMMON_HXX
15 #include "CT_common.hxx"
16 #endif
17 #ifndef _GLIBCXX_VECTOR
18 #include <vector>
19 #endif
20 #ifndef ERRORORTYPE_H
21 #include <ErrorOrType.h>
22 #endif
23 #ifndef MATRIX_H
24 #include <matrix.h>
25 #endif
26 
28 
31 
34 
36 
37 typedef std::vector<ConstSizeAwareTreePtr> ConstSizeAwareTreeVector;
38 
39 class Multiroot {
41  mutable symmetric_matrix<int> distance; // pairwise
42 
43 #if defined(ASSERTION_USED)
44  bool is_valid() const {
45  if (size()<2) return false; // too small
46  for (int i = 0; i<size(); ++i) {
47  if (!node[i]) return false;
48  if (node[i]->is_root_node()) return false;
49  }
50  return true;
51  }
52 #endif
53 
54  int lazy_eval_distance(const RootSynchronizer& rsync, int i, int j) const;
55 
56 public:
57  static const int UNKNOWN_DISTANCE = -1;
58 
59  Multiroot(const TreeContainer& trees) :
60  node(trees.get_tree_count(), NULp),
61  distance(trees.get_tree_count())
62  {
63  for (int i = 0; i<size(); ++i) {
64  node[i] = trees.get_tree(i)->get_leftson(); // take any son
65  for (int j = 0; j<i; ++j) {
66  distance.set(i, j, UNKNOWN_DISTANCE);
67  }
68  }
69  arb_assert(is_valid());
70  }
71  Multiroot(const Multiroot& other) :
72  node(other.node),
73  distance(other.size())
74  {
75  for (int i = 0; i<size(); ++i) {
76  for (int j = 0; j<i; ++j) {
77  distance.set(i, j, other.distance.get(i, j));
78  }
79  }
80  }
81 
82  int size() const { return distance.size(); }
83  int distanceSum(const RootSynchronizer& rsync) const;
84  int distanceToCenterSum(const RootSynchronizer& rsync) const;
85  int singleTreeDistanceSum(const RootSynchronizer& rsync, int idx);
86 
88  if (idx<0 || size_t(idx)>=node.size()) {
89  return NULp;
90  }
91  return node[idx];
92  }
93 
94  void replace_node(int idx, ConstSizeAwareTreePtr newNode);
95 };
96 
99 
101  ConstStrArray species_names;
102  SmartPtr<SpeciesSpace> speciesSpacePtr;
103  SmartPtr<TreeParts> treePartsPtr;
104 
105  std::vector<DeconstructedTreePtr> dtree; // all involved trees
106 
107  GB_ERROR deconstructTree(int treeIdx, bool provideProgress);
108 
109  bool has_deconstructed_tree(int idx) const {
110  return valid_tree_index(idx) && dtree.size()>size_t(idx) && dtree[idx].isSet();
111  }
112 
113  MultirootPtr find_better_multiroot(const Multiroot& start, int best_distSum, int best_centerDist, int *movesPerTree, arb_progress *progress = NULp);
114 
115 public:
117 
118  int add(SizeAwareTree*& tree, const char *treename) {
119  arb_assert(!deconstructionPhase()); // now its too late to add new trees
120  return TreeContainer::add(tree, treename);
121  }
122  SizeAwareTree *take_tree(int idx) {
123  SizeAwareTree *t = TreeContainer::take_tree(idx);
124  if (deconstructionPhase()) {
125  dtree[idx].setNull();
126  }
127  return t;
128  }
129 
131  bool deconstructionPhase() const {
132  return speciesSpacePtr.isSet();
133  }
134  GB_ERROR deconstruct_all_trees(bool provideProgress);
135  bool allTreesDeconstructed() const {
137  const int treeCount = get_tree_count();
138  for (int t = 0; t<treeCount; ++t) if (!has_deconstructed_tree(t)) return false;
139  return true;
140  }
141 
142  ErrorOrSizeAwareTreePtr find_best_root_candidate(int inTree, int accordingToTree, int& best_dist, bool provideProgress); // find root in 'inTree' with best match to root of tree 'accordingToTree'
143 
146  ErrorOrMultirootPtr find_good_roots_for_trees(const int MAX_DEPTH, arb_progress *progress = NULp);
147 
148  // some helper methods (used to port TEST_part_distance to RootSynchronizer):
151  return *speciesSpacePtr;
152  }
154  GB_ERROR error = deconstructTree(treeIdx, false); // lazy eval
155  return ErrorOrDeconstructedTreePtr(error, &*dtree[treeIdx]);
156  }
157  const PART *get_tree_PART(int treeIdx) const {
159  return treePartsPtr->get_tree_PART(treeIdx);
160  }
161  const PART *get_edge_PART(int treeIdx, const SizeAwareTree *sonOfEdge) const {
162  arb_assert(allTreesDeconstructed()); // otherwise dtree contains nothing yet
163  arb_assert(valid_tree_index(treeIdx));
164  arb_assert(!sonOfEdge->is_root_node());
165  return dtree[treeIdx]->find_part(sonOfEdge);
166  }
167 
168  int calcEdgeDistance(int i1, const SizeAwareTree *n1, int i2, const SizeAwareTree *n2) const;
169  int calcTreeDistance(int i1, int i2) const; // minimal possible distance between (any edges) of two trees
170  int minDistanceSum() const; // sum of pairwise distances between all trees
171 
172  static void find_best_matching_PART_in(int& best_dist, int &best_idx, const PART *part, const DeconstructedTree& in, const PART *tree_part, const PART *tree_in, bool provideProgress);
173  static void find_worst_matching_PART_in(int& worst_dist, int &worst_idx, const PART *part, const DeconstructedTree& in, const PART *tree_part, const PART *tree_in);
174 };
175 
176 #else
177 #error SyncRoot.hxx included twice
178 #endif // SYNCROOT_HXX
const PART * get_edge_PART(int treeIdx, const SizeAwareTree *sonOfEdge) const
Definition: SyncRoot.hxx:161
#define arb_assert(cond)
Definition: arb_assert.h:245
const char * GB_ERROR
Definition: arb_core.h:25
void beginDeconstructionPhase()
Definition: SyncRoot.cxx:18
int distanceSum(const RootSynchronizer &rsync) const
Definition: SyncRoot.cxx:484
static void find_best_matching_PART_in(int &best_dist, int &best_idx, const PART *part, const DeconstructedTree &in, const PART *tree_part, const PART *tree_in, bool provideProgress)
Definition: SyncRoot.cxx:116
const SpeciesSpace & get_SpeciesSpace() const
Definition: SyncRoot.hxx:149
const SizeAwareTree * get_tree(int idx) const
Definition: CT_common.hxx:111
void set(size_t i, size_t j, T val)
Definition: matrix.h:46
bool deconstructionPhase() const
Definition: SyncRoot.hxx:131
Multiroot(const Multiroot &other)
Definition: SyncRoot.hxx:71
static void find_worst_matching_PART_in(int &worst_dist, int &worst_idx, const PART *part, const DeconstructedTree &in, const PART *tree_part, const PART *tree_in)
Definition: SyncRoot.cxx:147
int calcEdgeDistance(int i1, const SizeAwareTree *n1, int i2, const SizeAwareTree *n2) const
Definition: SyncRoot.cxx:436
ErrorOrSizeAwareTreePtr find_best_root_candidate(int inTree, int accordingToTree, int &best_dist, bool provideProgress)
Definition: SyncRoot.cxx:58
ErrorOrMultirootPtr find_good_roots_for_trees(const int MAX_DEPTH, arb_progress *progress=NULp)
Definition: SyncRoot.cxx:297
size_t get_tree_count() const
Definition: CT_common.hxx:107
int add(SizeAwareTree *&tree, const char *treename)
Definition: CT_common.hxx:129
int singleTreeDistanceSum(const RootSynchronizer &rsync, int idx)
Definition: SyncRoot.cxx:506
const PART * get_tree_PART(int treeIdx) const
Definition: SyncRoot.hxx:157
static HelixNrInfo * start
ErrorOrDeconstructedTreePtr get_DeconstructedTree(int treeIdx)
Definition: SyncRoot.hxx:153
Multiroot(const TreeContainer &trees)
Definition: SyncRoot.hxx:59
SmartPtr< DeconstructedTree > DeconstructedTreePtr
Definition: SyncRoot.hxx:27
int distanceToCenterSum(const RootSynchronizer &rsync) const
Definition: SyncRoot.cxx:496
int add(SizeAwareTree *&tree, const char *treename)
Definition: SyncRoot.hxx:118
bool isSet() const
test if SmartPtr is not NULp
Definition: smartptr.h:245
Generic smart pointer.
Definition: smartptr.h:149
static void error(const char *msg)
Definition: mkptypes.cxx:96
GB_ERROR deconstruct_all_trees(bool provideProgress)
Definition: SyncRoot.cxx:274
ErrorOr< MultirootPtr > ErrorOrMultirootPtr
Definition: SyncRoot.hxx:98
SizeAwareTree * take_tree(int idx)
Definition: CT_common.hxx:112
ErrorOr< ConstSizeAwareTreePtr > ErrorOrSizeAwareTreePtr
Definition: SyncRoot.hxx:32
RefPtr< const SizeAwareTree > ConstSizeAwareTreePtr
Definition: SyncRoot.hxx:29
Definition: CT_part.hxx:62
MultirootPtr get_innermost_edges() const
Definition: SyncRoot.cxx:419
ErrorOrMultirootPtr get_current_roots() const
Definition: SyncRoot.cxx:407
RefPtr< const DeconstructedTree > ConstDeconstructedTreePtr
Definition: SyncRoot.hxx:30
int size() const
Definition: SyncRoot.hxx:82
std::vector< ConstSizeAwareTreePtr > ConstSizeAwareTreeVector
Definition: SyncRoot.hxx:35
const PART * get_tree_PART(int idx) const
Definition: CT_common.hxx:263
bool valid_tree_index(int idx) const
Definition: CT_common.hxx:108
bool allTreesDeconstructed() const
Definition: SyncRoot.hxx:135
ErrorOr< ConstDeconstructedTreePtr > ErrorOrDeconstructedTreePtr
Definition: SyncRoot.hxx:33
void replace_node(int idx, ConstSizeAwareTreePtr newNode)
Definition: SyncRoot.cxx:517
#define NULp
Definition: cxxforward.h:97
int minDistanceSum() const
Definition: SyncRoot.cxx:464
size_t size() const
Definition: matrix.h:63
T get(size_t i, size_t j) const
Definition: matrix.h:49
SmartPtr< Multiroot > MultirootPtr
Definition: SyncRoot.hxx:97
SizeAwareTree * take_tree(int idx)
Definition: SyncRoot.hxx:122
static const int UNKNOWN_DISTANCE
Definition: SyncRoot.hxx:57
ConstSizeAwareTreePtr get_node(int idx) const
Definition: SyncRoot.hxx:87
int calcTreeDistance(int i1, int i2) const
Definition: SyncRoot.cxx:457