Subversion Repositories programming

Rev

Rev 396 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 396 Rev 397
Line 15... Line 15...
15 
# 6) Generate M from the children of N
 15 
# 6) Generate M from the children of N
16 
# 7) Add anything not in M not in (CLOSED union OPEN) to OPEN
 16 
# 7) Add anything not in M not in (CLOSED union OPEN) to OPEN
17 
# 8) Reorder OPEN appropriately
 17 
# 8) Reorder OPEN appropriately
18 
# 9) goto LOOP
 18 
# 9) goto LOOP
19 
 
 19 
 
20 
# Fix for the lame version of python on the school's computers (v2.1)
 20 
from PyCompat import * # fixes for school computers
21 
try:
 - 
 
22 
	(True, False)
 - 
 
23 
except NameError:
 - 
 
24 
	(True, False) = (1, 0)
 - 
 
25 
 
 21 
 
26 
from PuzzlePiece import PuzzlePiece
 22 
from PuzzlePiece import PuzzlePiece
27 
from Graph import Graph
 23 
from Graph import Graph
28 
 
 24 
 
29 
# See if we can import GraphViz binding
 - 
 
30 
try:
 - 
 
31 
	no_graphviz = False
 25 
if have_yapgvb():
32 
	import yapgvb
 26 
	import yapgvb
33 
except ImportError:
 - 
 
34 
	no_graphviz = True
 - 
 
35 
 
 27 
 
36 
class SearchResult:
 28 
class SearchResult (object):
37 
	"""Class to store a search result"""
 29 
	"""Class to store a search result"""
38 
 
 30 
 
39 
	def __init__ (self, completed, status, depth_reached, nodes_created, result_graph):
 31 
	def __init__ (self, completed, status, depth_reached, nodes_created, result_graph):
40 
		self.completed = completed
 32 
		self.completed = completed
41 
		self.status = status
 33 
		self.status = status
Line 56... Line 48...
56 
 
 48 
 
57 
	def set_search_name (self, name):
 49 
	def set_search_name (self, name):
58 
		self.search_name = name
 50 
		self.search_name = name
59 
 
 51 
 
60 
 
 52 
 
61 
class PuzzleSearch:
 53 
class PuzzleSearch (object):
62 
	"""Implements a graph search"""
 54 
	"""Implements a graph search"""
63 
 
 55 
 
64 
	def __init__ (self, start_node, goal_nodes):
 56 
	def __init__ (self, start_node, goal_nodes):
65 
		"""Constructor.
 57 
		"""Constructor.
66 
		start_node: the node to start at (must have a get_children() function)
 58 
		start_node: the node to start at (must have a get_children() function)
Line 70... Line 62...
70 
		self.__goal_nodes = goal_nodes
 62 
		self.__goal_nodes = goal_nodes
71 
 
 63 
 
72 
	def __find_nearest_child (self, children, already_visited):
 64 
	def __find_nearest_child (self, children, already_visited):
73 
		"""Find the child that we came from. This necessitates that
 65 
		"""Find the child that we came from. This necessitates that
74 
		the list already_visited be sorted in the order of nodes visited"""
 66 
		the list already_visited be sorted in the order of nodes visited"""
75 
 
 - 
 
76 
		# This is the stupidest hack ever (gotta hate they school computers!)
 - 
 
77 
		rev = already_visited[:]
 - 
 
78 
		rev.reverse()
 - 
 
79 
 
 - 
 
80 
		for n in rev: #reversed(already_visited):
 67 
		for n in reversed(already_visited):
81 
			if n in children:
 68 
			if n in children:
82 
				return n
 69 
				return n
83 
 
 70 
 
84 
		# This should never happen
 71 
		# This should never happen
85 
		raise ValueError
 72 
		raise ValueError
Line 108... Line 95...
108 
			if not firsttime:
 95 
			if not firsttime:
109 
				v1 = str(N)
 96 
				v1 = str(N)
110 
				v2 = str(self.__find_nearest_child (M, CLOSED))
 97 
				v2 = str(self.__find_nearest_child (M, CLOSED))
111 
 
 98 
 
112 
				result.add_edge (v1, v2)
 99 
				result.add_edge (v1, v2)
113 
				result.set_edge_color (v1, v2, 'red')
 100 
				result.set_edge_color (v1, v2, yapgvb.colors.red)
114 
				result.set_edge_label (v1, v2, str(counter))
 101 
				result.set_edge_label (v1, v2, str(counter))
115 
 
 102 
 
116 
			else:
 103 
			else:
117 
				# Set start node shape to be a double circle
 104 
				# Set start node shape to be a double circle
118 
				result.set_vertex_shape (str(N), 'doublecircle')
 105 
				result.set_vertex_shape (str(N), yapgvb.shapes.doublecircle)
119 
				firsttime = False
 106 
				firsttime = False
120 
			###############################################################
 107 
			###############################################################
121 
 
 108 
 
122 
			# Check if we've reached the goal
 109 
			# Check if we've reached the goal
123 
			if N in self.__goal_nodes:
 110 
			if N in self.__goal_nodes:
124 
				# Set the goal node's shape to be a diamond
 111 
				# Set the goal node's shape to be a diamond
125 
				result.set_vertex_shape (str(N), 'diamond')
 112 
				result.set_vertex_shape (str(N), yapgvb.shapes.diamond)
126 
 
 113 
 
127 
				# Create the return result
 114 
				# Create the return result
128 
				search_result = SearchResult (completed=True,
 115 
				search_result = SearchResult (completed=True,
129 
							status='Success',
 116 
							status='Success',
130 
							depth_reached=N.depth,
 117 
							depth_reached=N.depth,
Line 253... Line 240...
253 
	result.set_search_name ('A*-search: Distance-from-correct')
 240 
	result.set_search_name ('A*-search: Distance-from-correct')
254 
	print result
 241 
	print result
255 
	print
 242 
	print
256 
 
 243 
 
257 
	if result.result_graph != None:
 244 
	if result.result_graph != None:
- 
 
 245 
		if have_yapgvb():
258 
		DrawGraph ('result', result.result_graph).render_graphviz ('res.svg', yapgvb.engines.dot)
 246 
			DrawGraph ('result', result.result_graph).render_graphviz ('res.svg', yapgvb.engines.dot)
- 
 
 247 
 
259 
		DrawGraph ('result', result.result_graph).render_stupid  ('generated_by')
 248 
		DrawGraph ('result', result.result_graph).render_stupid ('generated_by')
260 
	else:
 249 
	else:
261 
		print 'Failed to render graph'
 250 
		print 'Failed to render graph'
262 
 
 251 
 
263 
 
 252 
 
264 
if __name__ == '__main__':
 253 
if __name__ == '__main__':