-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathrspr.hpp
157 lines (113 loc) · 7.57 KB
/
rspr.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#ifndef rspr_hpp
#define rspr_hpp
#include <stdio.h>
#include <cstdlib>
#include <string>
#include <cstring>
#include <iostream>
#include <sstream>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include "Forest.hpp"
#include "ClusterForest.hpp"
#include "SPRLCA.hpp"
#include "ClusterInstance.hpp"
#include "SiblingPair.hpp"
#include "UndoMachine.hpp"
using namespace std;
enum RELAXATION {SPR_STRICT, NEGATIVE_RELAXED, ALL_RELAXED};
int rSPR_3_approx_hlpr(Forest *T1, Forest *T2, std::list<SPRNode *> *singletons,
std::list<SPRNode *> *sibling_pairs);
int rSPR_3_approx(Forest *T1, Forest *T2);
int rSPR_worse_3_approx_hlpr(Forest *T1, Forest *T2, std::list<SPRNode *> *singletons, std::list<SPRNode *> *sibling_pairs, Forest **F1, Forest **F2, bool save_forests);
int rSPR_worse_3_approx(Forest *T1, Forest *T2);
int rSPR_worse_3_approx(Forest *T1, Forest *T2, bool sync);
int rSPR_worse_3_approx(SPRNode *subtree, Forest *T1, Forest *T2);
int rSPR_worse_3_approx(SPRNode *subtree, Forest *T1, Forest *T2, bool sync);
int rSPR_worse_3_approx_binary_hlpr(Forest *T1, Forest *T2, std::list<SPRNode *> *singletons, std::list<SPRNode *> *sibling_pairs, Forest **F1, Forest **F2, bool save_forests);
int rSPR_worse_3_approx_binary(Forest *T1, Forest *T2, bool sync);
int rSPR_worse_3_approx_binary(Forest *T1, Forest *T2);
int rSPR_branch_and_bound(Forest *T1, Forest *T2);
int rSPR_branch_and_bound(Forest *T1, Forest *T2, int k);
int rSPR_branch_and_bound_range(Forest *T1, Forest *T2, int end_k);
int rSPR_branch_and_bound_range(Forest *T1, Forest *T2, int start_k, int end_k);
int rSPR_branch_and_bound_hlpr(Forest *T1, Forest *T2, int k,
std::set<SiblingPair> *sibling_pairs, std::list<SPRNode *> *singletons, bool cut_b_only,
std::list<std::pair<Forest,Forest> > *AFs, std::list<SPRNode *> *protected_stack,
int *num_ties);
int rSPR_branch_and_bound_hlpr(Forest *T1, Forest *T2, int k,
std::set<SiblingPair> *sibling_pairs, std::list<SPRNode *> *singletons, bool cut_b_only,
std::list<std::pair<Forest,Forest> > *AFs, std::list<SPRNode *> *protected_stack,
int *num_ties, SPRNode *prev_T1_a, SPRNode *prev_T1_c);
int rSPR_total_approx_distance(SPRNode *T1, std::vector<SPRNode *> &gene_trees);
int rSPR_total_approx_distance(SPRNode *T1, std::vector<SPRNode *> &gene_trees,
int threshold);
int rSPR_total_distance(SPRNode *T1, std::vector<SPRNode *> &gene_trees);
int rSPR_total_distance(SPRNode *T1, std::vector<SPRNode *> &gene_trees,
std::vector<int> *original_scores);
void rSPR_pairwise_distance(SPRNode *T1, std::vector<SPRNode *> &gene_trees);
void rSPR_pairwise_distance(SPRNode *T1, std::vector<SPRNode *> &gene_trees, bool approx);
void rSPR_pairwise_distance(SPRNode *T1, std::vector<SPRNode *> &gene_trees, int start, int end);
void rSPR_pairwise_distance(SPRNode *T1, std::vector<SPRNode *> &gene_trees, int start, int end, bool approx);
void rSPR_pairwise_distance(SPRNode *T1, std::vector<SPRNode *> &gene_trees, int max_spr);
void rSPR_pairwise_distance(SPRNode *T1, std::vector<SPRNode *> &gene_trees, int max_spr, int start, int end);
void rSPR_pairwise_distance_unrooted(SPRNode *T1, std::vector<SPRNode *> &gene_trees);
void rSPR_pairwise_distance_unrooted(SPRNode *T1, std::vector<SPRNode *> &gene_trees, int start, int end);
void rSPR_pairwise_distance_unrooted(SPRNode *T1, std::vector<SPRNode *> &gene_trees, bool approx);
void rSPR_pairwise_distance_unrooted(SPRNode *T1, std::vector<SPRNode *> &gene_trees, int start, int end, bool approx);
int rSPR_total_distance_unrooted(SPRNode *T1, std::vector<SPRNode *> &gene_trees, int threshold);
int rSPR_total_distance_unrooted(SPRNode *T1, std::vector<SPRNode *> &gene_trees, int threshold, std::vector<int> *original_scores);
int rSPR_branch_and_bound_simple_clustering(SPRNode *T1, SPRNode *T2, Forest **out_F1, Forest **out_F2);
int rSPR_branch_and_bound_simple_clustering(SPRNode *T1, SPRNode *T2, bool verbose, std::map<std::string, int> *label_map, std::map<int, std::string> *reverse_label_map);
int rSPR_branch_and_bound_simple_clustering(SPRNode *T1, SPRNode *T2, bool verbose, std::map<std::string, int> *label_map, std::map<int, std::string> *reverse_label_map, int min_k, int max_k);
int rSPR_branch_and_bound_simple_clustering(SPRNode *T1, SPRNode *T2);
int rSPR_branch_and_bound_simple_clustering(SPRNode *T1, SPRNode *T2, bool verbose);
int rSPR_branch_and_bound_simple_clustering(SPRNode *T1, SPRNode *T2, bool verbose, int min_k, int max_k);
int rSPR_branch_and_bound_simple_clustering(SPRNode *T1, SPRNode *T2, bool verbose, std::map<std::string, int> *label_map, std::map<int, std::string> *reverse_label_map, int min_k, int max_k, Forest **out_F1, Forest **out_F2);
void reduction_leaf(Forest *T1, Forest *T2);
void reduction_leaf(Forest *T1, Forest *T2, UndoMachine *um);
bool chain_match(SPRNode *T1_SPRNode, SPRNode *T2_SPRNode, SPRNode *T2_SPRNode_end);
bool is_nonbranching(Forest *T1, Forest *T2, SPRNode *T1_a, SPRNode *T1_c, SPRNode *T2_a, SPRNode *T2_c);
SPRNode *find_subtree_of_approx_distance(SPRNode *n, Forest *F1, Forest *F2, int target_size);
SPRNode *find_subtree_of_approx_distance_hlpr(SPRNode *n, Forest *F1, Forest *F2, int target_size);
SPRNode *find_best_root(SPRNode *T1, SPRNode *T2);
double find_best_root_acc(SPRNode *T1, SPRNode *T2);
void find_best_root_hlpr(SPRNode *T2, int pre_separator, int group_1_total,
int group_2_total, SPRNode **best_root, double *best_root_b_acc);
void find_best_root_hlpr(SPRNode *n, int pre_separator, int group_1_total,
int group_2_total, SPRNode **best_root, double *best_root_b_acc,
int *p_group_1_descendants, int *p_group_2_descendants, int *num_ties);
bool contains_bipartition(SPRNode *n, int pre_start, int pre_end,
int group_1_total, int group_2_total, int *p_group_1_descendants,
int *p_group_2_descendants);
bool outgroup_root(SPRNode *T, std::set<std::string, StringCompare> outgroup);
bool outgroup_root(SPRNode *n, std::vector<int> &num_in, std::vector<int> &num_out);
bool outgroup_reroot(SPRNode *n, std::vector<int> &num_in, std::vector<int> &num_out);
void count_in_out(SPRNode *n, std::vector<int> &num_in, std::vector<int> &num_out,
std::set<std::string, StringCompare> &outgroup);
/*Joel's part*/
int rSPR_branch_and_bound_simple_clustering(Forest *T1, Forest *T2, bool verbose, std::map<std::string, int> *label_map,std::map<int, std::string> *reverse_label_map);
int rSPR_branch_and_bound_simple_clustering(Forest *T1, Forest *T2);
int rSPR_branch_and_bound_simple_clustering(Forest *T1, Forest *T2, bool verbose);
int rSPR_total_distance(Forest *T1, std::vector<SPRNode *> &gene_trees);
int rSPR_worse_3_approx_distance_only(Forest *T1, Forest *T2);
class ProblemSolution {
public:
std::string T1;
std::string T2;
int k;
ProblemSolution(Forest *t1, Forest *t2, int new_k)
{
T1 = t1->str();
T2 = t2->str();
k = new_k;
}
};
void add_sibling_pair(std::set<SiblingPair> *sibling_pairs, SPRNode *a, SPRNode *c, UndoMachine *um);
SiblingPair pop_sibling_pair(std::set<SiblingPair> *sibling_pairs, UndoMachine *um);
SiblingPair pop_sibling_pair(std::set<SiblingPair>::iterator s, std::set<SiblingPair> *sibling_pairs, UndoMachine *um);
bool chain_match(SPRNode *T1_SPRNode, SPRNode *T2_SPRNode, SPRNode *T2_SPRNode_end);
#endif /* rspr_hpp */