minimum-spanning-tree-algorithms/compare_results.py at main · uni-projects-master/minimum-spanning-tree-algorithms · GitHub

Name: minimum-spanning-tree-algorithms/compare_results.py at main · uni-projects-master/minimum-spanning-tree-algorithms · GitHub
Rating: 4.8 (9899 reviews)
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
importmatplotlib.pyplotasplt
importmath


if__name__=='__main__':
# --------------------------------------READ RESULTS FROM .txt FILE------------------------------------------------
f=open('results/kruskal_naive_results.txt')
f.readline()
sizes= []
naive_kruskal_time= []

forlineinf:
result=line.split()
sizes.append(int(result[0]))
naive_kruskal_time.append(int(result[1]))
f.close()

f=open('results/kruskal_union_find_results.txt')
f.readline()
union_find_kruskal_time= []
forlineinf:
result=line.split()
union_find_kruskal_time.append(int(result[1]))
f.close()

f=open('results/prim_results.txt')
f.readline()
prim_time= []
forlineinf:
result=line.split()
prim_time.append(int(result[1]))
f.close()

# --------------------------------------FIRST FIGURE: KRUSKAL NAIVE------------------------------------------------
plt.plot(sizes, naive_kruskal_time, label='Naive Kruskal')

c_estimates_naive= [naive_kruskal_time[i] /sizes[i] foriinrange(len(sizes)-1)]
withopen('results/c_estimates_naive.txt', 'w+') asf:
f.write("Constant Estimations\n")
foriinrange(len(c_estimates_naive)):
f.write(str(c_estimates_naive[i]) +"\n")

# CONSTANT SELECTED FOR NAIVE KRUSKAL ALGORITHM
reference_naive= [12582136*sizeforsizeinsizes]
plt.plot(sizes, reference_naive, label='Constant for naive')
plt.legend()
plt.xlabel('Number of vertices')
plt.ylabel('Run times (ns)')

# ---------------------------------------SECOND FIGURE: KRUSKAL UNION FIND------------------------------------------
plt.figure()
plt.plot(sizes, union_find_kruskal_time, label='Union Find Kruskal')

c_estimates_union= [union_find_kruskal_time[i] /sizes[i] foriinrange(len(sizes)-1)]
withopen('results/c_estimates_union_find.txt', 'w+') asf:
f.write("Constant Estimations\n")
foriinrange(len(c_estimates_union)):
f.write(str(c_estimates_union[i]) +"\n")

# CONSTANT SELECTED FOR UNION FIND ALGORITHM
reference_union= [10185090*sizeforsizeinsizes]
plt.plot(sizes, reference_union, label='Constant for union')
plt.legend()
plt.xlabel('Number of vertices')
plt.ylabel('Run times (ns)')

# ---------------------------------------THIRD FIGURE: PRIM-------------------------------------------------------
plt.figure()
plt.plot(sizes, prim_time, label='Prim')

c_estimates_prim= [prim_time[i] /sizes[i] foriinrange(len(sizes)-1)]
withopen('results/c_estimates_prim.txt', 'w+') asf:
f.write("Constant Estimates\n")
foriinrange(len(c_estimates_prim)):
f.write(str(c_estimates_prim[i]) +"\n")

# CONTSTANT SELECTED FOR PRIM ALGORITHM
reference_prim= [10392495*sizeforsizeinsizes]
plt.plot(sizes, reference_prim, label='Constant for prim')
plt.legend()
plt.xlabel('Number of vertices')
plt.ylabel('Run times (ns)')

# -------------------------------------FOURTH FIGURE: THREE ALGORITHMS TOGETHER----------------------------------
plt.figure()
plt.plot(sizes, naive_kruskal_time, label='Kruskal Naive')
plt.plot(sizes, union_find_kruskal_time, label='Kruskal Union Find')
plt.plot(sizes, prim_time, label='Prim')
plt.legend()
plt.xlabel('Number of vertices')
plt.ylabel('Run times (ns)')

#--------------------------------------FIFTH FIGURE: THREE ALGORITHMS TOGETHER WITH THREE CONSTANTS--------------
plt.figure()
plt.plot(sizes, naive_kruskal_time, label='Kruskal Naive')
plt.plot(sizes, reference_naive, label='Constant for naive')
plt.plot(sizes, union_find_kruskal_time, label='Kruskal Union Find')
plt.plot(sizes, reference_union, label='Constant for union')
plt.plot(sizes, prim_time, label='Prim')
plt.plot(sizes, reference_prim, label='Constant for prim')
plt.legend()
plt.xlabel('Number of vertices')
plt.ylabel('Run times (ns)')

plt.show()

# ===========================================================================