FilesExpand file tree

master

/

ps5.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

244 lines (210 loc) · 8.7 KB

master

/

ps5.py

Copy path

Top

File metadata and controls

• Code
• Blame

244 lines (210 loc) · 8.7 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

# 6.00.2x Problem Set 5

# Graph optimization

# Finding shortest paths through MIT buildings

#

import string

# This imports everything from `graph.py` as if it was defined in this file!

from graph import *

#

# Problem 2: Building up the Campus Map

#

# Before you write any code, write a couple of sentences here

# describing how you will model this problem as a graph.

# building is vertex, the road is the edge, and distance is the weight

# This is a helpful exercise to help you organize your

# thoughts before you tackle a big design problem!

#

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

"""

# TODO

t = WeightedDigraph()

f = open(mapFilename)

for line in f :

ls = line.split()

if ls[0] not in t.nodes :

t.addNode(ls[0])

if ls[1] not in t.nodes :

t.addNode(ls[1])

edge = WeightedEdge(ls[0], ls[1], ls[2], ls[3])

t.addEdge(edge)

f.close()

return t

#

# Problem 3: Finding the Shortest Path using Brute Force Search

#

# State the optimization problem as a function to minimize

# and what the constraints are

#

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 maxDistOutdoors.

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.

"""

#TODO

pass

#

# Problem 4: Finding the Shorest Path using Optimized Search Method

#

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 maxDistOutdoors.

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.

"""

#TODO

pass

# Uncomment below when ready to test

#### NOTE! These tests may take a few minutes to run!! ####

if __name__ == '__main__':

# Test cases

mitMap = load_map("E:\edxpython\ProblemSet5\mit_map.txt")

print isinstance(mitMap, Digraph)

print isinstance(mitMap, WeightedDigraph)

nodes = mitMap.nodes

# print 'nodes', nodes

print 'edges', mitMap.edges

# 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(mitMap, '32', '56', LARGE_DIST, LARGE_DIST)

# dfsPath1 = directedDFS(mitMap, '32', '56', LARGE_DIST, LARGE_DIST)

# print "Expected: ", expectedPath1

# print "Brute-force: ", brutePath1

# print "DFS: ", dfsPath1

# print "Correct? BFS: {0}; DFS: {1}".format(expectedPath1 == brutePath1, expectedPath1 == dfsPath1)

# Test case 2

# print "---------------"

# print "Test case 2:"

# print "Find the shortest-path from Building 32 to 56 without going outdoors"

# expectedPath2 = ['32', '36', '26', '16', '56']

# brutePath2 = bruteForceSearch(mitMap, '32', '56', LARGE_DIST, 0)

# dfsPath2 = directedDFS(mitMap, '32', '56', LARGE_DIST, 0)

# print "Expected: ", expectedPath2

# print "Brute-force: ", brutePath2

# print "DFS: ", dfsPath2

# print "Correct? BFS: {0}; DFS: {1}".format(expectedPath2 == brutePath2, expectedPath2 == 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(mitMap, '2', '9', LARGE_DIST, LARGE_DIST)

# dfsPath3 = directedDFS(mitMap, '2', '9', LARGE_DIST, LARGE_DIST)

# print "Expected: ", expectedPath3

# print "Brute-force: ", brutePath3

# print "DFS: ", dfsPath3

# print "Correct? BFS: {0}; DFS: {1}".format(expectedPath3 == brutePath3, expectedPath3 == 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(mitMap, '2', '9', LARGE_DIST, 0)

# dfsPath4 = directedDFS(mitMap, '2', '9', LARGE_DIST, 0)

# print "Expected: ", expectedPath4

# print "Brute-force: ", brutePath4

# print "DFS: ", dfsPath4

# print "Correct? BFS: {0}; DFS: {1}".format(expectedPath4 == brutePath4, expectedPath4 == 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(mitMap, '1', '32', LARGE_DIST, LARGE_DIST)

# dfsPath5 = directedDFS(mitMap, '1', '32', LARGE_DIST, LARGE_DIST)

# print "Expected: ", expectedPath5

# print "Brute-force: ", brutePath5

# print "DFS: ", dfsPath5

# print "Correct? BFS: {0}; DFS: {1}".format(expectedPath5 == brutePath5, expectedPath5 == 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(mitMap, '1', '32', LARGE_DIST, 0)

# dfsPath6 = directedDFS(mitMap, '1', '32', LARGE_DIST, 0)

# print "Expected: ", expectedPath6

# print "Brute-force: ", brutePath6

# print "DFS: ", dfsPath6

# print "Correct? BFS: {0}; DFS: {1}".format(expectedPath6 == brutePath6, expectedPath6 == 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(mitMap, '8', '50', LARGE_DIST, 0)

# except ValueError:

# bruteRaisedErr = 'Yes'

# try:

# directedDFS(mitMap, '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(mitMap, '10', '32', 100, LARGE_DIST)

# except ValueError:

# bruteRaisedErr = 'Yes'

# try:

# directedDFS(mitMap, '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