-
Notifications
You must be signed in to change notification settings - Fork 0
/
GraphClass.py
171 lines (147 loc) · 10.4 KB
/
GraphClass.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
from NodeClass import Node
class Graph:
def __init__(self, nodes: list[Node]):
self.nodes = {node.name: node for node in nodes}
def get_branches_from(self, node_name: str):
"""Get all the branches adjacent to a given node.name. This is slightly different than Node's get_branches
because the branches attribute has node objects as its keys, whereas this method returns a dict with
the names of those node objects as keys."""
try:
return {node_obj.name: cost for node_obj, cost in self.nodes[node_name].get_branches().items()}
except KeyError:
raise Exception(f"\"{node_name}\" DNE in the nodes, {self.nodes}, of this Graph object.")
def get_vertices(self):
"""Get all the vertices in the graph."""
return tuple(self.nodes.keys())
def shortest_path(self, start_vertex, end_vertex):
"""Returns a tuple containing the shortest path and total cost
between start_vertex and end_vertex of a given table. See GraphVisualization.jpg and the table below
to format the table properly to create a Graph object out of it."""
# Construct a dictionary, with the keys representing the vertices and the values representing a list
# containing the shortest distance from start_vertex and the previous vertex.
#
# Vertex | Shortest Distance from start_vertex | Previous Vertex
# A | 0 |
# B | infinity | A
# C | infinity | A
# ...
table = {}
for vertex in self.get_vertices():
# Assume that every vertex is infinitely far away
table.update({vertex: [0 if vertex == start_vertex else float("inf"), ""]})
processed = [] # Create a list to store all future processed vertices
# A function that calculates the next vertex to process. First, it filters out every vertex that has been
# processed, and then grabs the vertex with the shortest distance from start_vertex.
calculate_vertex_to_process = lambda: min(dict(filter(lambda item: item[0] not in processed, table.items())),
key=lambda key: table[key][0])
# Store the result of the function above in vertex_to_process
vertex_to_process = calculate_vertex_to_process()
# Start looping until the destination vertex is about to be processed
while vertex_to_process != end_vertex:
# print("Vertex to process =", vertex_to_process)
# Grab all the branches and costs that vertex_to_process has, filtering out all the vertices that have been
# processed.
branches = {vertex: cost for vertex, cost in self.get_branches_from(vertex_to_process).items() if
vertex not in processed}
# Deal with node islands; raise an exception if start_vertex and end_vertex are not connected.
# If the number of vertex_to_process's branches that haven't been processed is 0, then vertex_to_process is
# the last node to process on an island. Since everything else has already been processed, catch this event
# and raise an exception.
if len(branches) == 0:
raise Exception(f"\"{start_vertex}\" & \"{end_vertex}\" aren't connected. Node \"{vertex_to_process}\""
f" can't be processed because it's the last on its island, which contains nodes"
f" {[f'{node}' for node in processed] + [f'{vertex_to_process}']}"
f" and were processed in that respective order.")
# Loop through each vertex and cost in the branches, and update the table accordingly.
for vertex, cost in branches.items():
# Calculate the distance from start_vertex to vertex_to_process
dist_from_start_vertex = table[vertex_to_process][0] + cost
if dist_from_start_vertex < table[vertex][0]:
# If that calculated distance is < the distance that's already in the table, updated it so that that
# value is the shortest distance from start_vertex to vertex_to_process
table[vertex] = [dist_from_start_vertex, vertex_to_process]
# Append vertex_to_process to processed, which was defined above.
processed.append(vertex_to_process)
# Recalculate the next vertex to process, and update vertex_to_process to equal that new vertex for the next
# loop iteration.
vertex_to_process = calculate_vertex_to_process()
# Create a list that will hold the shortest path from start_vertex to end_vertex.
path = []
# Create a variable to store a changing vertex. Personally, I didn't want to change the value of end_vertex.
looping_vertex = end_vertex
# Append end_vertex to the path; the while loop below will fill in the rest.
path.append(looping_vertex)
# This while loop basically is exactly the same as repeated VLOOKUPs in Excel/Google Sheets.
while looping_vertex != start_vertex:
# Append the value obtained from looping_vertex serving as the key to the table dictionary.
path.append(table[looping_vertex][1])
# Update the value of looping_vertex.
looping_vertex = table[looping_vertex][1]
# Return a tuple of the reversed version of path and the total cost of that shortest path.
return path[::-1], table[end_vertex][0]
def longest_path(self, start_vertex, end_vertex):
"""Returns a tuple containing the shortest path and total cost
between start_vertex and end_vertex of a given table. See GraphVisualization.jpg and the table below
to format the table properly to create a Graph object out of it."""
# Construct a dictionary, with the keys representing the vertices and the values representing a list
# containing the shortest distance from start_vertex and the previous vertex.
#
# Vertex | Shortest Distance from start_vertex | Previous Vertex
# A | 0 |
# B | infinity | A
# C | infinity | A
# ...
table = {}
for vertex in self.get_vertices():
# Assume that every vertex is infinitely far away in the negative direction
table.update({vertex: [0 if vertex == start_vertex else float("-inf"), ""]})
processed = [] # Create a list to store all future processed vertices
# A function that calculates the next vertex to process. First, it filters out every vertex that has been
# processed, and then grabs the vertex with the shortest distance from start_vertex.
calculate_vertex_to_process = lambda: max(dict(filter(lambda item: item[0] not in processed, table.items())),
key=lambda key: table[key][0])
# Store the result of the function above in vertex_to_process
vertex_to_process = calculate_vertex_to_process()
# Start looping until the destination vertex is about to be processed
while vertex_to_process != end_vertex:
# print("Vertex to process =", vertex_to_process)
# Grab all the branches and costs that vertex_to_process has, filtering out all the vertices that have been
# processed.
branches = {vertex: cost for vertex, cost in self.get_branches_from(vertex_to_process).items() if
vertex not in processed}
# Deal with node islands; raise an exception if start_vertex and end_vertex are not connected.
# If the number of vertex_to_process's branches that haven't been processed is 0, then vertex_to_process is
# the last node to process on an island. Since everything else has already been processed, catch this event
# and raise an exception.
if len(branches) == 0:
raise Exception(f"\"{start_vertex}\" & \"{end_vertex}\" aren't connected. Node \"{vertex_to_process}\""
f" can't be processed because it's the last on its island, which contains nodes"
f" {[f'{node}' for node in processed] + [f'{vertex_to_process}']}"
f" and were processed in that respective order.")
# Loop through each vertex and cost in the branches, and update the table accordingly.
for vertex, cost in branches.items():
# Calculate the distance from start_vertex to vertex_to_process
dist_from_start_vertex = table[vertex_to_process][0] + cost
if dist_from_start_vertex > table[vertex][0]:
# If that calculated distance is < the distance that's already in the table, updated it so that that
# value is the shortest distance from start_vertex to vertex_to_process
table[vertex] = [dist_from_start_vertex, vertex_to_process]
# Append vertex_to_process to processed, which was defined above.
processed.append(vertex_to_process)
# Recalculate the next vertex to process, and update vertex_to_process to equal that new vertex for the next
# loop iteration.
vertex_to_process = calculate_vertex_to_process()
# Create a list that will hold the shortest path from start_vertex to end_vertex.
path = []
# Create a variable to store a changing vertex. Personally, I didn't want to change the value of end_vertex.
looping_vertex = end_vertex
# Append end_vertex to the path; the while loop below will fill in the rest.
path.append(looping_vertex)
# This while loop basically is exactly the same as repeated VLOOKUPs in Excel/Google Sheets.
while looping_vertex != start_vertex:
# Append the value obtained from looping_vertex serving as the key to the table dictionary.
path.append(table[looping_vertex][1])
# Update the value of looping_vertex.
looping_vertex = table[looping_vertex][1]
# Return a tuple of the reversed version of path and the total cost of that shortest path.
return path[::-1], table[end_vertex][0]