Subversion Repositories programming

Rev

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

Rev 393 Rev 395
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)
- 
 
 21 
try:
- 
 
 22 
	(True, False)
- 
 
 23 
except NameError:
- 
 
 24 
	(True, False) = (1, 0)
- 
 
 25 
 
20 
from PuzzlePiece import PuzzlePiece
 26 
from PuzzlePiece import PuzzlePiece
21 
from Graph import Graph
 27 
from Graph import Graph
22 
import yapgvb
 - 
 
23 
 
 28 
 
- 
 
 29 
# See if we can import GraphViz binding
- 
 
 30 
try:
- 
 
 31 
	no_graphviz = False
- 
 
 32 
	import yapgvb
- 
 
 33 
except ImportError:
- 
 
 34 
	no_graphviz = True
- 
 
 35 
 
24 
class SearchResult (object):
 36 
class SearchResult:
25 
	"""Class to store a search result"""
 37 
	"""Class to store a search result"""
26 
 
 38 
 
27 
	def __init__ (self, completed, status, depth_reached, nodes_created, result_graph):
 39 
	def __init__ (self, completed, status, depth_reached, nodes_created, result_graph):
28 
		self.completed = completed
 40 
		self.completed = completed
29 
		self.status = status
 41 
		self.status = status
Line 44... Line 56...
44 
 
 56 
 
45 
	def set_search_name (self, name):
 57 
	def set_search_name (self, name):
46 
		self.search_name = name
 58 
		self.search_name = name
47 
 
 59 
 
48 
 
 60 
 
49 
class PuzzleSearch (object):
 61 
class PuzzleSearch:
50 
	"""Implements a graph search"""
 62 
	"""Implements a graph search"""
51 
 
 63 
 
52 
	def __init__ (self, start_node, goal_nodes):
 64 
	def __init__ (self, start_node, goal_nodes):
53 
		"""Constructor.
 65 
		"""Constructor.
54 
		start_node: the node to start at (must have a get_children() function)
 66 
		start_node: the node to start at (must have a get_children() function)
Line 89... Line 101...
89 
			# Find all possible next paths
 101 
			# Find all possible next paths
90 
			M = N.get_children()
 102 
			M = N.get_children()
91 
 
 103 
 
92 
			###############################################################
 104 
			###############################################################
93 
			# Add the current place to the result graph
 105 
			# Add the current place to the result graph
94 
			result.add_vertex (str(N))
 106 
			result.add_vertex (str(N), str(counter), raw_obj=N)
95 
 
 107 
 
96 
			if not firsttime:
 108 
			if not firsttime:
97 
				v1 = str(N)
 109 
				v1 = str(N)
98 
				v2 = str(self.__find_nearest_child (M, CLOSED))
 110 
				v2 = str(self.__find_nearest_child (M, CLOSED))
99 
 
 111 
 
Line 241... Line 253...
241 
	result.set_search_name ('A*-search: Distance-from-correct')
 253 
	result.set_search_name ('A*-search: Distance-from-correct')
242 
	print result
 254 
	print result
243 
	print
 255 
	print
244 
 
 256 
 
245 
	if result.result_graph != None:
 257 
	if result.result_graph != None:
246 
		DrawGraph ('result', result.result_graph).render_graph ('res.svg', yapgvb.engines.dot)
 258 
		DrawGraph ('result', result.result_graph).render_graphviz ('res.svg', yapgvb.engines.dot)
- 
 
 259 
		DrawGraph ('result', result.result_graph).render_stupid  ('generated_by')
247 
	else:
 260 
	else:
248 
		print 'Failed to render graph'
 261 
		print 'Failed to render graph'
249 
 
 262 
 
250 
 
 263 
 
251 
if __name__ == '__main__':
 264 
if __name__ == '__main__':