-
Notifications
You must be signed in to change notification settings - Fork 0
/
dijkstras.py
86 lines (59 loc) · 32.7 KB
/
dijkstras.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
# Source Code: https://bradfieldcs.com/algos/graphs/dijkstras-algorithm/
import heapq
import time
import matplotlib.pyplot as plt
import numpy as np
from graph import Graph
from main import Experiments
bbTimer = []
dijTimer = []
def calculate_distances(graph, starting_vertex):
distances = {vertex: float('infinity') for vertex in graph}
distances[starting_vertex] = 0
pq = [(0, starting_vertex)]
while len(pq) > 0:
current_distance, current_vertex = heapq.heappop(pq)
# Nodes can get added to the priority queue multiple times. We only
# process a vertex the first time we remove it from the priority queue.
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
# Only consider this new path if it's better than any path we've
# already found.
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
def timer(graph, start):
timer_on = time.time()
print("Graph", calculate_distances(graph, start))
timer_off = time.time()
dijTimer.append(timer_off - timer_on)
test = Experiments()
size10 = {1: {2: 28, 7: 50, 8: 20, 5: 40, 6: 39, 10: 21}, 2: {6: 13, 1: 28, 3: 40, 10: 42, 4: 47, 7: 30, 9: 29, 8: 33}, 3: {9: 29, 2: 40, 6: 37, 8: 40}, 4: {10: 34, 2: 47, 7: 27, 6: 23, 9: 43, 8: 27}, 5: {7: 9, 8: 49, 9: 27, 1: 40, 6: 15}, 6: {10: 25, 2: 13, 4: 23, 3: 37, 5: 15, 8: 35, 9: 45, 1: 39}, 7: {5: 9, 10: 16, 1: 50, 9: 16, 2: 30, 4: 27}, 8: {3: 40, 5: 49, 2: 33, 9: 12, 4: 27, 1: 20, 6: 35, 10: 26}, 9: {7: 16, 3: 29, 5: 27, 2: 29, 8: 12, 4: 43, 10: 29, 6: 45}, 10: {7: 16, 6: 25, 2: 42, 4: 34, 8: 26, 9: 29, 1: 21}}
size50 = {1: {45: 33, 4: 47, 43: 44, 15: 29, 25: 27, 12: 42, 34: 4, 39: 9, 11: 11, 7: 34, 36: 42, 16: 11}, 2: {23: 13, 34: 39, 41: 34, 44: 1, 17: 45, 4: 46, 5: 42, 13: 14}, 3: {15: 41, 22: 47, 23: 41, 48: 47}, 4: {34: 48, 7: 37, 1: 47, 36: 32, 23: 33, 22: 5, 16: 29, 15: 29, 6: 13, 14: 10, 50: 16, 46: 8, 2: 46, 30: 5}, 5: {8: 41, 23: 31, 18: 33, 37: 37, 24: 48, 50: 41, 43: 25, 34: 26, 25: 21, 31: 20, 39: 25, 32: 15, 47: 42, 36: 28, 11: 10, 2: 42, 19: 38, 48: 28, 26: 10, 7: 3}, 6: {10: 38, 29: 24, 39: 35, 16: 18, 8: 20, 4: 13, 18: 22, 11: 6, 32: 5, 44: 14, 30: 17, 9: 41}, 7: {4: 37, 30: 25, 8: 39, 31: 17, 23: 22, 11: 35, 15: 21, 39: 30, 1: 34, 17: 18, 16: 28, 19: 38, 5: 3, 20: 45}, 8: {46: 45, 5: 41, 10: 50, 7: 39, 13: 9, 6: 20, 25: 32, 33: 6, 44: 50, 49: 18, 50: 47, 11: 29, 23: 13, 15: 49}, 9: {36: 14, 17: 41, 22: 2, 10: 14, 38: 12, 41: 43, 18: 17, 25: 42, 19: 4, 11: 7, 6: 41, 21: 41, 32: 47, 26: 48}, 10: {37: 22, 46: 30, 9: 14, 8: 50, 50: 6, 6: 38, 11: 19, 20: 1, 16: 50, 31: 7}, 11: {41: 32, 43: 17, 7: 35, 16: 15, 35: 49, 10: 19, 34: 17, 13: 9, 29: 15, 31: 14, 6: 6, 1: 11, 9: 7, 44: 49, 45: 31, 5: 10, 8: 29, 36: 45}, 12: {1: 42, 23: 39, 39: 28, 13: 27, 41: 20, 22: 44, 31: 24, 27: 34}, 13: {46: 44, 12: 27, 47: 24, 11: 9, 8: 9, 31: 14, 41: 12, 25: 8, 45: 18, 2: 14, 23: 40}, 14: {4: 10, 23: 12}, 15: {1: 29, 25: 40, 4: 29, 7: 21, 23: 33, 3: 41, 27: 5, 38: 33, 8: 49, 32: 10, 36: 16, 21: 49, 44: 17, 26: 20}, 16: {43: 3, 37: 3, 11: 15, 4: 29, 6: 18, 35: 19, 45: 21, 7: 28, 1: 11, 27: 44, 26: 43, 10: 50, 44: 19, 40: 31}, 17: {9: 41, 23: 4, 36: 30, 34: 38, 7: 18, 2: 45, 46: 32, 49: 4, 22: 41, 24: 9, 21: 20, 47: 14, 26: 13, 43: 5, 25: 22, 44: 46}, 18: {26: 47, 5: 33, 46: 13, 47: 15, 36: 4, 6: 22, 45: 39, 34: 7, 41: 32, 9: 17, 50: 17, 19: 36}, 19: {7: 38, 9: 4, 44: 19, 30: 10, 27: 41, 5: 38, 18: 36, 33: 25}, 20: {10: 1, 25: 30, 46: 28, 48: 11, 7: 45}, 21: {48: 22, 41: 17, 9: 41, 17: 20, 15: 49, 33: 20}, 22: {30: 2, 34: 5, 4: 5, 9: 2, 3: 47, 17: 41, 12: 44, 45: 21, 33: 9, 44: 20, 50: 37, 42: 13}, 23: {5: 31, 47: 20, 17: 4, 41: 23, 12: 39, 4: 33, 25: 36, 7: 22, 14: 12, 2: 13, 28: 46, 15: 33, 13: 40, 48: 32, 46: 3, 3: 41, 35: 9, 50: 46, 38: 34, 8: 13}, 24: {31: 15, 5: 48, 27: 21, 41: 22, 17: 9, 33: 40}, 25: {47: 13, 43: 3, 15: 40, 1: 27, 29: 38, 23: 36, 20: 30, 48: 38, 44: 15, 5: 21, 9: 42, 13: 8, 45: 20, 8: 32, 46: 5, 17: 22}, 26: {43: 3, 18: 47, 46: 38, 39: 22, 9: 48, 17: 13, 30: 27, 16: 43, 15: 20, 5: 10}, 27: {47: 48, 24: 21, 16: 44, 15: 5, 12: 34, 19: 41}, 28: {33: 11, 47: 28, 46: 5, 48: 42, 30: 22, 23: 46}, 29: {6: 24, 25: 38, 34: 6, 11: 15, 44: 7, 46: 47}, 30: {35: 2, 22: 2, 7: 25, 49: 21, 4: 5, 45: 43, 19: 10, 28: 22, 42: 12, 6: 17, 41: 32, 26: 27}, 31: {7: 17, 24: 15, 11: 14, 13: 14, 5: 20, 49: 24, 10: 7, 12: 24}, 32: {42: 11, 43: 11, 41: 49, 6: 5, 5: 15, 47: 1, 33: 26, 45: 50, 15: 10, 9: 47}, 33: {48: 33, 36: 14, 49: 29, 28: 11, 24: 40, 32: 26, 8: 6, 22: 9, 19: 25, 44: 44, 21: 20, 47: 39}, 34: {22: 5, 4: 48, 44: 26, 39: 7, 5: 26, 11: 17, 2: 39, 1: 4, 17: 38, 29: 6, 18: 7, 46: 43, 45: 44, 36: 26}, 35: {46: 18, 30: 2, 16: 19, 11: 49, 47: 3, 48: 43, 45: 3, 23: 9}, 36: {4: 32, 38: 3, 47: 47, 9: 14, 33: 14, 43: 36, 41: 29, 17: 30, 49: 18, 18: 4, 5: 28, 46: 30, 11: 45, 1: 42, 40: 49, 45: 38, 34: 26, 15: 16}, 37: {16: 3, 45: 37, 5: 37, 10: 22}, 38: {36: 3, 46: 13, 39: 37, 9: 12, 15: 33, 23: 34}, 39: {7: 30, 12: 28, 34: 7, 6: 35, 1: 9, 38: 37, 26: 22, 50: 50, 48: 12, 5: 25, 47: 32, 46: 12}, 40: {47: 45, 44: 47, 48: 45, 41: 7, 16: 31, 36: 49}, 41: {23: 23, 11: 32, 9: 43, 50: 6, 21: 17, 36: 29, 13: 12, 2: 34, 40: 7, 32: 49, 24: 22, 18: 32, 48: 35, 12: 20, 43: 28, 30: 32}, 42: {45: 36, 32: 11, 22: 13, 30: 12}, 43: {11: 17, 16: 3, 32: 11, 26: 3, 25: 3, 1: 44, 36: 36, 5: 25, 17: 5, 41: 28}, 44: {40: 47, 34: 26, 50: 9, 48: 35, 2: 1, 25: 15, 6: 14, 29: 7, 11: 49, 19: 19, 22: 20, 8: 50, 33: 44, 16: 19, 17: 46, 15: 17}, 45: {49: 7, 1: 33, 37: 37, 42: 36, 30: 43, 18: 39, 13: 18, 47: 38, 46: 18, 16: 21, 32: 50, 11: 31, 22: 21, 25: 20, 48: 39, 35: 3, 36: 38, 34: 44}, 46: {13: 44, 35: 18, 38: 13, 8: 45, 10: 30, 18: 13, 4: 8, 26: 38, 34: 43, 17: 32, 29: 47, 28: 5, 36: 30, 45: 18, 39: 12, 20: 28, 48: 8, 23: 3, 47: 12, 25: 5}, 47: {23: 20, 36: 47, 18: 15, 25: 13, 13: 24, 40: 45, 28: 28, 35: 3, 32: 1, 27: 48, 45: 38, 5: 42, 17: 14, 39: 32, 33: 39, 46: 12}, 48: {25: 38, 33: 33, 44: 35, 21: 22, 35: 43, 40: 45, 28: 42, 39: 12, 23: 32, 41: 35, 20: 11, 46: 8, 3: 47, 45: 39, 5: 28, 50: 47}, 49: {30: 21, 45: 7, 31: 24, 36: 18, 17: 4, 33: 29, 8: 18, 50: 15}, 50: {5: 41, 10: 6, 41: 6, 4: 16, 39: 50, 44: 9, 49: 15, 22: 37, 23: 46, 8: 47, 48: 47, 18: 17}}
size90 = {1: {46: 40, 20: 48, 27: 7, 77: 36}, 2: {48: 17, 25: 32, 16: 7, 89: 8, 37: 22, 73: 22, 87: 31, 42: 42, 74: 14, 85: 6, 63: 21, 43: 11}, 3: {4: 50, 67: 40, 39: 2, 32: 22, 45: 33, 71: 40, 36: 35, 50: 39, 74: 19, 46: 45, 34: 17, 79: 4}, 4: {60: 44, 3: 50, 10: 1, 52: 23, 32: 38, 83: 1, 45: 50, 18: 2, 48: 9, 29: 2, 34: 25, 59: 44, 70: 30, 35: 40, 24: 22, 17: 16}, 5: {60: 41, 76: 46, 18: 26, 85: 35, 33: 4, 89: 19, 72: 19, 73: 49, 15: 39, 52: 27, 71: 21, 49: 17, 68: 21, 56: 13, 86: 10, 61: 6}, 6: {21: 18, 50: 39, 44: 20, 63: 30, 52: 14, 34: 34}, 7: {57: 20, 14: 50, 63: 22, 40: 41, 65: 45, 8: 9, 78: 15, 32: 16, 22: 22, 12: 8, 16: 29, 50: 43}, 8: {54: 47, 44: 34, 7: 9, 49: 25, 39: 1, 82: 33, 45: 18, 38: 12, 42: 50, 13: 20, 66: 6, 85: 27, 86: 27, 83: 40, 28: 10, 31: 1}, 9: {66: 17, 42: 17, 86: 11, 85: 9, 48: 3, 12: 32, 45: 42, 57: 36}, 10: {51: 22, 4: 1, 59: 12, 25: 37, 55: 48, 35: 18, 85: 40, 47: 17, 27: 19, 14: 45, 66: 36, 23: 4, 15: 33, 46: 19, 37: 49, 81: 25, 89: 29, 88: 5}, 11: {50: 49, 81: 5, 52: 35, 57: 30, 80: 20, 44: 26, 84: 4, 33: 13, 38: 22, 63: 12}, 12: {54: 16, 77: 3, 86: 11, 57: 29, 89: 41, 83: 13, 82: 22, 90: 31, 7: 8, 70: 41, 23: 33, 28: 50, 9: 32, 33: 41}, 13: {21: 22, 45: 37, 29: 10, 26: 42, 8: 20, 19: 35}, 14: {25: 6, 54: 29, 7: 50, 79: 24, 81: 24, 69: 6, 59: 28, 39: 18, 10: 45, 55: 22, 26: 9, 31: 18, 50: 35, 38: 29}, 15: {49: 7, 65: 40, 29: 49, 79: 9, 10: 33, 28: 18, 5: 39}, 16: {87: 48, 2: 7, 75: 14, 18: 20, 71: 32, 25: 33, 77: 12, 52: 1, 61: 9, 45: 44, 59: 9, 68: 33, 30: 37, 7: 29, 33: 43, 24: 30}, 17: {42: 28, 90: 36, 41: 36, 33: 23, 68: 10, 23: 32, 83: 38, 67: 21, 4: 16, 31: 46, 78: 2, 89: 20}, 18: {62: 41, 20: 2, 16: 20, 69: 18, 64: 50, 23: 42, 58: 34, 5: 26, 4: 2, 86: 19, 79: 17, 56: 6, 53: 17, 48: 21}, 19: {59: 26, 23: 4, 32: 28, 74: 20, 53: 17, 78: 21, 13: 35, 50: 2, 20: 14, 45: 48, 31: 33, 24: 42}, 20: {1: 48, 25: 11, 18: 2, 86: 49, 59: 32, 65: 44, 85: 3, 53: 20, 81: 31, 62: 14, 72: 22, 80: 23, 84: 43, 19: 14, 71: 34, 45: 38}, 21: {25: 19, 43: 15, 44: 31, 83: 48, 37: 29, 13: 22, 69: 1, 47: 25, 35: 34, 6: 18, 33: 34, 66: 14, 29: 49, 74: 24, 49: 50, 58: 43, 56: 9, 39: 9, 75: 3, 70: 26}, 22: {35: 30, 79: 11, 28: 25, 7: 22, 73: 43, 45: 48, 39: 30, 64: 2, 62: 14}, 23: {18: 42, 59: 24, 19: 4, 69: 18, 17: 32, 12: 33, 39: 15, 41: 21, 10: 4, 66: 23, 60: 43, 65: 37, 45: 24, 48: 22}, 24: {49: 38, 64: 31, 29: 5, 73: 16, 56: 35, 4: 22, 19: 42, 86: 8, 54: 50, 33: 4, 16: 30, 45: 2}, 25: {2: 32, 21: 19, 43: 13, 35: 3, 20: 11, 14: 6, 16: 33, 39: 21, 10: 37, 87: 39, 46: 21, 65: 33, 41: 50, 42: 41, 86: 27, 26: 14}, 26: {84: 15, 28: 38, 83: 14, 44: 2, 48: 49, 43: 28, 13: 42, 63: 20, 86: 29, 78: 11, 25: 14, 14: 9, 59: 37, 77: 41}, 27: {73: 26, 1: 7, 30: 25, 49: 48, 83: 19, 37: 30, 55: 22, 59: 1, 52: 21, 84: 7, 79: 2, 66: 19, 47: 9, 10: 19}, 28: {26: 38, 46: 44, 45: 16, 22: 25, 12: 50, 29: 3, 51: 26, 8: 10, 31: 3, 15: 18}, 29: {90: 39, 36: 40, 70: 18, 13: 10, 83: 36, 21: 49, 15: 49, 47: 9, 28: 3, 24: 5, 4: 2, 39: 31, 61: 15, 78: 44, 37: 38, 62: 39}, 30: {69: 36, 27: 25, 40: 5, 72: 49, 55: 49, 44: 5, 42: 46, 89: 43, 90: 1, 16: 37}, 31: {42: 24, 73: 19, 63: 33, 88: 21, 8: 1, 28: 3, 14: 18, 71: 3, 81: 38, 72: 21, 17: 46, 19: 33}, 32: {82: 39, 58: 34, 59: 4, 84: 4, 3: 22, 4: 38, 50: 36, 64: 23, 7: 16, 19: 28, 86: 38, 79: 7, 61: 1, 33: 13}, 33: {17: 23, 21: 34, 81: 35, 49: 35, 11: 13, 85: 37, 65: 12, 61: 45, 12: 41, 5: 4, 32: 13, 39: 31, 24: 4, 16: 43}, 34: {88: 38, 87: 29, 83: 44, 81: 37, 47: 48, 3: 17, 6: 34, 60: 48, 75: 43, 4: 25}, 35: {25: 3, 22: 30, 81: 4, 21: 34, 10: 18, 52: 45, 65: 5, 67: 11, 63: 12, 72: 46, 4: 40, 45: 22}, 36: {29: 40, 88: 18, 71: 48, 42: 8, 37: 25, 3: 35, 69: 13, 82: 25, 79: 30, 81: 27}, 37: {74: 5, 71: 21, 49: 37, 21: 29, 27: 30, 2: 22, 75: 45, 36: 25, 40: 21, 86: 1, 56: 17, 85: 22, 60: 16, 29: 38, 45: 45, 10: 49}, 38: {8: 12, 49: 13, 84: 15, 44: 32, 14: 29, 47: 12, 81: 19, 85: 15, 48: 10, 11: 22}, 39: {56: 39, 49: 44, 25: 21, 3: 2, 76: 18, 80: 17, 83: 20, 69: 25, 66: 33, 55: 31, 14: 18, 74: 7, 21: 9, 8: 1, 44: 23, 22: 30, 29: 31, 23: 15, 33: 31, 50: 5}, 40: {67: 36, 84: 9, 7: 41, 76: 8, 64: 50, 30: 5, 75: 16, 54: 38, 72: 12, 37: 21}, 41: {54: 41, 17: 36, 23: 21, 25: 50, 42: 48, 65: 50}, 42: {45: 10, 17: 28, 9: 17, 62: 11, 36: 8, 60: 1, 2: 42, 31: 24, 73: 8, 8: 50, 25: 41, 30: 46, 83: 40, 84: 20, 51: 47, 41: 48}, 43: {21: 15, 25: 13, 26: 28, 86: 46, 85: 21, 88: 23, 49: 49, 62: 21, 44: 28, 80: 42, 89: 29, 81: 24, 2: 11, 65: 47}, 44: {8: 34, 21: 31, 26: 2, 62: 14, 11: 26, 43: 28, 38: 32, 6: 20, 30: 5, 39: 23}, 45: {76: 19, 74: 8, 75: 49, 42: 10, 13: 37, 56: 22, 16: 44, 3: 33, 85: 37, 28: 16, 82: 18, 8: 18, 22: 48, 4: 50, 35: 22, 23: 24, 19: 48, 37: 45, 20: 38, 51: 13, 24: 2, 9: 42}, 46: {28: 44, 1: 40, 3: 45, 25: 21, 10: 19, 81: 2, 89: 19, 79: 36}, 47: {21: 25, 50: 23, 29: 9, 82: 32, 10: 17, 27: 9, 78: 37, 34: 48, 38: 12, 59: 25}, 48: {88: 21, 2: 17, 52: 32, 26: 49, 74: 38, 61: 47, 18: 21, 4: 9, 79: 26, 9: 3, 23: 22, 90: 5, 85: 32, 38: 10, 84: 10, 68: 29}, 49: {15: 7, 51: 5, 39: 44, 37: 37, 27: 48, 43: 49, 88: 19, 68: 22, 8: 25, 87: 5, 66: 26, 21: 50, 70: 14, 90: 33, 38: 13, 64: 9, 33: 35, 24: 38, 5: 17, 75: 21}, 50: {55: 17, 82: 36, 47: 23, 11: 49, 3: 39, 32: 36, 6: 39, 69: 36, 67: 8, 56: 38, 19: 2, 64: 31, 7: 43, 14: 35, 39: 5, 89: 42}, 51: {49: 5, 76: 39, 86: 15, 10: 22, 71: 26, 58: 7, 66: 36, 59: 45, 80: 35, 65: 44, 83: 11, 42: 47, 57: 6, 28: 26, 68: 3, 73: 9, 45: 13, 56: 10}, 52: {4: 23, 55: 12, 72: 46, 48: 32, 16: 1, 11: 35, 35: 45, 27: 21, 64: 36, 68: 31, 5: 27, 6: 14}, 53: {77: 37, 70: 8, 20: 20, 19: 17, 62: 3, 18: 17, 89: 29, 83: 24}, 54: {14: 29, 8: 47, 72: 6, 12: 16, 57: 26, 73: 17, 40: 38, 41: 41, 56: 34, 24: 50}, 55: {52: 12, 50: 17, 39: 31, 27: 22, 69: 1, 71: 11, 74: 27, 10: 48, 14: 22, 30: 49}, 56: {84: 32, 39: 39, 45: 22, 72: 3, 89: 2, 71: 6, 82: 25, 87: 31, 50: 38, 21: 9, 18: 6, 37: 17, 5: 13, 24: 35, 51: 10, 54: 34}, 57: {12: 29, 54: 26, 11: 30, 7: 20, 68: 25, 51: 6, 9: 36, 78: 21}, 58: {32: 34, 75: 49, 51: 7, 63: 49, 21: 43, 18: 34}, 59: {75: 25, 32: 4, 83: 26, 66: 25, 60: 48, 81: 23, 23: 24, 10: 12, 27: 1, 74: 26, 82: 6, 19: 26, 76: 45, 14: 28, 51: 45, 20: 32, 4: 44, 16: 9, 47: 25, 26: 37}, 60: {64: 2, 4: 44, 42: 1, 59: 48, 75: 5, 5: 41, 71: 20, 82: 5, 34: 48, 23: 43, 80: 3, 37: 16}, 61: {48: 47, 16: 9, 33: 45, 29: 15, 5: 6, 32: 1}, 62: {44: 14, 18: 41, 42: 11, 75: 49, 43: 21, 67: 44, 20: 14, 53: 3, 29: 39, 84: 13, 88: 32, 22: 14}, 63: {58: 49, 86: 39, 26: 20, 66: 31, 69: 37, 7: 22, 65: 11, 31: 33, 6: 30, 35: 12, 79: 7, 2: 21, 11: 12, 84: 31, 89: 42, 71: 43}, 64: {77: 25, 60: 2, 32: 23, 18: 50, 70: 48, 40: 50, 49: 9, 81: 47, 50: 31, 83: 41, 24: 31, 52: 36, 22: 2, 76: 15}, 65: {25: 33, 63: 11, 20: 44, 7: 45, 51: 44, 15: 40, 90: 50, 35: 5, 41: 50, 33: 12, 23: 37, 83: 28, 68: 22, 86: 33, 43: 47, 81: 32}, 66: {59: 25, 9: 17, 63: 31, 39: 33, 21: 14, 51: 36, 27: 19, 49: 26, 70: 16, 10: 36, 23: 23, 8: 6}, 67: {3: 40, 40: 36, 62: 44, 77: 15, 35: 11, 50: 8, 81: 35, 84: 29, 17: 21, 70: 37, 79: 14, 72: 33}, 68: {80: 38, 75: 29, 49: 22, 70: 13, 52: 31, 17: 10, 73: 47, 57: 25, 83: 40, 51: 3, 16: 33, 65: 22, 48: 29, 5: 21}, 69: {18: 18, 21: 1, 77: 30, 30: 36, 79: 19, 89: 5, 14: 6, 83: 35, 39: 25, 82: 11, 74: 17, 36: 13, 23: 18, 55: 1, 73: 32, 63: 37, 50: 36, 75: 49}, 70: {89: 50, 77: 32, 53: 8, 71: 30, 82: 15, 29: 18, 68: 13, 64: 48, 12: 41, 49: 14, 67: 37, 66: 16, 21: 26, 4: 30}, 71: {37: 21, 77: 42, 70: 30, 16: 32, 56: 6, 51: 26, 3: 40, 36: 48, 55: 11, 60: 20, 31: 3, 5: 21, 63: 43, 20: 34}, 72: {56: 3, 52: 46, 88: 31, 54: 6, 30: 49, 89: 9, 35: 46, 40: 12, 67: 33, 5: 19, 31: 21, 20: 22}, 73: {54: 17, 27: 26, 2: 22, 74: 47, 31: 19, 69: 32, 85: 48, 42: 8, 24: 16, 22: 43, 5: 49, 68: 47, 51: 9, 76: 36}, 74: {45: 8, 37: 5, 73: 47, 48: 38, 59: 26, 69: 17, 39: 7, 3: 19, 21: 24, 55: 27, 19: 20, 2: 14}, 75: {79: 11, 45: 49, 58: 49, 59: 25, 62: 49, 16: 14, 83: 32, 60: 5, 68: 29, 37: 45, 69: 49, 40: 16, 76: 1, 34: 43, 49: 21, 21: 3}, 76: {51: 39, 45: 19, 5: 46, 39: 18, 40: 8, 59: 45, 64: 15, 79: 4, 73: 36, 75: 1}, 77: {71: 42, 88: 43, 70: 32, 64: 25, 12: 3, 53: 37, 83: 44, 89: 28, 1: 36, 69: 30, 67: 15, 16: 12, 26: 41, 79: 2}, 78: {26: 11, 7: 15, 19: 21, 79: 23, 29: 44, 47: 37, 57: 21, 17: 2}, 79: {22: 11, 75: 11, 14: 24, 69: 19, 78: 23, 27: 2, 32: 7, 18: 17, 76: 4, 36: 30, 85: 48, 15: 9, 3: 4, 48: 26, 46: 36, 67: 14, 77: 2, 63: 7}, 80: {39: 17, 11: 20, 43: 42, 68: 38, 84: 20, 51: 35, 20: 23, 60: 3}, 81: {11: 5, 85: 43, 59: 23, 14: 24, 43: 24, 35: 4, 64: 47, 67: 35, 34: 37, 33: 35, 36: 27, 20: 31, 46: 2, 83: 19, 65: 32, 31: 38, 10: 25, 38: 19}, 82: {50: 36, 32: 39, 69: 11, 70: 15, 36: 25, 59: 6, 60: 5, 56: 25, 47: 32, 12: 22, 8: 33, 45: 18}, 83: {21: 48, 26: 14, 86: 50, 59: 26, 4: 1, 77: 44, 12: 13, 27: 19, 69: 35, 75: 32, 87: 48, 39: 20, 84: 5, 29: 36, 64: 41, 34: 44, 53: 24, 17: 38, 8: 40, 42: 40, 81: 19, 51: 11, 65: 28, 68: 40}, 84: {40: 9, 26: 15, 32: 4, 56: 32, 87: 15, 83: 5, 27: 7, 80: 20, 67: 29, 38: 15, 42: 20, 11: 4, 62: 13, 20: 43, 63: 31, 48: 10}, 85: {81: 43, 43: 21, 2: 6, 20: 3, 5: 35, 45: 37, 9: 9, 73: 48, 37: 22, 10: 40, 8: 27, 86: 24, 33: 37, 79: 48, 38: 15, 48: 32}, 86: {20: 49, 51: 15, 43: 46, 83: 50, 63: 39, 12: 11, 90: 45, 26: 29, 37: 1, 9: 11, 18: 19, 32: 38, 85: 24, 8: 27, 65: 33, 25: 27, 24: 8, 5: 10}, 87: {34: 29, 16: 48, 25: 39, 83: 48, 56: 31, 2: 31, 49: 5, 84: 15}, 88: {77: 43, 48: 21, 36: 18, 34: 38, 43: 23, 72: 31, 31: 21, 49: 19, 10: 5, 62: 32}, 89: {2: 8, 70: 50, 77: 28, 56: 2, 69: 5, 12: 41, 72: 9, 43: 29, 30: 43, 53: 29, 5: 19, 46: 19, 50: 42, 63: 42, 17: 20, 10: 29}, 90: {17: 36, 29: 39, 12: 31, 86: 45, 49: 33, 65: 50, 48: 5, 30: 1}}
size140 = {1: {118: 36, 121: 11, 77: 49, 46: 33, 82: 10, 79: 29, 89: 40, 122: 48, 65: 45, 28: 24, 68: 40, 93: 6, 11: 30, 108: 28}, 2: {101: 22, 41: 42, 24: 45, 3: 18, 29: 48, 43: 21, 80: 21, 28: 12, 56: 33, 109: 27, 75: 50, 92: 42, 94: 10, 64: 38, 130: 9, 95: 22, 63: 36, 17: 38}, 3: {131: 43, 135: 11, 2: 18, 37: 29, 8: 38, 98: 26, 69: 14, 56: 26, 118: 3, 10: 2, 100: 25, 136: 30, 93: 18, 111: 44, 137: 42, 132: 27, 125: 47, 106: 18}, 4: {18: 42, 12: 16, 78: 15, 131: 33, 62: 47, 5: 50}, 5: {20: 41, 139: 50, 4: 50, 58: 1, 22: 46, 17: 17, 88: 30, 7: 13, 43: 17, 33: 21, 123: 15, 21: 7}, 6: {28: 3, 126: 21, 100: 11, 118: 46, 117: 30, 127: 6, 81: 40, 88: 11, 45: 2, 99: 43, 19: 33, 47: 9, 11: 14, 66: 39, 32: 20, 94: 3, 139: 15, 31: 13, 16: 48, 108: 4}, 7: {47: 19, 61: 9, 133: 15, 54: 8, 51: 42, 117: 3, 5: 13, 120: 31, 97: 31, 131: 15, 108: 32, 50: 32}, 8: {17: 18, 125: 8, 58: 13, 3: 38, 71: 39, 48: 1, 78: 7, 18: 39, 41: 4, 56: 18, 34: 49, 126: 21}, 9: {64: 13, 94: 45, 30: 10, 19: 32, 41: 35, 80: 7}, 10: {103: 5, 88: 5, 90: 22, 131: 37, 73: 50, 38: 8, 54: 17, 102: 46, 3: 2, 56: 32, 97: 29, 51: 43, 94: 12, 34: 50, 130: 20, 70: 42, 78: 42, 119: 32}, 11: {78: 13, 101: 22, 90: 48, 105: 15, 129: 48, 102: 23, 128: 44, 88: 18, 20: 11, 115: 47, 27: 41, 6: 14, 108: 6, 139: 29, 100: 27, 21: 43, 112: 48, 81: 7, 62: 44, 1: 30, 37: 26, 95: 46}, 12: {4: 16, 94: 24, 116: 46, 52: 16, 28: 13, 30: 47, 70: 18, 64: 11, 120: 45, 126: 50}, 13: {98: 39, 73: 6, 15: 43, 115: 35, 137: 11, 53: 21}, 14: {85: 29, 103: 16, 20: 38, 54: 25, 48: 37, 96: 37}, 15: {122: 41, 82: 5, 56: 15, 13: 43, 115: 38, 125: 47, 129: 41, 63: 37, 119: 5, 112: 47, 17: 38, 60: 34, 80: 26, 138: 12}, 16: {109: 42, 78: 35, 26: 46, 67: 18, 98: 14, 6: 48}, 17: {58: 18, 54: 10, 79: 14, 47: 31, 39: 9, 8: 18, 5: 17, 91: 1, 120: 3, 123: 27, 131: 25, 15: 38, 2: 38, 62: 17}, 18: {58: 29, 4: 42, 29: 47, 81: 3, 8: 39, 136: 6, 109: 23, 137: 11, 21: 26, 119: 42}, 19: {107: 44, 136: 35, 123: 8, 79: 41, 9: 32, 77: 24, 63: 40, 41: 30, 111: 2, 6: 33, 92: 33, 26: 50, 138: 46, 84: 6, 133: 17, 21: 29}, 20: {78: 5, 5: 41, 38: 37, 11: 11, 122: 45, 111: 28, 109: 18, 25: 20, 69: 26, 82: 23, 26: 13, 55: 49, 138: 48, 14: 38}, 21: {112: 40, 47: 42, 33: 49, 131: 31, 137: 40, 66: 2, 103: 37, 92: 18, 25: 17, 45: 2, 11: 43, 23: 46, 111: 22, 18: 26, 38: 35, 120: 7, 5: 7, 68: 8, 19: 29, 74: 34}, 22: {88: 21, 40: 46, 76: 33, 104: 36, 38: 33, 115: 2, 114: 19, 5: 46, 49: 6, 136: 35, 113: 13, 94: 48}, 23: {46: 39, 75: 34, 114: 7, 45: 33, 30: 49, 99: 30, 21: 46, 123: 14}, 24: {128: 24, 2: 45, 94: 4, 93: 20, 52: 21, 64: 12, 75: 14, 70: 19, 90: 30, 31: 1, 77: 43, 30: 23}, 25: {36: 47, 64: 43, 68: 17, 33: 49, 131: 33, 89: 37, 40: 42, 114: 11, 20: 20, 133: 17, 128: 35, 21: 17, 90: 34, 113: 35}, 26: {43: 30, 107: 30, 116: 17, 104: 34, 135: 2, 47: 42, 103: 10, 90: 32, 19: 50, 16: 46, 79: 45, 100: 44, 64: 32, 138: 18, 31: 29, 20: 13}, 27: {70: 15, 115: 39, 104: 45, 96: 4, 69: 41, 135: 28, 50: 19, 11: 41}, 28: {84: 32, 78: 1, 71: 25, 44: 21, 2: 12, 38: 7, 58: 46, 86: 5, 138: 49, 6: 3, 67: 26, 90: 32, 136: 42, 129: 17, 1: 24, 12: 13, 82: 24, 39: 16}, 29: {120: 43, 118: 2, 61: 16, 2: 48, 106: 28, 96: 6, 115: 2, 112: 1, 74: 3, 113: 34, 121: 5, 18: 47, 140: 32, 87: 47, 92: 32, 45: 9, 66: 49, 81: 6}, 30: {60: 46, 128: 4, 79: 38, 138: 50, 31: 32, 71: 49, 58: 26, 9: 10, 12: 47, 23: 49, 24: 23, 98: 6}, 31: {92: 46, 58: 10, 86: 25, 30: 32, 53: 37, 80: 22, 133: 37, 95: 46, 105: 36, 75: 24, 6: 13, 49: 37, 24: 1, 26: 29}, 32: {67: 39, 38: 34, 109: 2, 6: 20, 34: 31, 96: 49, 94: 13, 112: 14}, 33: {43: 47, 98: 31, 51: 3, 112: 19, 93: 22, 59: 25, 25: 49, 67: 32, 49: 27, 21: 49, 5: 21, 40: 19, 55: 29, 128: 27, 41: 28, 106: 15, 54: 8, 102: 11, 38: 18, 37: 11}, 34: {135: 34, 84: 17, 136: 38, 108: 49, 10: 50, 96: 21, 77: 8, 32: 31, 55: 38, 8: 49}, 35: {125: 6, 115: 31, 128: 17, 83: 32, 114: 48, 47: 13}, 36: {95: 8, 101: 31, 49: 5, 115: 29, 98: 28, 25: 47, 87: 47, 117: 18, 40: 23, 125: 22, 53: 44, 116: 36, 134: 44, 50: 32, 61: 19, 58: 30, 48: 43, 86: 8, 111: 1, 109: 22}, 37: {3: 29, 104: 16, 90: 36, 74: 4, 91: 16, 131: 4, 33: 11, 122: 44, 45: 7, 11: 26}, 38: {91: 32, 84: 5, 10: 8, 48: 43, 28: 7, 22: 33, 102: 23, 94: 7, 32: 34, 20: 37, 99: 9, 44: 11, 70: 21, 111: 47, 68: 39, 21: 35, 49: 41, 33: 18, 126: 15, 51: 27}, 39: {102: 30, 17: 9, 99: 48, 43: 28, 81: 14, 140: 42, 113: 20, 65: 13, 28: 16, 123: 3, 60: 1, 64: 9}, 40: {22: 46, 87: 35, 105: 13, 36: 23, 74: 50, 60: 42, 33: 19, 67: 25, 86: 49, 25: 42, 47: 2, 140: 33, 73: 4, 52: 35, 95: 27, 77: 18, 113: 1, 139: 7}, 41: {2: 42, 78: 31, 60: 49, 42: 43, 19: 30, 68: 29, 44: 42, 33: 28, 106: 48, 8: 4, 112: 6, 53: 47, 107: 20, 9: 35}, 42: {41: 43, 61: 26, 123: 5, 98: 33, 70: 39, 59: 50, 64: 50, 48: 23}, 43: {96: 27, 33: 47, 98: 28, 26: 30, 2: 21, 130: 48, 91: 30, 80: 1, 39: 28, 61: 37, 139: 9, 5: 17, 86: 2, 138: 11}, 44: {65: 48, 64: 16, 137: 14, 113: 20, 28: 21, 53: 46, 110: 6, 99: 42, 112: 5, 76: 17, 101: 24, 100: 50, 38: 11, 121: 46, 92: 13, 41: 42, 74: 15, 80: 13, 138: 22, 61: 5}, 45: {67: 10, 59: 10, 105: 29, 112: 15, 23: 33, 6: 2, 29: 9, 50: 10, 21: 2, 138: 29, 110: 39, 74: 9, 88: 23, 37: 7}, 46: {1: 33, 136: 4, 89: 36, 23: 39, 85: 10, 116: 38, 106: 20, 73: 9}, 47: {21: 42, 7: 19, 17: 31, 131: 43, 92: 18, 93: 28, 102: 41, 71: 19, 26: 42, 109: 4, 135: 37, 50: 39, 6: 9, 40: 2, 35: 13, 107: 44, 120: 43, 123: 34}, 48: {38: 43, 65: 9, 8: 1, 115: 39, 87: 48, 36: 43, 109: 36, 123: 15, 42: 23, 14: 37}, 49: {61: 45, 36: 5, 103: 18, 99: 17, 56: 9, 53: 5, 82: 8, 33: 27, 137: 27, 22: 6, 31: 37, 38: 41}, 50: {99: 39, 98: 25, 36: 32, 104: 30, 47: 39, 101: 43, 45: 10, 27: 19, 77: 38, 137: 30, 111: 20, 125: 43, 131: 45, 94: 35, 7: 32, 107: 50}, 51: {98: 2, 95: 12, 79: 4, 33: 3, 10: 43, 7: 42, 116: 21, 55: 15, 70: 33, 139: 8, 74: 28, 60: 41, 63: 8, 81: 24, 38: 27, 131: 4}, 52: {57: 9, 104: 1, 12: 16, 102: 27, 68: 39, 130: 31, 40: 35, 24: 21, 55: 13, 103: 17}, 53: {110: 7, 91: 11, 140: 46, 90: 44, 85: 19, 36: 44, 44: 46, 62: 46, 99: 38, 31: 37, 49: 5, 106: 42, 98: 11, 117: 40, 92: 32, 77: 5, 13: 21, 87: 5, 41: 47, 60: 32}, 54: {17: 10, 98: 12, 131: 34, 118: 14, 115: 45, 10: 17, 7: 8, 71: 4, 62: 29, 136: 8, 124: 31, 121: 30, 104: 39, 75: 42, 123: 33, 33: 8, 14: 25, 63: 1}, 55: {99: 33, 65: 11, 96: 36, 82: 43, 74: 34, 88: 41, 104: 8, 71: 11, 51: 15, 102: 6, 85: 16, 61: 18, 109: 50, 33: 29, 20: 49, 52: 13, 120: 26, 34: 38, 108: 22, 123: 28}, 56: {90: 39, 49: 9, 3: 26, 85: 39, 10: 32, 15: 15, 98: 15, 2: 33, 8: 18, 120: 48}, 57: {107: 9, 52: 9, 86: 38, 89: 44}, 58: {97: 50, 17: 18, 122: 22, 65: 16, 31: 10, 18: 29, 94: 13, 77: 15, 104: 49, 123: 38, 62: 7, 87: 27, 59: 15, 8: 13, 5: 1, 28: 46, 139: 30, 66: 17, 36: 30, 30: 26, 71: 38, 73: 23, 100: 36, 74: 36}, 59: {121: 44, 107: 40, 93: 4, 73: 17, 45: 10, 58: 15, 33: 25, 99: 20, 84: 4, 79: 29, 83: 1, 92: 3, 116: 46, 87: 20, 42: 50, 64: 10, 69: 47, 113: 38}, 60: {132: 18, 30: 46, 115: 19, 41: 49, 119: 49, 76: 30, 40: 42, 109: 6, 51: 41, 90: 12, 53: 32, 107: 12, 15: 34, 39: 1}, 61: {136: 25, 122: 38, 7: 9, 49: 45, 42: 26, 29: 16, 43: 37, 67: 8, 55: 18, 36: 19, 65: 15, 110: 14, 44: 5, 64: 41}, 62: {124: 27, 58: 7, 53: 46, 105: 22, 108: 36, 4: 47, 112: 10, 54: 29, 90: 27, 68: 31, 17: 17, 11: 44, 96: 33, 135: 20}, 63: {99: 25, 128: 41, 73: 24, 51: 8, 109: 4, 19: 40, 67: 48, 66: 43, 15: 37, 77: 48, 54: 1, 2: 36, 80: 33, 83: 50}, 64: {44: 16, 9: 13, 25: 43, 121: 5, 138: 26, 77: 26, 24: 12, 75: 17, 2: 38, 108: 36, 12: 11, 120: 10, 59: 10, 26: 32, 39: 9, 86: 20, 61: 41, 42: 50, 125: 19}, 65: {55: 11, 91: 27, 58: 16, 44: 48, 83: 14, 73: 32, 48: 9, 84: 10, 72: 14, 136: 19, 39: 13, 1: 45, 87: 17, 92: 11, 68: 25, 61: 15}, 66: {131: 49, 82: 45, 73: 47, 71: 43, 113: 20, 78: 41, 58: 17, 81: 5, 21: 2, 105: 33, 6: 39, 97: 24, 63: 43, 29: 49, 127: 13, 114: 33, 139: 36, 95: 37, 74: 8, 77: 42}, 67: {61: 8, 45: 10, 90: 18, 68: 16, 33: 32, 28: 26, 40: 25, 32: 39, 16: 18, 63: 48}, 68: {91: 41, 102: 37, 67: 16, 25: 17, 139: 21, 138: 47, 89: 39, 74: 29, 41: 29, 52: 39, 116: 32, 129: 36, 62: 31, 65: 25, 107: 25, 96: 34, 112: 20, 38: 39, 21: 8, 1: 40, 128: 49, 98: 12}, 69: {129: 7, 3: 14, 133: 40, 27: 41, 77: 39, 112: 25, 126: 3, 20: 26, 90: 8, 59: 47}, 70: {84: 6, 27: 15, 122: 41, 51: 33, 10: 42, 78: 37, 24: 19, 99: 41, 81: 48, 38: 21, 121: 32, 12: 18, 132: 8, 42: 39, 123: 41, 109: 5}, 71: {78: 36, 131: 28, 66: 43, 129: 47, 30: 49, 28: 25, 55: 11, 133: 7, 54: 4, 8: 39, 47: 19, 138: 44, 122: 33, 58: 38, 118: 36, 128: 9, 115: 49, 120: 7}, 72: {96: 27, 65: 14, 102: 27, 73: 20, 105: 38, 104: 10}, 73: {59: 17, 126: 49, 82: 42, 124: 4, 65: 32, 66: 47, 81: 8, 10: 50, 13: 6, 109: 13, 74: 40, 118: 37, 117: 19, 114: 8, 72: 20, 89: 29, 58: 23, 63: 24, 46: 9, 40: 4}, 74: {104: 5, 55: 34, 139: 9, 40: 50, 135: 4, 84: 19, 126: 31, 73: 40, 82: 15, 105: 31, 77: 12, 29: 3, 68: 29, 51: 28, 37: 4, 85: 27, 131: 12, 109: 45, 45: 9, 127: 43, 130: 20, 113: 12, 58: 36, 66: 8, 21: 34, 44: 15, 121: 43, 75: 10}, 75: {98: 1, 120: 42, 109: 1, 97: 38, 23: 34, 111: 39, 54: 42, 127: 14, 64: 17, 2: 50, 31: 24, 24: 14, 74: 10, 90: 10}, 76: {97: 17, 22: 33, 60: 30, 118: 45, 44: 17, 137: 48, 121: 46, 109: 4}, 77: {58: 15, 1: 49, 93: 42, 119: 48, 64: 26, 99: 35, 53: 5, 74: 12, 19: 24, 122: 4, 117: 8, 34: 8, 63: 48, 50: 38, 66: 42, 69: 39, 40: 18, 24: 43}, 78: {28: 1, 11: 13, 41: 31, 71: 36, 66: 41, 4: 15, 98: 37, 20: 5, 16: 35, 115: 27, 70: 37, 8: 7, 105: 15, 10: 42, 92: 24, 134: 20}, 79: {94: 2, 103: 12, 19: 41, 82: 40, 1: 29, 17: 14, 90: 28, 30: 38, 80: 31, 51: 4, 59: 29, 110: 1, 134: 20, 139: 40, 122: 47, 26: 45}, 80: {43: 1, 122: 46, 121: 34, 83: 35, 103: 14, 79: 31, 118: 42, 93: 13, 31: 22, 2: 21, 9: 7, 63: 33, 44: 13, 15: 26}, 81: {131: 2, 73: 8, 66: 5, 98: 23, 18: 3, 6: 40, 51: 24, 39: 14, 29: 6, 117: 11, 11: 7, 70: 48}, 82: {15: 5, 97: 13, 55: 43, 92: 42, 66: 45, 73: 42, 79: 40, 1: 10, 91: 23, 74: 15, 136: 27, 49: 8, 121: 33, 84: 1, 20: 23, 28: 24}, 83: {80: 35, 65: 14, 118: 21, 59: 1, 35: 32, 92: 29, 63: 50, 115: 46}, 84: {38: 5, 28: 32, 34: 17, 70: 6, 65: 10, 86: 41, 91: 44, 135: 43, 74: 19, 59: 4, 132: 43, 128: 31, 103: 44, 107: 10, 82: 1, 138: 42, 19: 6, 105: 15}, 85: {115: 20, 53: 19, 56: 39, 14: 29, 94: 36, 46: 10, 74: 27, 55: 16, 134: 31, 132: 28}, 86: {84: 41, 31: 25, 28: 5, 102: 50, 96: 4, 135: 25, 136: 6, 57: 38, 36: 8, 40: 49, 133: 42, 118: 8, 111: 42, 124: 28, 64: 20, 43: 2}, 87: {40: 35, 117: 26, 58: 27, 36: 47, 105: 46, 119: 49, 29: 47, 48: 48, 59: 20, 65: 17, 53: 5, 122: 43}, 88: {10: 5, 22: 21, 55: 41, 137: 26, 97: 21, 131: 37, 11: 18, 134: 25, 6: 11, 5: 30, 96: 29, 45: 23}, 89: {25: 37, 46: 36, 73: 29, 134: 6, 57: 44, 68: 39, 128: 16, 1: 40}, 90: {126: 7, 10: 22, 53: 44, 11: 48, 125: 34, 79: 28, 102: 33, 67: 18, 28: 32, 56: 39, 26: 32, 137: 43, 60: 12, 37: 36, 127: 15, 62: 27, 112: 11, 24: 30, 75: 10, 25: 34, 135: 12, 69: 8}, 91: {53: 11, 68: 41, 112: 14, 38: 32, 65: 27, 122: 6, 123: 39, 43: 30, 102: 34, 84: 44, 17: 1, 82: 23, 100: 4, 111: 7, 120: 41, 37: 16}, 92: {107: 28, 31: 46, 82: 42, 93: 35, 131: 24, 47: 18, 137: 28, 112: 49, 59: 3, 99: 18, 116: 25, 53: 32, 65: 11, 78: 24, 21: 18, 29: 32, 83: 29, 19: 33, 118: 47, 44: 13, 2: 42, 130: 43}, 93: {92: 35, 59: 4, 47: 28, 77: 42, 80: 13, 33: 22, 24: 20, 3: 18, 1: 6, 127: 10}, 94: {79: 2, 9: 45, 104: 47, 12: 24, 58: 13, 108: 42, 102: 3, 127: 38, 10: 12, 38: 7, 85: 36, 6: 3, 24: 4, 22: 48, 2: 10, 50: 35, 32: 13}, 95: {51: 12, 36: 8, 119: 41, 118: 37, 31: 46, 100: 12, 66: 37, 111: 23, 2: 22, 121: 45, 11: 46, 40: 27}, 96: {27: 4, 43: 27, 130: 26, 55: 36, 29: 6, 86: 4, 34: 21, 72: 27, 32: 49, 116: 9, 68: 34, 118: 27, 14: 37, 88: 29, 139: 27, 62: 33}, 97: {102: 48, 58: 50, 82: 13, 76: 17, 75: 38, 88: 21, 115: 3, 10: 29, 66: 24, 7: 31}, 98: {54: 12, 75: 1, 112: 2, 118: 30, 139: 28, 51: 2, 33: 31, 43: 28, 42: 33, 36: 28, 3: 26, 78: 37, 50: 25, 13: 39, 81: 23, 53: 11, 136: 20, 56: 15, 134: 12, 103: 27, 30: 6, 121: 29, 68: 12, 16: 14}, 99: {118: 49, 55: 33, 77: 35, 39: 48, 59: 20, 53: 38, 44: 42, 50: 39, 49: 17, 131: 37, 114: 28, 133: 12, 92: 18, 63: 25, 107: 45, 100: 23, 6: 43, 38: 9, 23: 30, 130: 31, 70: 41, 138: 5}, 100: {44: 50, 6: 11, 99: 23, 122: 5, 138: 27, 3: 25, 95: 12, 91: 4, 131: 49, 11: 27, 26: 44, 58: 36}, 101: {11: 22, 2: 22, 36: 31, 132: 14, 50: 43, 44: 24, 106: 11, 105: 34}, 102: {68: 37, 97: 48, 94: 3, 104: 16, 11: 23, 39: 30, 10: 46, 91: 34, 86: 50, 47: 41, 52: 27, 90: 33, 113: 26, 38: 23, 55: 6, 72: 27, 140: 16, 106: 43, 33: 11, 139: 6}, 103: {79: 12, 10: 5, 127: 26, 140: 40, 118: 9, 80: 14, 128: 7, 49: 18, 108: 36, 84: 44, 14: 16, 26: 10, 98: 27, 21: 37, 52: 17, 129: 45}, 104: {22: 36, 136: 49, 37: 16, 27: 45, 94: 47, 112: 38, 102: 16, 58: 49, 26: 34, 74: 5, 50: 30, 55: 8, 52: 1, 108: 40, 72: 10, 54: 39}, 105: {11: 15, 40: 13, 62: 22, 87: 46, 74: 31, 45: 29, 101: 34, 78: 15, 66: 33, 116: 41, 137: 4, 72: 38, 123: 33, 31: 36, 84: 15, 119: 15}, 106: {53: 42, 29: 28, 102: 43, 101: 11, 33: 15, 46: 20, 3: 18, 41: 48}, 107: {26: 30, 19: 44, 59: 40, 92: 28, 84: 10, 57: 9, 110: 9, 99: 45, 47: 44, 68: 25, 60: 12, 127: 34, 50: 50, 41: 20, 126: 13, 133: 30}, 108: {34: 49, 94: 42, 115: 50, 103: 36, 104: 40, 62: 36, 64: 36, 11: 6, 1: 28, 7: 32, 6: 4, 55: 22}, 109: {60: 6, 75: 1, 73: 13, 132: 6, 47: 4, 16: 42, 2: 27, 63: 4, 136: 26, 18: 23, 74: 45, 32: 2, 76: 4, 20: 18, 36: 22, 55: 50, 70: 5, 48: 36}, 110: {140: 49, 53: 7, 79: 1, 44: 6, 125: 30, 107: 9, 61: 14, 45: 39, 113: 26, 128: 44}, 111: {75: 39, 116: 5, 20: 28, 134: 28, 130: 37, 19: 2, 3: 44, 86: 42, 91: 7, 36: 1, 95: 23, 50: 20, 38: 47, 21: 22}, 112: {121: 15, 91: 14, 136: 1, 98: 2, 104: 38, 21: 40, 33: 19, 118: 34, 29: 1, 44: 5, 92: 49, 114: 4, 45: 15, 62: 10, 138: 35, 11: 48, 32: 14, 68: 20, 69: 25, 41: 6, 15: 47, 90: 11}, 113: {44: 20, 66: 20, 29: 34, 102: 26, 122: 32, 39: 20, 74: 12, 22: 13, 127: 10, 130: 42, 25: 35, 110: 26, 59: 38, 40: 1}, 114: {112: 4, 99: 28, 73: 8, 22: 19, 25: 11, 23: 7, 66: 33, 35: 48, 123: 40, 120: 8}, 115: {27: 39, 139: 42, 36: 29, 60: 19, 35: 31, 85: 20, 22: 2, 54: 45, 48: 39, 128: 31, 131: 18, 108: 50, 78: 27, 29: 2, 13: 35, 97: 3, 11: 47, 15: 38, 83: 46, 71: 49}, 116: {36: 36, 26: 17, 126: 43, 12: 46, 111: 5, 92: 25, 46: 38, 51: 21, 138: 9, 133: 35, 105: 41, 59: 46, 96: 9, 68: 32}, 117: {87: 26, 127: 24, 36: 18, 123: 7, 7: 3, 6: 30, 53: 40, 73: 19, 120: 19, 122: 3, 81: 11, 77: 8}, 118: {29: 2, 1: 36, 54: 14, 99: 49, 98: 30, 131: 35, 76: 45, 140: 36, 95: 37, 103: 9, 112: 34, 80: 42, 6: 46, 3: 3, 73: 37, 83: 21, 86: 8, 71: 36, 96: 27, 92: 47}, 119: {77: 48, 60: 49, 87: 49, 95: 41, 10: 32, 136: 18, 18: 42, 131: 1, 105: 15, 15: 5}, 120: {75: 42, 29: 43, 7: 31, 117: 19, 56: 48, 91: 41, 21: 7, 17: 3, 64: 10, 12: 45, 71: 7, 47: 43, 114: 8, 55: 26}, 121: {1: 11, 112: 15, 64: 5, 59: 44, 138: 17, 80: 34, 134: 19, 29: 5, 44: 46, 82: 33, 54: 30, 128: 34, 132: 18, 76: 46, 95: 45, 70: 32, 98: 29, 74: 43}, 122: {91: 6, 15: 41, 61: 38, 58: 22, 80: 46, 130: 38, 117: 3, 70: 41, 100: 5, 20: 45, 77: 4, 71: 33, 1: 48, 113: 32, 87: 43, 79: 47, 37: 44, 134: 15}, 123: {130: 13, 42: 5, 58: 38, 91: 39, 117: 7, 19: 8, 137: 2, 136: 21, 23: 14, 105: 33, 17: 27, 5: 15, 39: 3, 54: 33, 47: 34, 70: 41, 48: 15, 114: 40, 55: 28, 139: 22}, 124: {73: 4, 62: 27, 86: 28, 54: 31}, 125: {36: 22, 90: 34, 8: 8, 35: 6, 15: 47, 110: 30, 50: 43, 3: 47, 139: 20, 64: 19}, 126: {73: 49, 90: 7, 6: 21, 116: 43, 136: 39, 74: 31, 128: 32, 139: 27, 12: 50, 69: 3, 129: 21, 38: 15, 8: 21, 107: 13}, 127: {117: 24, 103: 26, 6: 6, 94: 38, 75: 14, 90: 15, 74: 43, 66: 13, 93: 10, 137: 9, 107: 34, 113: 10}, 128: {30: 4, 24: 24, 84: 31, 11: 44, 115: 31, 103: 7, 63: 41, 126: 32, 71: 9, 89: 16, 121: 34, 35: 17, 33: 27, 25: 35, 110: 44, 68: 49}, 129: {71: 47, 11: 48, 28: 17, 69: 7, 68: 36, 15: 41, 103: 45, 126: 21}, 130: {43: 48, 123: 13, 122: 38, 96: 26, 99: 31, 10: 20, 52: 31, 111: 37, 92: 43, 74: 20, 113: 42, 2: 9}, 131: {71: 28, 54: 34, 118: 35, 3: 43, 10: 37, 66: 49, 47: 43, 92: 24, 4: 33, 134: 38, 88: 37, 81: 2, 99: 37, 115: 18, 21: 31, 25: 33, 7: 15, 74: 12, 37: 4, 100: 49, 119: 1, 50: 45, 51: 4, 17: 25}, 132: {101: 14, 60: 18, 109: 6, 84: 43, 3: 27, 121: 18, 85: 28, 70: 8}, 133: {71: 7, 7: 15, 99: 12, 69: 40, 116: 35, 86: 42, 25: 17, 31: 37, 107: 30, 19: 17}, 134: {131: 38, 135: 26, 88: 25, 36: 44, 89: 6, 121: 19, 111: 28, 79: 20, 78: 20, 98: 12, 122: 15, 85: 31}, 135: {3: 11, 34: 34, 134: 26, 138: 49, 84: 43, 74: 4, 86: 25, 26: 2, 27: 28, 47: 37, 62: 20, 90: 12}, 136: {104: 49, 112: 1, 19: 35, 61: 25, 46: 4, 34: 38, 123: 21, 28: 42, 65: 19, 126: 39, 54: 8, 82: 27, 3: 30, 86: 6, 18: 6, 98: 20, 119: 18, 137: 23, 22: 35, 109: 26}, 137: {88: 26, 44: 14, 76: 48, 123: 2, 90: 43, 92: 28, 136: 23, 49: 27, 18: 11, 21: 40, 50: 30, 3: 42, 138: 34, 105: 4, 127: 9, 13: 11}, 138: {30: 50, 121: 17, 135: 49, 64: 26, 71: 44, 28: 49, 68: 47, 100: 27, 84: 42, 116: 9, 45: 29, 137: 34, 99: 5, 112: 35, 26: 18, 19: 46, 43: 11, 20: 48, 15: 12, 44: 22}, 139: {115: 42, 98: 28, 5: 50, 74: 9, 126: 27, 58: 30, 51: 8, 43: 9, 79: 40, 68: 21, 11: 29, 66: 36, 102: 6, 6: 15, 123: 22, 96: 27, 40: 7, 125: 20}, 140: {103: 40, 110: 49, 118: 36, 53: 46, 39: 42, 29: 32, 40: 33, 102: 16}}
sizeArray = [size10, size50, size90, size140]
t = [10, 50, 90, 140]
for x in sizeArray:
timer(x, 1)
print("Dijkstras vs Branch and Bound", dijTimer)
for i in t:
b = test.size_graph(i)
time_bb = test.timer(b)
bbTimer.append(time_bb)
print("Branch and Bound", bbTimer)
y = bbTimer
y2 = dijTimer
x = t
fig = plt.figure()
ax = plt.subplot(111)
ax.plot(x, y, label='Branch and Bound')
ax.plot(x, y2, label='Dijkstras')
plt.xlabel('Size')
plt.ylabel('Runtime')
plt.title('Branch and Bound vs Dijkstras')
ax.legend()
plt.show()