-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.py
102 lines (71 loc) · 3.2 KB
/
main.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
from random import randint
from statistics import mean
from time import time
from graph import Graph
no_vertices = [ 500, 5000, 10000 ]
no_edges = [ 3, 5, 7 ]
OUTPUT_DIR = './output/'
FILENAME = OUTPUT_DIR + str(time()).replace('.','')
data = {
'breadth': { 'times': [], 'distances': [] },
'depth': { 'times': [], 'distances': [] },
'best': { 'times': [], 'distances': [] },
'a': { 'times': [], 'distances': [] },
'a_star': { 'times': [], 'distances': [] },
}
NO_SAMPLES = 10
def avg(algorithm: str, list_type: str):
return mean(data[algorithm][list_type])
for n in no_vertices:
for k in no_edges:
graph = Graph(n, k)
for _ in range(NO_SAMPLES):
root = randint(0, n-1)
target = randint(0, n-1)
while target == root: target = randint(0, n-1)
# BREADTH FIRST SEARCH
start_time = time()
breadth = graph.breadthFirstSearch(root, target)
breadth_time = time() - start_time
data['breadth']['distances'].append(graph.travelledDistance(breadth))
data['breadth']['times'].append(breadth_time)
# DEPTH FIRST SEARCH
start_time = time()
depth = graph.depthFirstSearch(root, target)
depth_time = time() - start_time
data['depth']['distances'].append(graph.travelledDistance(depth))
data['depth']['times'].append(depth_time)
# BEST FIRST SEARCH
start_time = time()
best = graph.bestFirstSearch(root, target)
best_time = time() - start_time
data['best']['distances'].append(graph.travelledDistance(best))
data['best']['times'].append(best_time)
# A ALGORITHM
start_time = time()
a = graph.aSearch(root, target)
a_time = time() - start_time
data['a']['distances'].append(graph.travelledDistance(a))
data['a']['times'].append(a_time)
# A* ALGORITHM
start_time = time()
a_star = graph.aStarSearch(root, target)
a_star_time = time() - start_time
data['a_star']['distances'].append(graph.travelledDistance(a_star))
data['a_star']['times'].append(a_star_time)
print(f"### n = {n} ### k = {k} ###", end='\n\n')
print(f"Breadth First Search:")
print(f" * Time: {avg('breadth', 'times'):.2e}s")
print(f" * Distance: {avg('breadth', 'distances'):.2e}", end='\n\n')
print(f"Depth First Search:")
print(f" * Time: {avg('depth', 'times'):.2e}s")
print(f" * Distance: {avg('depth', 'distances'):.2e}", end='\n\n')
print(f"Best First Search:")
print(f" * Time: {avg('best', 'times'):.2e}s")
print(f" * Distance: {avg('best', 'distances'):.2e}", end='\n\n')
print(f"A Search:")
print(f" * Time: {avg('a', 'times'):.2e}s")
print(f" * Distance: {avg('a', 'distances'):.2e}", end='\n\n')
print(f"A Star Search:")
print(f" * Time: {avg('a_star', 'times'):.2e}s")
print(f" * Distance: {avg('a_star', 'distances'):.2e}", end='\n\n\n\n\n')