-
Notifications
You must be signed in to change notification settings - Fork 0
/
ps10_3.py
executable file
·302 lines (251 loc) · 9.97 KB
/
ps10_3.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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
# 6.00 Problem Set 10
# Graph optimization
# Finding shortest paths through MIT buildings
#
# Name:
# Collaborators:
#
import time
from graph import SmartNode, WeightedEdge, Path, SmartDigraph
#
# Problem 2: Building up the Campus Map
#
# Write a couple of sentences describing how you will model the
# problem as a graph
#
def load_map(mapFilename):
"""
Parses the map file and constructs a directed graph
Parameters:
mapFilename : name of the map file
Assumes:
Each entry in the map file consists of the following four positive
integers, separated by a blank space:
From To TotalDistance DistanceOutdoors
e.g.
32 76 54 23
This entry would become an edge from 32 to 76.
Returns:
a directed graph representing the map
"""
print "Loading map from file..."
campus_graph = SmartDigraph()
with open(mapFilename, 'r') as map_file:
for line in map_file.readlines():
(start_loc,
end_loc,
total_distance,
distance_outdoors) = line.split()
start_node = SmartNode(start_loc)
end_node = SmartNode(end_loc)
if not campus_graph.hasNode(start_node):
campus_graph.addNode(start_node)
if not campus_graph.hasNode(end_node):
campus_graph.addNode(end_node)
edge = WeightedEdge(start_node,
end_node,
int(total_distance),
int(distance_outdoors))
campus_graph.addEdge(edge)
return campus_graph
#
# Problem 3: Finding the Shortest Path using Brute Force Search
#
# State the optimization problem as a function to minimize
# and the constraints
#
def timeit(func):
def _timeit(*args, **kwargs):
start = time.time()
try:
result = func(*args, **kwargs)
except ValueError:
raise
else:
return result
finally:
duration = time.time() - start
print '{0} ran for: {1:0.5f} secs.'.format(func.__name__, duration)
return _timeit
@timeit
def bruteForceSearch(digraph, start, end, maxTotalDist, maxDistOutdoors):
"""
Finds the shortest path from start to end using brute-force approach.
The total distance travelled on the path must not exceed maxTotalDist, and
the distance spent outdoor on this path must not exceed maxDisOutdoors.
Parameters:
digraph: instance of class Digraph or its subclass
start, end: start & end building numbers (strings)
maxTotalDist : maximum total distance on a path (integer)
maxDistOutdoors: maximum distance spent outdoors on a path (integer)
Assumes:
start and end are numbers for existing buildings in graph
Returns:
The shortest-path from start to end, represented by
a list of building numbers (in strings), [n_1, n_2, ..., n_k],
where there exists an edge from n_i to n_(i+1) in digraph,
for all 1 <= i < k.
If there exists no path that satisfies maxTotalDist and
maxDistOutdoors constraints, then raises a ValueError.
"""
stack = [Path([SmartNode(start)], 0, 0)]
valid_paths = []
while stack:
path = stack.pop(-1)
for edge in digraph.childrenOf(path.get_current_position()):
if not path.is_node_visited(edge.getDestination()):
new_path = path.clone()
new_path.add_edge(edge)
# "...consider first finding all valid paths that satisfy
# the max distance outdoors constraint,..."
if new_path.distance_outdoors <= maxDistOutdoors:
if new_path.is_end_reached(end):
valid_paths.append(new_path)
else:
stack.append(new_path)
# "... and then going through those paths and returning the shortest,
# rather than trying to fulfill both constraints at once..."
valid_paths = filter(lambda path: path.total_distance <= maxTotalDist,
valid_paths)
# min will raise a ValueError if an empty sequence is passed to it
shortest = min(valid_paths, key=lambda x: x.total_distance)
return shortest.get_node_list()
#
# Problem 4: Finding the Shorest Path using Optimized Search Method
#
@timeit
def directedDFS(digraph, start, end, maxTotalDist, maxDistOutdoors):
"""
Finds the shortest path from start to end using directed depth-first.
search approach. The total distance travelled on the path must not
exceed maxTotalDist, and the distance spent outdoor on this path must
not exceed maxDisOutdoors.
Parameters:
digraph: instance of class Digraph or its subclass
start, end: start & end building numbers (strings)
maxTotalDist : maximum total distance on a path (integer)
maxDistOutdoors: maximum distance spent outdoors on a path (integer)
Assumes:
start and end are numbers for existing buildings in graph
Returns:
The shortest-path from start to end, represented by
a list of building numbers (in strings), [n_1, n_2, ..., n_k],
where there exists an edge from n_i to n_(i+1) in digraph,
for all 1 <= i < k.
If there exists no path that satisfies maxTotalDist and
maxDistOutdoors constraints, then raises a ValueError.
"""
stack = [Path([SmartNode(start)], 0, 0)]
while stack:
path = stack.pop(-1)
for edge in digraph.childrenOf(path.get_current_position()):
if not path.is_node_visited(edge.getDestination()):
new_path = path.clone()
new_path.add_edge(edge)
if (new_path.distance_outdoors <= maxDistOutdoors and
new_path.total_distance <= maxTotalDist):
if new_path.is_end_reached(end):
return new_path.get_node_list()
else:
stack.append(new_path)
raise ValueError()
# Uncomment below when ready to test
if __name__ == '__main__':
# Test cases
digraph = load_map("mit_map.txt")
LARGE_DIST = 1000000
# Test case 1
print "---------------"
print "Test case 1:"
print "Find the shortest-path from Building 32 to 56"
expectedPath1 = ['32', '56']
brutePath1 = bruteForceSearch(digraph, '32', '56', LARGE_DIST, LARGE_DIST)
dfsPath1 = directedDFS(digraph, '32', '56', LARGE_DIST, LARGE_DIST)
print "Expected: ", expectedPath1
print "Brute-force: ", brutePath1
print "DFS: ", dfsPath1
# Test case 2
print "---------------"
print "Test case 2:"
print "Find the shortest-path from Building 32 to 56 without going out"
expectedPath2 = ['32', '36', '26', '16', '56']
brutePath2 = bruteForceSearch(digraph, '32', '56', LARGE_DIST, 0)
dfsPath2 = directedDFS(digraph, '32', '56', LARGE_DIST, 0)
print "Expected: ", expectedPath2
print "Brute-force: ", brutePath2
print "DFS: ", dfsPath2
# Test case 3
print "---------------"
print "Test case 3:"
print "Find the shortest-path from Building 2 to 9"
expectedPath3 = ['2', '3', '7', '9']
brutePath3 = bruteForceSearch(digraph, '2', '9', LARGE_DIST, LARGE_DIST)
dfsPath3 = directedDFS(digraph, '2', '9', LARGE_DIST, LARGE_DIST)
print "Expected: ", expectedPath3
print "Brute-force: ", brutePath3
print "DFS: ", dfsPath3
# Test case 4
print "---------------"
print "Test case 4:"
print "Find the shortest-path from Building 2 to 9 without going outdoors"
expectedPath4 = ['2', '4', '10', '13', '9']
brutePath4 = bruteForceSearch(digraph, '2', '9', LARGE_DIST, 0)
dfsPath4 = directedDFS(digraph, '2', '9', LARGE_DIST, 0)
print "Expected: ", expectedPath4
print "Brute-force: ", brutePath4
print "DFS: ", dfsPath4
# Test case 5
print "---------------"
print "Test case 5:"
print "Find the shortest-path from Building 1 to 32"
expectedPath5 = ['1', '4', '12', '32']
brutePath5 = bruteForceSearch(digraph, '1', '32', LARGE_DIST, LARGE_DIST)
dfsPath5 = directedDFS(digraph, '1', '32', LARGE_DIST, LARGE_DIST)
print "Expected: ", expectedPath5
print "Brute-force: ", brutePath5
print "DFS: ", dfsPath5
# Test case 6
print "---------------"
print "Test case 6:"
print "Find the shortest-path from Building 1 to 32 without going outdoors"
expectedPath6 = ['1', '3', '10', '4', '12', '24', '34', '36', '32']
brutePath6 = bruteForceSearch(digraph, '1', '32', LARGE_DIST, 0)
dfsPath6 = directedDFS(digraph, '1', '32', LARGE_DIST, 0)
print "Expected: ", expectedPath6
print "Brute-force: ", brutePath6
print "DFS: ", dfsPath6
# Test case 7
print "---------------"
print "Test case 7:"
print "Find the shortest-path from Building 8 to 50 without going outdoors"
bruteRaisedErr = 'No'
dfsRaisedErr = 'No'
try:
bruteForceSearch(digraph, '8', '50', LARGE_DIST, 0)
except ValueError:
bruteRaisedErr = 'Yes'
try:
directedDFS(digraph, '8', '50', LARGE_DIST, 0)
except ValueError:
dfsRaisedErr = 'Yes'
print "Expected: No such path! Should throw a value error."
print "Did brute force search raise an error?", bruteRaisedErr
print "Did DFS search raise an error?", dfsRaisedErr
# Test case 8
print "---------------"
print "Test case 8:"
print "Find the shortest-path from Building 10 to 32 without walking"
print "more than 100 meters in total"
bruteRaisedErr = 'No'
dfsRaisedErr = 'No'
try:
bruteForceSearch(digraph, '10', '32', 100, LARGE_DIST)
except ValueError:
bruteRaisedErr = 'Yes'
try:
directedDFS(digraph, '10', '32', 100, LARGE_DIST)
except ValueError:
dfsRaisedErr = 'Yes'
print "Expected: No such path! Should throw a value error."
print "Did brute force search raise an error?", bruteRaisedErr
print "Did DFS search raise an error?", dfsRaisedErr