-
Notifications
You must be signed in to change notification settings - Fork 0
/
analysis.py
125 lines (112 loc) · 4.71 KB
/
analysis.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
"""
----------- TO RUN -----------------
python analysis.py <vertex count*>
where <vertex count*> = {3, 4, 5, 6}
note: Before running, run optimalsolutions.py first to generate the inputs and optimal solutions
"""
import sys, os
from ast import literal_eval
sys.path.append('Utils')
from Analysis_Utils import isTreePoset, areTreePosets, isAllConnected, binaryToCover, covered
args = sys.argv
#
with open(f'optsol/trees/{args[1]}treesoptsol.txt', 'r') as optimal_file, open(f'outputs/output_{args[1]}.txt', 'r') as HeuristicOutput_file:
#Optimal Solution Data
inputs = []
optcost = []
optsol = []
insert_optsols = 0
for line in optimal_file:
if line[:7] == "Input: ":
inputs.append(literal_eval(line[7:-1]))
elif line[:23] == "Optimal solution cost: ":
optcost.append(int(line[23:]))
insert_optsols = int(line[23:])
elif line == "\n":
continue
else:
if insert_optsols == optcost[-1] and line[0] == '[': #first poset is added to the list of optimal solutions
lst = literal_eval(line)
optsol.append([])
optsol[-1].append(lst)
insert_optsols -= 1 #decrement until 0 (all posets are added)
else:
#print(insert_optsols)
lst = literal_eval(line)
optsol[-1].append(lst) #n + 1 posets are added to the latest group of posets added
insert_optsols -= 1
n = len(str(inputs[0][0]))
#Heuristic data
heuristicsol = []
for line in HeuristicOutput_file:
if line[:7] == "Input: ":
continue
elif line[:4] == "P1: ":
#first poset is added to the list of heuristic solutions
start = line.index('[')
lst = literal_eval(line[start:])
lst = binaryToCover(lst, n)
heuristicsol.append([])
heuristicsol[-1].append(lst)
elif line == "\n":
continue
else:
start = line.index('[')
lst = literal_eval(line[start:])
lst = binaryToCover(lst, n)
heuristicsol[-1].append(lst)
#write to a new file <vertex>analysis.py on directory /analysis
#write analysis per input in this format:
#Input: [123, 132]
#Optimal Solution: [[(1, 2), (1, 3)]]
#Heuristic Solution: [[(1, 2), (1, 3)]]
#Analysis: FEASIBLE - OPTIMAL
# ... UNTIL EOF
#SUMMARY
#Total Number of Inputs:
#Total Number of FEASIBLE Heuristic Solutions:
#Total Number of Optimal Heuristic Solutions:
if not os.path.exists("analysis/"):
os.makedirs("analysis/")
output = open(f"analysis/{args[1]}analysis.txt", "w")
#for summary
len_inputs = len(inputs)
Feasible = 0
optimal = 0
not_optimal = []
performanceRatio = 0
for (input, cost, O_sol, H_sol) in zip(inputs, optcost, optsol, heuristicsol):
output.write("Input: "+ str(input)+"\n")
output.write("Optimal Solution: "+ str(O_sol)+"\n")
output.write("Heuristic Solution: "+ str(H_sol)+"\n")
if areTreePosets(H_sol) and isAllConnected(H_sol, n) and len(H_sol) == cost and covered(H_sol) == input:
output.write("Analysis: FEASIBLE - OPTIMAL\n")
Feasible += 1
optimal += 1
performanceRatio +=1
elif areTreePosets(H_sol) and isAllConnected(H_sol, n) and len(H_sol) > cost and covered(H_sol) == input:
diff_cost = len(H_sol) - cost
not_optimal.append(diff_cost)
Feasible += 1
performanceRatio += len(H_sol) / cost
output.write("Analysis: FEASIBLE - NOT OPTIMAL\n")
#output.write("Heuristic_Cost - Optimal_Cost: "+str(diff_cost)+"\n")
else:
output.write("Analysis: NOT FEASIBLE - NOT OPTIMAL\n")
output.write("Output: "+ str(covered(H_sol))+"\n")
output.write("\n")
if len(not_optimal) == 0:
average_diff_not_optimal = 0
max_not_optimal = 0
else:
average_diff_not_optimal = sum(not_optimal)/len(not_optimal)
max_not_optimal = max(not_optimal)
output.write("Summary\n")
output.write("Total Number of Inputs: "+str(len_inputs)+"\n")
output.write("Total Number of Feasible Heuristic Solutions: "+str(Feasible)+"\n")
output.write("Total Number of Optimal Heuristic Solutions: "+str(optimal)+"\n")
#output.write("Average difference in Heuristic Cost and Optimal Cost: "+str(average_diff_not_optimal)+"\n")
#output.write("Maximum difference in Heuristic Cost and Optimal Cost: "+str(max_not_optimal)+"\n")
output.write("Approximation Error: "+str((performanceRatio/len_inputs))+"\n")
output.close
print("FINISHED ANALYSING HEURISTIC")