-
Notifications
You must be signed in to change notification settings - Fork 0
/
Conflict_Detect.py
262 lines (240 loc) · 10.9 KB
/
Conflict_Detect.py
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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
#!/usr/bin/env python
import Header
from Header import *
import UtilFunc
from UtilFunc import *
#-------------------------------------------------------
"""
this function checks whether the current relation (given as an input) is feasible to the input supertree configuration
if the current relation is already existing in the supertree, then this function returns 2
if the current relation produces a cycle to the existing configuration of the final supertree, then it returns 1
otherwise the function returns 0
"""
def Possible_Conflict_Curr_Reln(clust1, clust2, Reachability_Graph_Mat, target_reln_type, Output_Text_File):
if (target_reln_type == RELATION_R2):
src_taxa_clust_idx = clust2
dest_taxa_clust_idx = clust1
else:
src_taxa_clust_idx = clust1
dest_taxa_clust_idx = clust2
#--------------------------------------------------------------------
"""
check whether the cluster pair is already resolved
"""
"""
first check whether clust1 = clust2 - same cluster
"""
if (src_taxa_clust_idx == dest_taxa_clust_idx):
if (DEBUG_LEVEL >= 2):
fp = open(Output_Text_File, 'a')
fp.write('\n already in same cluster index')
fp.close()
return 1
"""
we find the indices of the reachability matrix corresponding to individual cluster indices
"""
reach_mat_src_taxa_clust_idx = CURRENT_CLUST_IDX_LIST.index(src_taxa_clust_idx)
reach_mat_dest_taxa_clust_idx = CURRENT_CLUST_IDX_LIST.index(dest_taxa_clust_idx)
"""
case 1 - if the clusters are already related (depicted in the reachability matrix) then return 1
"""
if (Reachability_Graph_Mat[reach_mat_dest_taxa_clust_idx][reach_mat_src_taxa_clust_idx] > 0) or \
(Reachability_Graph_Mat[reach_mat_src_taxa_clust_idx][reach_mat_dest_taxa_clust_idx] > 0):
if (DEBUG_LEVEL >= 2):
fp = open(Output_Text_File, 'a')
if (Reachability_Graph_Mat[reach_mat_src_taxa_clust_idx][reach_mat_dest_taxa_clust_idx] == 1):
fp.write('\n target_reln_type: ' + str(target_reln_type) + ' already related via relation r1')
elif (Reachability_Graph_Mat[reach_mat_src_taxa_clust_idx][reach_mat_dest_taxa_clust_idx] == 2):
fp.write('\n target_reln_type: ' + str(target_reln_type) + ' already related via relation r4')
elif (Reachability_Graph_Mat[reach_mat_dest_taxa_clust_idx][reach_mat_src_taxa_clust_idx] == 1):
fp.write('\n target_reln_type: ' + str(target_reln_type) + ' already related via relation r2')
fp.close()
return 2
#--------------------------------------------------------------------
# check for the transitive conflict
if (target_reln_type == RELATION_R2) or (target_reln_type == RELATION_R1):
"""
if A->B is to be established
and there exists D->A
then if B->D or B><D then return a conflict
"""
for x in Cluster_Info_Dict[src_taxa_clust_idx]._GetClustRelnList(RELATION_R2):
if (Reachability_Graph_Mat[reach_mat_dest_taxa_clust_idx][CURRENT_CLUST_IDX_LIST.index(x)] > 0): #== 1):
if (DEBUG_LEVEL >= 2):
fp = open(Output_Text_File, 'a')
fp.write('\n possible conflict - case 1 - target: ' + str(src_taxa_clust_idx) + '->' + str(dest_taxa_clust_idx) + \
' given ' + str(x) + '->' + str(src_taxa_clust_idx) + ' and ' + str(dest_taxa_clust_idx) + '-> / ><' + str(x))
fp.close()
return 1
"""
if A->B is to be established
and there exists B->E
then if E->A or E><A then return a conflict
"""
for x in Cluster_Info_Dict[dest_taxa_clust_idx]._GetClustRelnList(RELATION_R1):
if (Reachability_Graph_Mat[CURRENT_CLUST_IDX_LIST.index(x)][reach_mat_src_taxa_clust_idx] > 0): #== 1):
if (DEBUG_LEVEL >= 2):
fp = open(Output_Text_File, 'a')
fp.write('\n possible conflict - case 2 - target: ' + str(src_taxa_clust_idx) + '->' + str(dest_taxa_clust_idx) + \
' given ' + str(dest_taxa_clust_idx) + '->' + str(x) + ' and ' + str(x) + '-> / ><' + str(src_taxa_clust_idx))
fp.close()
return 1
"""
if A->B is to be established
and there exists D->A and B->E
then if E->D or E=D or E><D then return a conflict
"""
for x in Cluster_Info_Dict[src_taxa_clust_idx]._GetClustRelnList(RELATION_R2):
for y in Cluster_Info_Dict[dest_taxa_clust_idx]._GetClustRelnList(RELATION_R1):
if (x == y) or (Reachability_Graph_Mat[CURRENT_CLUST_IDX_LIST.index(y)][CURRENT_CLUST_IDX_LIST.index(x)] > 0): #== 1):
if (DEBUG_LEVEL >= 2):
fp = open(Output_Text_File, 'a')
fp.write('\n possible conflict - case 3 - target: ' + str(src_taxa_clust_idx) + '->' + str(dest_taxa_clust_idx) + \
' given ' + str(x) + '->' + str(src_taxa_clust_idx) + ' and ' \
+ str(dest_taxa_clust_idx) + '->' + str(y) + ' and ' + str(y) + '-> / = / ><' + str(x))
fp.close()
return 1
"""
if A->B is to be established
and there exists D><A
then it would be D><B afterwards
so if there is D->B, B->D or D=B then return a conflict
"""
for x in Cluster_Info_Dict[src_taxa_clust_idx]._GetClustRelnList(RELATION_R4):
if (dest_taxa_clust_idx == x) \
or (Reachability_Graph_Mat[CURRENT_CLUST_IDX_LIST.index(x)][reach_mat_dest_taxa_clust_idx] == 1) \
or (Reachability_Graph_Mat[reach_mat_dest_taxa_clust_idx][CURRENT_CLUST_IDX_LIST.index(x)] == 1):
#if (dest_taxa_clust_idx == x):
if (DEBUG_LEVEL >= 2):
fp = open(Output_Text_File, 'a')
fp.write('\n possible conflict - case 4 - target: ' + str(src_taxa_clust_idx) + '->' + str(dest_taxa_clust_idx) + \
' given ' + str(src_taxa_clust_idx) + '><' + str(x) + ' and ' + str(x) + '-> / = / <-' + str(dest_taxa_clust_idx))
fp.close()
return 1
"""
if A->B is to be established
and there exists D><A
then for all B->E
it would be D><E afterwards
so if D->E or E->D or D=E then return a conflict
"""
for x in Cluster_Info_Dict[src_taxa_clust_idx]._GetClustRelnList(RELATION_R4):
for y in Cluster_Info_Dict[dest_taxa_clust_idx]._GetClustRelnList(RELATION_R1):
if (x == y) \
or (Reachability_Graph_Mat[CURRENT_CLUST_IDX_LIST.index(y)][CURRENT_CLUST_IDX_LIST.index(x)] == 1) \
or (Reachability_Graph_Mat[CURRENT_CLUST_IDX_LIST.index(x)][CURRENT_CLUST_IDX_LIST.index(y)] == 1):
#if (x == y):
if (DEBUG_LEVEL >= 2):
fp = open(Output_Text_File, 'a')
fp.write('\n possible conflict - case 5 - target: ' + str(src_taxa_clust_idx) + '->' + str(dest_taxa_clust_idx) + \
' given ' + str(src_taxa_clust_idx) + '><' + str(x) + \
' and ' + str(dest_taxa_clust_idx) + '->' + str(y) + ' and ' + str(x) + '-> / = / <-' + str(y))
fp.close()
return 1
elif (target_reln_type == RELATION_R3):
"""
if A=B is to be established
and there exists B->D
then if D->A or D><A or D=A then return a conflict
"""
for x in Cluster_Info_Dict[dest_taxa_clust_idx]._GetClustRelnList(RELATION_R1):
if (x == src_taxa_clust_idx) or (Reachability_Graph_Mat[CURRENT_CLUST_IDX_LIST.index(x)][reach_mat_src_taxa_clust_idx] > 0): #== 1):
if (DEBUG_LEVEL >= 2):
fp = open(Output_Text_File, 'a')
fp.write('\n possible conflict - case 6')
fp.close()
return 1
"""
if A=B is to be established
and there exists D->B
then if A->D or A><D or A=D then return a conflict
"""
for x in Cluster_Info_Dict[dest_taxa_clust_idx]._GetClustRelnList(RELATION_R2):
if (x == src_taxa_clust_idx) or (Reachability_Graph_Mat[reach_mat_src_taxa_clust_idx][CURRENT_CLUST_IDX_LIST.index(x)] > 0): #== 1):
if (DEBUG_LEVEL >= 2):
fp = open(Output_Text_File, 'a')
fp.write('\n possible conflict - case 7')
fp.close()
return 1
"""
if A=B is to be established
and there exists B><D
then if A->D or D->A or A=D then return a conflict
"""
for x in Cluster_Info_Dict[dest_taxa_clust_idx]._GetClustRelnList(RELATION_R4):
if (x == src_taxa_clust_idx) or (Reachability_Graph_Mat[reach_mat_src_taxa_clust_idx][CURRENT_CLUST_IDX_LIST.index(x)] == 1) \
or (Reachability_Graph_Mat[CURRENT_CLUST_IDX_LIST.index(x)][reach_mat_src_taxa_clust_idx] == 1):
#if (x == src_taxa_clust_idx):
if (DEBUG_LEVEL >= 2):
fp = open(Output_Text_File, 'a')
fp.write('\n possible conflict - case 8')
fp.close()
return 1
"""
if A=B is to be established
and there exists A->D
then if D->B or D><B or D=B then return a conflict
"""
for x in Cluster_Info_Dict[src_taxa_clust_idx]._GetClustRelnList(RELATION_R1):
if (x == dest_taxa_clust_idx) or (Reachability_Graph_Mat[CURRENT_CLUST_IDX_LIST.index(x)][reach_mat_dest_taxa_clust_idx] > 0): #== 1):
if (DEBUG_LEVEL >= 2):
fp = open(Output_Text_File, 'a')
fp.write('\n possible conflict - case 9')
fp.close()
return 1
"""
if A=B is to be established
and there exists D->A
then if B->D or B><D or B=D then return a conflict
"""
for x in Cluster_Info_Dict[src_taxa_clust_idx]._GetClustRelnList(RELATION_R2):
if (x == dest_taxa_clust_idx) or (Reachability_Graph_Mat[reach_mat_dest_taxa_clust_idx][CURRENT_CLUST_IDX_LIST.index(x)] > 0): #== 1):
if (DEBUG_LEVEL >= 2):
fp = open(Output_Text_File, 'a')
fp.write('\n possible conflict - case 10')
fp.close()
return 1
"""
if A=B is to be established
and there exists A><D
then if D->B or B->D or B=D then return a conflict
"""
for x in Cluster_Info_Dict[src_taxa_clust_idx]._GetClustRelnList(RELATION_R4):
if (x == dest_taxa_clust_idx) or (Reachability_Graph_Mat[reach_mat_dest_taxa_clust_idx][CURRENT_CLUST_IDX_LIST.index(x)] == 1) \
or (Reachability_Graph_Mat[CURRENT_CLUST_IDX_LIST.index(x)][reach_mat_dest_taxa_clust_idx] == 1):
#if (x == dest_taxa_clust_idx):
if (DEBUG_LEVEL >= 2):
fp = open(Output_Text_File, 'a')
fp.write('\n possible conflict - case 11')
fp.close()
return 1
else: #if (target_reln_type == RELATION_R4):
"""
construct the out neighborhood of src_cluster
it will contain the cluster itself and all the other clusters connected via out edges from this cluster
"""
src_clust_out_neighb = []
src_clust_out_neighb.append(src_taxa_clust_idx)
src_clust_out_neighb.extend(Cluster_Info_Dict[src_taxa_clust_idx]._GetClustRelnList(RELATION_R1))
"""
construct the out neighborhood of dest cluster
it will contain the cluster itself and all the other clusters connected via out edges from this cluster
"""
dest_clust_out_neighb = []
dest_clust_out_neighb.append(dest_taxa_clust_idx)
dest_clust_out_neighb.extend(Cluster_Info_Dict[dest_taxa_clust_idx]._GetClustRelnList(RELATION_R1))
"""
if mutually any pair of taxa belonging to respective out edge clusters
are themselves related via any relationships other than NO EDGE then this connection is not possible
"""
for x in src_clust_out_neighb:
for y in dest_clust_out_neighb:
if (x == y) or (Reachability_Graph_Mat[CURRENT_CLUST_IDX_LIST.index(y)][CURRENT_CLUST_IDX_LIST.index(x)] == 1) \
or (Reachability_Graph_Mat[CURRENT_CLUST_IDX_LIST.index(x)][CURRENT_CLUST_IDX_LIST.index(y)] == 1):
#if (x == y):
if (DEBUG_LEVEL >= 2):
fp = open(Output_Text_File, 'a')
fp.write('\n possible conflict - case 12')
fp.close()
return 1
return 0